首页 > 代码库 > 树和二叉树
树和二叉树
树：n（n≥0）个结点的有限集。
在任一棵非空树中： 1.有且仅有一个特定称为根的结点 2.n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tn，Ti称为树的子树。
树的性质： 递归性 层次性
基本术语： 树的结点：数据元素及若干指向其子树的分支
叶子（终端结点）：度（分支的个数）为零的结点
分支结点（非终端结点）：度大于零的结点
结点的度：分支的个数
树的度：树中所有结点的度的最大值
树的深度（高度）：树中叶子结点所在的最大层次
孩子(结点)：结点子树的根称为该结点的孩子
祖先(结点) ：从根到该结点所经分支上的所有结点。
子孙(结点) ：以某结点为根的子树的任一结点
兄弟(结点) ：同一双亲的孩子互称兄弟。
堂兄弟(结点) ：双亲在同一层的结点互称堂兄弟
有序树：树中结点的各子树从左到右有次序(不能互换)。
无序树：树中结点的各子树从左到右无次序(能互换)。
森林：m（m≥0）棵互不相交的树的集合
二叉树递归定义：由n(n>=0)个结点的有限集合，或为空集，或由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。
二叉树的五种不同形态：
二叉树的性质：（证明过程略）
性质1：在二叉树的第i层上至多有2i-1个结点(i>=1)。
性质2：深度为k的二叉树至多有2k－1个结点（k>=1).
性质3：对任一棵二叉树，若其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。
性质4：有n个结点的完全二叉树的深度为log2n ＋1
满二叉树：一棵深度为k且有2k-1个结点的二叉树。
完全二叉树：若深度为k、有n个结点的二叉树中各结点能与深度为k的顺序编号的满二叉树编号从1到n的结点相对应。 所有的叶结点都出现在第k层或k－1层。 若任一结点右子树最大层次为l，其左子树最大层次为1或l＋1。
二叉树的存储结构：（1）顺序储存结构
（2）链式储存结构
以下代码实现采取链式储存结构
1 #include<stdio.h> 2 #include<stdlib.h> 3 4 #define OK 1 5 #define ERROR -1 6 #define OVERFLOW -2 7 8 9 typedef int TElem; 10 typedef int Status; 11 12 typedef struct BiTNode 13 { 14 TElem data; 15 struct BiTNode *lchild,*rchild; //左右孩子指针 16 } BiTNode,*BiTree; 17 18 /***函数原型**/ 19 Status CreateBiTree(BiTree &T); 20 //安先序次序输入二叉树中结点值，空格字符表示空树,构造二叉树表表示的二叉树T 21 Status PreOrderTraverse(BiTree T,Status(*visit)(TElem e)); 22 //采用二叉树表储存结构，visit是对应结点操作的应用函数 23 //先序遍历二叉树T，对每个结点调用函数visit一次且仅一次 24 //一旦visit()失败，则操作失败 25 Status InorderTraverse(BiTree T,Status(*visit)(TElem e)); 26 //中序遍历二叉树T，对每个结点调用函数visit一次且仅一次 27 Status PostOrderTraverse(BiTree T,Status(*visit)(TElem e)); 28 //后序遍历二叉树T，对每个结点调用函数visit一次且仅一次 29 void visit(TElem e); 30 //输出 31 32 void visit(TElem e) 33 { 34 printf("%d ",e); 35 } 36 37 Status CreateBiTree(BiTree *T) 38 { 39 TElem e; 40 scanf("%d",&e); 41 42 if(e==0) 43 { 44 *T=NULL; 45 } 46 47 else 48 { 49 *T = (BiTree) malloc(sizeof(BiTNode)); 50 if (!T) 51 { 52 exit(OVERFLOW); 53 } 54 (*T)->data =http://www.mamicode.com/ e; 55 CreateBiTree(&(*T)->lchild); //创建左子树 56 CreateBiTree(&(*T)->rchild); //创建右子树 57 } 58 return 0; 59 } 60 61 Status PreOrderTraverse(BiTree T,void(*visit)(TElem)) 62 { 63 64 if(T) 65 { 66 visit(T->data); 67 PreOrderTraverse(T->lchild,visit); 68 PreOrderTraverse(T->rchild,visit); 69 70 } 71 else return OK; 72 } 73 74 75 Status InOrderTraverse(BiTree T,void(*visit)(TElem)) 76 { 77 if(T) 78 { 79 InOrderTraverse(T->lchild,visit); 80 visit(T->data); 81 InOrderTraverse(T->rchild,visit); 82 } 83 84 } 85 86 Status PostOrderTraverse(BiTree T,void (*visit)(TElem)) 87 { 88 if(T) 89 { 90 PostOrderTraverse(T->lchild,visit); 91 PostOrderTraverse(T->rchild,visit); 92 visit(T->data); 93 } 94 } 95 96 int main() 97 { 98 BiTree T; 99 100 printf("创建一个树，输入0为空数");101 CreateBiTree(&T);102 printf("先序遍历：");103 PreOrderTraverse(T, *visit);104 printf("\n中序遍历：");105 InOrderTraverse(T, *visit);106 printf("\n后序遍历：");107 PostOrderTraverse(T, *visit);108 printf("\n"); 109 }
树和二叉树