二叉树的递归遍历和销毁c++_二叉树遍历销毁

二叉树的建立

//按前序输入二叉树中节点的值(一个字符)
// '#'表示空树， 构造二叉链表表示二叉树T
bool CreateBiTree(BiTree &T){
    ElemType ch;

    scanf("%c",&ch);//@@@
    if(ch == '#'){
        //printf("您要创建一棵空树吗？\n");
        T=NULL;//
        return false;
    }
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T){
            printf("malloc failure\n");
            return false;
        }
        T->data=ch;//生成根节点
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

二叉树的递归遍历：

先根/后根遍历又称为树的深度遍历

前序

即先根遍历，根左右

//二叉树的前序遍历
void PreOrder(BiTree T,int level){
    if(T!=NULL){
        visit(T,level);//访问根节点
        PreOrder(T->lchild,level+1);//递归遍历左子树
        PreOrder(T->rchild,level+1);//递归遍历右子树
    }
}
1
2
3
4
5
6
7
8

中序

中根遍历，左根右

//二叉树的中序遍历序列
void InOrder(BiTree T,int level){
    if(T!=NULL){
        InOrder(T->lchild,level+1);//递归遍历左子树
        visit(T,level);//访问根节点
        InOrder(T->rchild,level+1);//递归遍历右子树
    }
}
1
2
3
4
5
6
7
8

后序

后根遍历，左右根

//二叉树的后续遍历
void PostOrder(BiTree T,int level){
    if(T!=NULL){
        PostOrder(T->lchild,level+1);//递归遍历左子树
        PostOrder(T->rchild,level+1);//递归遍历右子树
        visit(T,level);
    }
}
1
2
3
4
5
6
7
8

后序递归遍历的应用：求树的深度

//后序递归遍历的应用:求树的深度   后序遍历的变种
int TreeDepth(BiTree T){
    if(!T){
        return 0;
    }
    else{
        int left = TreeDepth(T->lchild);
        int right = TreeDepth(T->rchild);
         //树的深度=Max(左子树深度，右子树深度)+1
        return left>right?left+1:right+1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

二叉树的销毁(使用后序遍历)

销毁一棵二叉树和遍历操作类似，即遍历一个结点释放
如果采用先序遍历或中序遍历，销毁根节点后就找不到左右孩子了，
在销毁的时候需要保存左右孩子的地址。
所以在销毁的时候要保存左右孩子的地址
这里采用后序遍历销毁一棵二叉树，按照左孩子，右孩子，根节点
的顺序销毁。注意：根节点将根节点指向空，防止成为野指针

bool DestroyBiTree(BiTree T){//@@@
    if(T == NULL){
        printf("空结点#\n");
        return false;
    }
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    printf("销毁%c\n",T->data);
    free(T);//@@@
    T=NULL;//防止产生野指针
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12

完整测试代码

#include<stdio.h>
#include<stdlib.h>
#define ElemType char
typedef struct BiTNode{
    ElemType data;
    struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

void visit(BiTree T,int level){
    printf("%c 位于第 %d 层\n",T->data,level);
}

//二叉树的前序遍历
void PreOrder(BiTree T,int level){
    if(T!=NULL){
        visit(T,level);//访问根节点
        PreOrder(T->lchild,level+1);//递归遍历左子树
        PreOrder(T->rchild,level+1);//递归遍历右子树
    }
}

//二叉树的中序遍历序列
void InOrder(BiTree T,int level){
    if(T!=NULL){
        InOrder(T->lchild,level+1);//递归遍历左子树
        visit(T,level);//访问根节点
        InOrder(T->rchild,level+1);//递归遍历右子树
    }
}

//二叉树的后续遍历
void PostOrder(BiTree T,int level){
    if(T!=NULL){
        PostOrder(T->lchild,level+1);//递归遍历左子树
        PostOrder(T->rchild,level+1);//递归遍历右子树
        visit(T,level);
    }
}


//后序递归遍历的应用:求树的深度   后序遍历的变种
int TreeDepth(BiTree T){
    if(!T){
        return 0;
    }
    else{
        int left = TreeDepth(T->lchild);
        int right = TreeDepth(T->rchild);
         //树的深度=Max(左子树深度，右子树深度)+1
        return left>right?left+1:right+1;
    }
}


//按前序输入二叉树中节点的值(一个字符)
// '#'表示空树， 构造二叉链表表示二叉树T
bool CreateBiTree(BiTree &T){
    ElemType ch;

    scanf("%c",&ch);//@@@
    if(ch == '#'){
        //printf("您要创建一棵空树吗？\n");
        T=NULL;//
        return false;
    }
    else{
        T=(BiTree)malloc(sizeof(BiTNode));
        if(!T){
            printf("malloc failure\n");
            return false;
        }
        T->data=ch;//生成根节点
        CreateBiTree(T->lchild);//构造左子树
        CreateBiTree(T->rchild);//构造右子树
        return true;
    }
}


//销毁一棵二叉树和遍历操作类似，即遍历一个结点释放
/*如果采用先序遍历或中序遍历，销毁根节点后就找不到左右孩子了，
在销毁的时候需要保存左右孩子的地址。
所以在销毁的时候要保存左右孩子的地址

这里采用后序遍历销毁一棵二叉树，按照左孩子，右孩子，根节点
的顺序销毁。注意：根节点将根节点指向空，防止成为野指针
*/


bool DestroyBiTree(BiTree T){//@@@
    if(T == NULL){
        printf("空结点#\n");
        return false;
    }
    DestroyBiTree(T->lchild);
    DestroyBiTree(T->rchild);
    printf("销毁%c\n",T->data);
    free(T);//@@@
    T=NULL;//防止产生野指针
    return true;
}



int main(){
    int level=1;
    BiTree T=NULL;//@@@
    printf("按前序输入二叉树中节点的值(输入#表示空节点)\n");
    CreateBiTree(T);
    printf("中序遍历结果为：\n");
    InOrder(T,level);
    printf("\n后序遍历结果为: \n");
    PostOrder(T,level);

    printf("\n求树的深度为：");
    int depth=TreeDepth(T);
    printf("%d\n",depth);

    printf("\n\n销毁开始(按后序遍历来销毁):\n\n");
    DestroyBiTree(T);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122

输入样例

在输入窗口输入： AB#D##C##

测试结果