首页 > 代码库 > 树1---基础

树1---基础

2024-08-11 14:35:45   212人阅读

参考资料：

　　大话数据结构

　　http://blog.csdn.net/xy010902100449/article/details/46602273

 

【摘要】计算机科学中，二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。二叉树是递归定义的，因此，与二叉树有关的题目基本都可以用递归思想解决，当然有些题目非递归解法也应该掌握，如非递归遍历节点等等。本文努力对二叉树相关题目做一个较全的整理总结，希望对找工作的同学有所帮助。

本文内容如下所示 
1. 求二叉树中的节点个数 
2. 求二叉树的深度 
3. 前序遍历，中序遍历，后序遍历 
4. 分层遍历二叉树（按层次从上往下，从左往右） 
5. 将二叉查找树变为有序的双向链表 
6. 求二叉树第K层的节点个数 
7. 求二叉树中叶子节点的个数 
8. 判断两棵二叉树是否结构相同 
9. 判断二叉树是不是平衡二叉树 
10. 求二叉树的镜像 
11. 求二叉树中两个节点的最低公共祖先节点 
12. 求二叉树中节点的最大距离 
13. 由前序遍历序列和中序遍历序列重建二叉树 
14. 判断二叉树是不是完全二叉树

0-二叉树节点定义

1 //0.二叉树的二叉链表节点结构定义2 // 二叉链表表示法3 typedef struct BiTNode 4 {5     TElemType data;6     struct BiTNode *lchild,*rchild;7 } BiTNode,*BiTree;

 

 1-求二叉树中节点的个数

 1 //5.求树节点的个数 2 int GetNodeNum(BiTNode * pRoot) 3 { 4     if(pRoot == NULL) // 递归出口 5         return 0; 6     //cout<<pRoot->data; 7     int a=GetNodeNum(pRoot->lchild); 8     int b= GetNodeNum(pRoot->rchild); 9 10     return   a+ 1;11 }

 

2-求树的深度

//3.求二叉树的高度（深度）int GetDepth(BiTree pRoot){    if(pRoot == NULL) // 递归出口        return 0;    int depthLeft = GetDepth(pRoot->lchild);    int depthRight = GetDepth(pRoot->rchild);    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1); }

 

3-三种遍历

 1 //1.前序遍历 2 void PreOrder(BiTree T) 3 { 4     if(T==NULL) 5     { 6         return; 7     } 8     printf("%5d",T->data); 9     PreOrder(T->lchild);10     PreOrder(T->rchild);11 }12 13 //中序14 void InOrder(BiTree T)15 {16     if(T==NULL)17     {18         return;19     }20     InOrder(T->lchild);21 22     printf("%5d",T->data);23     24     InOrder(T->rchild);25 }26 27 //后序28 void PostOrder(BiTree T)29 {30     if(T==NULL)31     {32         return;33     }34     35     PreOrder(T->lchild);36     PreOrder(T->rchild);37     printf("%5d",T->data);38 }

 

4-求叶子节点个数

 1 void countLeaf3(BiTree T,int *sum) 2 { 3     if(T!=NULL) 4     { 5         if (T->lchild==NULL&&T->rchild==NULL) 6         { 7             (*sum)++; 8         } 9         if (T->lchild)10         {11             countLeaf3(T->lchild,sum);12         }13         if (T->rchild)14         {15             countLeaf3(T->rchild,sum);16         }17 18     }19 }

 

5-copy二叉树

 1 //4.copy 二叉树 2 BiTNode *CopyTree(BiTNode *T) 3 { 4     BiTNode *newNode=NULL; 5     BiTNode *newLp=NULL; 6     BiTNode *newRp=NULL; 7  8     if(T==NULL) 9     {10         return NULL;11     }12 13     if(T->lchild!=NULL)14     {15         newLp=CopyTree(T->lchild);16     }17     else18     {19         newLp=NULL;20     }21 22     if(T->rchild!=NULL)23     {24         newRp=CopyTree(T->lchild);25     }26     else27     {28         newRp=NULL;29     }30 31     //malloc根节点32     newNode=(BiTNode*)malloc(sizeof(BiTNode));33     if (newNode==NULL)34     {35         return NULL;36     }37     newNode->lchild=newLp;38     newNode->rchild=newRp;39     newNode->data=http://www.mamicode.com/T->data;40     return newNode;41 }

 

树1---基础


联系
我们