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

文章目录

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.运行结果

在这里插入图片描述

相关阅读:
⑰霍兰德EI*如何选选专业？高考志愿填报选专业
 RS485收发自动切换电路 [原创www.cnblogs.com/helesheng]
监控与运维，主流it运维监控工具
 Vue路由&nodejs环境搭建
 Wakelocks 框架设计与实现
 pikachu---暴力破解（burpsuite）
Docker学习-Docker底层原理和常用命令
 【PyTorchVideo教程02】快速安装PyTorchVideo 采用 yolov5、slowfast、deepsort对学生课堂行为进行检测
 前端必备：Node.js是什么？它有哪些特点和优势？
2022年最新西藏建筑八大员（机械员）模拟考试题库及答案
原文地址：https://blog.csdn.net/treesorshining/article/details/125905714