经典二叉树
彻底二叉树特色：
1 叶子节点只能出如今最下面两层
2 最下层的叶子必定集中在左部连续位置
3 倒数第二层，若是有叶子节点，必定都集中在右边
4 若是节点度为1，则该节点只有作孩子
5 一样节点数的二叉树，彻底二叉树深度最小
性质1：在二叉树的第i层上至多有2的（i-1）次幂个节点
性质2：深度为k的二叉树最多有2的k-1次幂个节点
性质3：叶子节点数为m,度为2的节点数为n，那么 m=n+1
性质4：具备n个节点的彻底二叉树深度为[log2n]+1
性质5：若是节点i的两个孩子是2i和2i+1
遍历方式
前序遍历
void PreOrderTree(BiTree *b){ if( b == NULL) return; printf("%c",b->data); PreOrderTree(b->lchild); PreOrderTree(b->rchild); }
中序遍历spa
void InOrderTree(BiTree *b){ if( b == NULL) return ; InOrderTree(b->lchild); printf("%c",b->data); InOrderTree(b->rchild); }
后序遍历code
void PostOrderTree(BiTree *b){ if( b == NULL) return ; PostOrderTree(b->lchild); PostOrderTree(b->rchild); printf("%c",b->data); }
所有代码
1 #include <stdio.h> 2 #include <stdlib.h> 3 typedef struct BiTree{ 4 int data; 5 struct BiTree * lchild,*rchild; 6 }BiTree; 7 8 void initTree(BiTree *b); 9 void PreOrderTree(BiTree *b); 10 void InOrderTree(BiTree *b); 11 void PostOrderTree(BiTree *b); 12 13 int main() 14 { 15 BiTree *b = (BiTree *)malloc(sizeof(BiTree)); 16 initTree(b); 17 PreOrderTree(b); 18 printf("\n"); 19 InOrderTree(b); 20 printf("\n"); 21 PostOrderTree(b); 22 printf("\n"); 23 free(b); 24 return 0; 25 } 26 void initTree(BiTree *b){ 27 b->data = 'A'; 28 BiTree *b1 = (BiTree *)malloc(sizeof(BiTree)); 29 b->lchild = b1; 30 b1->data = 'B'; 31 32 BiTree *b2 = (BiTree *)malloc(sizeof(BiTree)); 33 b->rchild = b2; 34 b2->data = 'C'; 35 36 BiTree *b3 = (BiTree *)malloc(sizeof(BiTree)); 37 b1->lchild = b3; 38 b3->data = 'D'; 39 40 BiTree *b4 = (BiTree *)malloc(sizeof(BiTree)); 41 b1->rchild = b4; 42 b4->data = 'E'; 43 b4->lchild = NULL; 44 b4->rchild = NULL; 45 46 BiTree *b5 = (BiTree *)malloc(sizeof(BiTree)); 47 b2->lchild = b5; 48 b5->data = 'F'; 49 b5->lchild = NULL; 50 b5->rchild = NULL; 51 52 BiTree *b6 = (BiTree *)malloc(sizeof(BiTree)); 53 b2->rchild = b6; 54 b6->data = 'G'; 55 b6->lchild = NULL; 56 b6->rchild = NULL; 57 58 BiTree *b7 = (BiTree *)malloc(sizeof(BiTree)); 59 b3->lchild = b7; 60 b7->data = 'H'; 61 b7->lchild = NULL; 62 b7->rchild = NULL; 63 64 BiTree *b8 = (BiTree *)malloc(sizeof(BiTree)); 65 b3->rchild = b8; 66 b8->data = 'I'; 67 b8->lchild = NULL; 68 b8->rchild = NULL; 69 } 70 void PreOrderTree(BiTree *b){ 71 if( b == NULL) 72 return; 73 printf("%c",b->data); 74 PreOrderTree(b->lchild); 75 PreOrderTree(b->rchild); 76 } 77 78 void InOrderTree(BiTree *b){ 79 if( b == NULL) 80 return ; 81 InOrderTree(b->lchild); 82 printf("%c",b->data); 83 InOrderTree(b->rchild); 84 } 85 86 void PostOrderTree(BiTree *b){ 87 if( b == NULL) 88 return ; 89 PostOrderTree(b->lchild); 90 PostOrderTree(b->rchild); 91 printf("%c",b->data); 92 }
运行结果
