经典二叉树

用户1154259

发布于 2018-01-17 11:07:49

44200

代码可运行

文章被收录于专栏：xingoo, 一个梦想做发明家的程序员xingoo, 一个梦想做发明家的程序员

运行总次数：0

代码可运行

完全二叉树特点：

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);
}

中序遍历

void InOrderTree(BiTree *b){
    if( b == NULL)
        return ;
    InOrderTree(b->lchild);
    printf("%c",b->data);
    InOrderTree(b->rchild);
}

后序遍历

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 }