【数据结构】【王道】【树与二叉树】二叉树的实现及基本操作（可直接运行）

文章目录

1.基本操作
2.完整代码
3.运行结果

各部分的解释已经以注释形式写于代码中。

1.基本操作

1.1 结构体构造

typedef struct BiTNode {
    // 数据域
    char data;
    // 左、右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
1
2
3
4
5
6

1.2 初始化

// 初始化
void InitTree(BiTree &T) {
    // 初始化可将根节点置空，空树
    T = NULL;
    // 插入根节点
    // 分配空间
    T = (BiTree)malloc(sizeof(BiTree));
    // 赋值
    T->data = 'A';
    // 初始无左右子树
    T->lchild = NULL;
    T->rchild = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.3 左插入结点

// 左插入结点
bool InsertLeftTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->lchild = p;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.4 右插入节点

// 右插入结点
bool InsertRightTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->rchild = p;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1.5 访问结点

// 访问结点
void visit(BiTree T) {
    printf("%c   ", T->data);
}
1
2
3
4

1.6 先序遍历（递归）

// 先序遍历
// 即根左右，先访问根结点，再依次访问左右结点
void PreOrder(BiTree T) {
    // 根节点为空则直接跳过
    if(T != NULL) {
        // 访问根结点
        visit(T);
        // 递归访问左子树
        PreOrder(T->lchild);
        // 地柜访问右子树
        PreOrder(T->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.7 中序遍历（递归）

// 中序遍历
// 即左根右，先访问左结点，再访问根结点，最后访问右结点
void InOrder(BiTree T) {
    if(T != NULL) {
        // 递归遍历左子树
        InOrder(T->lchild);
        // 访问根结点
        visit(T);
        // 递归遍历右子树
        InOrder(T->rchild);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.8 后序遍历（递归）

// 后序遍历
// 即左右根，先依次访问左右结点，最后访问根结点
void PostOrder(BiTree T) {
    if(T != NULL) {
        // 递归遍历左子树
        PostOrder(T->lchild);
        // 递归遍历右子树
        PostOrder(T->rchild);
        // 访问根结点
        visit(T);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

1.9 树的深度

// 树的深度
int treeDepth(BiTree T) {
    // 根结点为空，则深度为0
    if(T == NULL) {
        return 0;
    } else {
        // 递归遍历左子树，获得左子树深度
        int l = treeDepth(T->lchild);
        // 递归遍历右子树，获得右子树深度
        int r = treeDepth(T->rchild);
        // 树的深度=Max{左子树深度，右子树深度} + 1
        // 加1相当于访问根节点，包括根结点深度+1
        return l > r ? l + 1 : r + 1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

2.完整代码

#include
#include

typedef struct BiTNode {
    // 数据域
    char data;
    // 左、右孩子指针
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

// 初始化
void InitTree(BiTree &T) {
    // 初始化可将根节点置空，空树
    T = NULL;
    // 插入根节点
    // 分配空间
    T = (BiTree)malloc(sizeof(BiTree));
    // 赋值
    T->data = 'A';
    // 初始无左右子树
    T->lchild = NULL;
    T->rchild = NULL;
}

// 左插入结点
bool InsertLeftTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->lchild = p;
    return true;
}

// 右插入结点
bool InsertRightTreeNode(BiTNode* &T, char x) {
    // 分配空间
    BiTNode *p = (BiTNode*)malloc(sizeof(BiTNode));
    // 分配空间失败的情况
    if(p == NULL) {
        return false;
    }
    // 数据域赋值
    p->data = x;
    // 初始插入，无左右孩子，置空
    p->lchild = NULL;
    p->rchild = NULL;
    // 作为指定插入结点的左孩子
    T->rchild = p;
    return true;
}

// 访问结点
void visit(BiTree T) {
    printf("%c   ", T->data);
}

// 先序遍历
// 即根左右，先访问根结点，再依次访问左右结点
void PreOrder(BiTree T) {
    // 根节点为空则直接跳过
    if(T != NULL) {
        // 访问根结点
        visit(T);
        // 递归访问左子树
        PreOrder(T->lchild);
        // 地柜访问右子树
        PreOrder(T->rchild);
    }
}

// 中序遍历
// 即左根右，先访问左结点，再访问根结点，最后访问右结点
void InOrder(BiTree T) {
    if(T != NULL) {
        // 递归遍历左子树
        InOrder(T->lchild);
        // 访问根结点
        visit(T);
        // 递归遍历右子树
        InOrder(T->rchild);
    }
}

// 后序遍历
// 即左右根，先依次访问左右结点，最后访问根结点
void PostOrder(BiTree T) {
    if(T != NULL) {
        // 递归遍历左子树
        PostOrder(T->lchild);
        // 递归遍历右子树
        PostOrder(T->rchild);
        // 访问根结点
        visit(T);
    }
}

// 树的深度
int treeDepth(BiTree T) {
    // 根结点为空，则深度为0
    if(T == NULL) {
        return 0;
    } else {
        // 递归遍历左子树，获得左子树深度
        int l = treeDepth(T->lchild);
        // 递归遍历右子树，获得右子树深度
        int r = treeDepth(T->rchild);
        // 树的深度=Max{左子树深度，右子树深度} + 1
        // 加1相当于访问根节点，包括根结点深度+1
        return l > r ? l + 1 : r + 1;
    }
}


int main() {
    BiTree T;
    InitTree(T);
    InsertLeftTreeNode(T, 'B');
    InsertRightTreeNode(T, 'C');
    InsertLeftTreeNode(T->lchild, 'D');
    InsertRightTreeNode(T->lchild, 'E');
    InsertLeftTreeNode(T->rchild, 'F');
    InsertRightTreeNode(T->rchild, 'G');
    printf("PreOrder\n");
    PreOrder(T);
    printf("\nInOrder\n");
    InOrder(T);
    printf("\nPostOrder\n");
    PostOrder(T);
    printf("\ntreeDepth:%d\n", treeDepth(T));
}
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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139

3.运行结果

在这里插入图片描述

相关阅读:
提高尼日利亚稻米产量丰收节贸促会：国稻种芯百团计划行动
 vsftp配置多用户
 【C语言】算法学习·回溯算法
 Qt：信号与槽机制
 正则验证用户名和跨域postmessage
解决OpenSSL加入到在Visual Studio 2019中编译返回LNK2019错误
 五表联筛：从五个表格中筛选出出现过两次及两次以上的人名
 基于JavaFX图形界面演示的迷宫创建与路径寻找
 pnpm 是凭什么对 npm 和 yarn 降维打击的
 互联网通信的核心协议HTTP和HTTPS
原文地址：https://blog.csdn.net/treesorshining/article/details/125905714