二叉树

01 二叉树的性质

在二叉树的第n层上最多有2^n-1个结点
深度为k的二叉树最多有2^k-1个结点(k>=1)
对于任何一个二叉树T,度为0的结点数为n₀,度为2的结点数为n₂则n₀=n₂+1

　　解释:有n个结点的二叉树,除了根节点,其他每个结点都对应一条连线.所以由 n-1条线. 而度为2的对应两条连线,度为1的对应1条连线.所以 n-1 =n2*2+n1.

　　　　n个结点包括度分别为0,1,2的结点.所以n =n1+n2+n0 综合两个公式得出 n0 = n2+1

具有n个结点的完全二叉树的深度为[log₂ⁿ]+1 ([x]表示不大于x的最大整数
如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有

如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整

如果2i>n那么节点i没有左孩子，否则其左孩子为2i

如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

02代码实现(C语言实现)

  1 #include <stdio.h>
  2 #include <malloc.h>
  3 #include <stdlib.h>
  4 
  5 typedef char ElemType;
  6 
  7 //定义二叉树结点
  8 typedef struct BtNode {
  9     ElemType data;
 10     struct BtNode *lchild, *rchild;
 11 }BtNode, *BTree;
 12 
 13 
 14 //创建二叉树.使用#表示结点为空
 15 void CreateBTree(BTree &BT) {
 16     ElemType data;
 17     scanf_s("%c", &data);
 18     if (data == '#') {
 19         BT = NULL;
 20     }
 21     else
 22     {
 23         BT = (BTree)malloc(sizeof(BtNode));
 24         BT->data = data;
 25         CreateBTree(BT->lchild);
 26         CreateBTree(BT->rchild);
 27     }
 28 }
 29 
 30 //访问结点并输出
 31 void visit(BTree bt)
 32 {
 33     if (bt->data != NULL)
 34     {
 35         printf("%2c", bt->data);
 36     }
 37 }
 38 //前序遍历
 39 void PreNode(BTree bt)
 40 {
 41     if (bt != NULL)
 42     {
 43         visit(bt);
 44         PreNode(bt->lchild);
 45         PreNode(bt->rchild);
 46     }
 47 }
 48 //中序遍历
 49 void InNode(BTree bt)
 50 {
 51     if (bt != NULL)
 52     {
 53         InNode(bt->lchild);
 54         visit(bt);
 55         InNode(bt->rchild);
 56     }
 57 }
 58 //后序遍历
 59 void LastNode(BTree bt)
 60 {
 61     if (bt != NULL)
 62     {
 63         LastNode(bt->lchild);
 64         LastNode(bt->rchild);
 65         visit(bt);
 66     }
 67 }
 68 //树的深度
 69 int  len_tree(BTree bt) {
 70     int dl, dr, len;
 71     if (bt == NULL)
 72     {
 73         return 0;
 74     }
 75     else
 76     {
 77         dl = len_tree(bt->lchild);
 78         dr = len_tree(bt->rchild);
 79         len = (dl >= dr) ? dl : dr;
 80         return len + 1;
 81     }
 82 }
 83 //度为2的结点数
 84 int leaf_2(BTree bt)
 85 {
 86     if (bt == NULL) return 0;
 87     if (bt->lchild->data != NULL && bt->rchild->data != NULL)
 88     {
 89         return 1;
 90     }
 91 
 92     return leaf_2(bt->lchild) + leaf_2(bt->rchild);
 93 }
 94 //度为0的结点数
 95 int leaf_0(BTree bt)
 96 {
 97     if (bt == NULL) return 0;
 98     if (bt->lchild == NULL && bt->rchild == NULL)
 99     {
100         return 1;
101     }
102 
103     return leaf_0(bt->lchild) + leaf_0(bt->rchild);
104 }
105 int main()
106 {
107     BTree bt;
108     printf("先序建立一棵二叉树:\n");
109     CreateBTree(bt);
110 
111     printf("前序遍历:\n");
112     PreNode(bt);
113     printf("\n中序遍历:\n");
114     InNode(bt);
115     printf("\n后序遍历:\n");
116     LastNode(bt);
117 
118     printf("\n二叉树的深度：%d\n", len_tree(bt));
119     printf("\n二叉树度为2的结点：%d\n", leaf_2(bt));
120     printf("\n二叉树度为0的结点：%d\n", leaf_0(bt));
121     system("pause");
122 
123 }

二叉树

01 二叉树的性质

02代码实现(C语言实现)

推荐阅读