二叉树的创建、遍历、广义表转换
1树的定义及相关术语
1.1 树的定义
- 树是一种非线性的数据结构，由n(n>=0)个结点组成的有限集合；
- 如果n=0，称为空树；
- 如果n>0，则：
- 有一个特定的结点被称之为根结点(root)，根结点只有直接后继，没有前驱；
- 除根结点外的其他结点划分为m(m>=0)个互不相交的有限集合T0,T1...Tm-1，每一个集合又是一颗子树，并称之为根的子树。
- 每个结点有零个或多个子结点；
- 没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；
- 节点的数量等于边数加一；树由n 个节点 和 (n-1)条边 构成，其中n ≥ 1；
- 树或栈这种数据结构用于解决** 具有完全包含关系的问题**；
- 问题抽象（思维逻辑）：本质上是把一个大问题分成若干个小问题，当小问题解决了，大问题自然也解决了；首先，将树中的“节点”看作“集合”，“边”看作“关系”，接着把“全集”看成是一个大问题，而“子集”看作是若干个小问题，我们只需要关注小问题的求解即可。
文章图片
1.3 树的相关术语
- 节点深度：对任意节点x，x节点的深度表示为根节点到x节点的路径长度。所以根节点深度为0，第二层节点深度为1，以此类推；
- 节点高度：对任意节点x，叶子节点到x节点的路径长度就是节点x的高度；
- 树的深度（高度）：一棵树中节点的最大深度就是树的深度，也称为树的高度；
- 度：节点的子树数目就是节点的度；
- 叶子节点 vs 分支节点：度为零的节点就是叶子节点（路径中的最后一个节点）；度不为零的节点就是分支节点；
- 父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
- 子节点：一个节点含有的子树的根节点称为该节点的子节点；
- 兄弟节点：拥有共同父节点的节点互称为兄弟节点；
- 节点的层次：从根节点开始，根节点为第一层，根的子节点为第二层，以此类推；
- 祖先：对任意节点x，从根节点到节点x的所有节点都是x的祖先（节点x也是自己的祖先）
- 后代：对任意节点x，从节点x到叶子节点的所有节点都是x的后代（节点x也是自己的后代）
- 森林：m颗互不相交的树构成的集合就是森林
- n叉树：由一个节点向外最多引出节点的数量，即当前这个节点最多向外有n个指向；
- 补充：度分为“入度”和“出度”；
- 出度：由一个节点向外指向边的数量；
- 入度：有多少条边指向一个节点的数量；树的入度为1，所以只考虑出度，即为度；
- 案例：
- 树的深度（高度）：4，path = 1→4→6→8
- 节点4的深度：2，path = 1→4；节点4的高度：3，path = 8→6→4
- 节点2的度：1, =(5, )；节点4的度：2，=(6, 7)；叶子节点的度：0
文章图片
2 二叉树 2.1 定义
- 在一个树中，由一个节点向外最多引出2个节点，即当前这个节点最多向外有2个指向；
如何定义n叉树，n是多少的问题？
- 对于n叉树中的n是一个不确定性的问题，一般计算机只能处理确定性问题，所以，我们可以将n 叉树转换为2叉树来思考；
- 由于计算机底层是基于二进制计算的，故2 叉树 与 n叉树之间可以相互转换；
- 表示方法：左孩子右兄弟表示法，又名十字链表法
文章图片
2.3 特点
- 每个节点的度最多为2；
- 度为0的节点比度为2的节点多1个；
- 证明：参考公式 —> 节点的数量等于边数加一
- xi：表示度为i的节点数，其中i 为 0，1，2。总共的节点数 = x2 + x1 + x0，度为2提供的边数：2x2， 度为1提供的边数：x1，度为0提供的边数：0；所以 节点数 = 边数 + 1==> x2 + x1 + x0 = 2x2 + x1 + 1 ==> x0 = x2 + 1
- 二叉树的遍历是指从二叉树的根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点仅被访问一次。
- 二叉树的访问次序：前序遍历、中序遍历、后序遍历
文章图片
- 前序遍历：1→2→4→5→3→6
- 中序遍历：4→2→5→1→3→6
- 后序遍历：4→5→2→6→3→1
- 中国版
文章图片
- 国际版
文章图片
- 完美二叉树：叶子节点都在同一层并且除叶子节点外的所有节点都有两个子节点；
- 完全二叉树（重点）：对于一颗二叉树，假设其深度为d（d>1）。除第d层外的所有节点构成完美二叉树，且第d层所有节点从左向右连续地紧密排列，这样的二叉树被称为完全二叉树；
- 完全二叉树的优势：从根节点到叶子节点中的每一个节点进行一个顺序（连续）标号；
- 完全二叉树的特点：
- 编号为i的子节点：左孩子编号为2i，右孩子编号为2i+1，注：i ≥ 1;
- 若 i 从0 开始标记，则左孩子编号为2i + 1，右孩子编号为2i+2，无意中多了一次加法运算；（不建议）
- 可以用连续空间存储（数组）；
- 完全二叉树实现方式：顺序表 和 链表
【二叉树的创建、遍历、广义表转换】可以使用广义表来表示一颗二叉树
文章图片
文章图片
2.7 二叉排序树
- 本质：基于二叉树这种结构，定义了一种性质，并且在不断维护这种性质的一种新结构。
- 性质：一颗二叉树中的任何三元组都满足 B(左孩子) < A(根节点) < C (右孩子)的这种关系。故中序遍历即可实现排序操作。
- 补充：数据结构的本质：定义一种性质，并且维护这种性质的一种结构
- 通过“栈”这种数据结构实现广义表转二叉树；
#include
#include
#include typedef struct Node {
int data;
struct Node *lchild, *rchild;
} Node;
typedef struct Tree {
Node *root;
int length;
// 记录二叉树的节点个数
} Tree;
Node *getNewNode(int val);
Tree *getNewTree();
Node *insert_node(Node *, int, int *);
void insert(Tree *, int);
void pre_order_node(Node *);
void pre_order(Tree *);
void in_order_node(Node *);
void in_order(Tree *);
void post_order_node(Node *);
void post_order(Tree *);
void clear_node(Node *);
void clear(Tree *);
void output_node(Node *);
void output(Tree *);
int main() {
srand(time(0));
Tree *tree = getNewTree();
#define MAX_OP 10
for (int i = 0;
i < MAX_OP;
i++) {
int val = rand() % 100;
insert(tree, val);
output(tree);
}
#undef MAX_OP
pre_order(tree);
in_order(tree);
post_order(tree);
clear(tree);
return 0;
}Node *getNewNode(int val) {
Node *p = (Node *)malloc(sizeof(Node));
p->data = https://www.it610.com/article/val;
p->lchild = p->rchild = NULL;
return p;
}Tree *getNewTree() {
Tree *t = (Tree *)malloc(sizeof(Tree));
t->root = NULL;
t->length = 0;
return t;
}// ?叉排序树插入操作
// 性质：一颗二叉树中的任何三元组都满足 B(左孩子) < A(根节点) < C (右孩子)的这种关系，故中序遍历可实现排序
// 插入过程（尾插法）：从根节点开始，找到待插入位置前的叶子节点（向下寻找），然后返回各个节点地址（向上回溯）
Node *insert_node(Node *root, int val, int *flag) {
if (root == NULL) {
*flag = 1;
return getNewNode(val);
}
if (root->data =https://www.it610.com/article/= val) return root;
// ?叉排序树的性质：任何三元组都满足 B(左孩子) < A(根节点) < C (右孩子)
if (root->data > val) root->lchild = insert_node(root->lchild, val, flag);
else root->rchild = insert_node(root->rchild, val, flag);
return root;
}void insert(Tree *t, int val) {
if (t == NULL) return ;
int flag = 0;
// 传出参数，标记当前插入节点是否成功，成功:1，失败:0
t->root = insert_node(t->root, val, &flag);
t->length += flag;
return ;
}// 前序：根->左->右
void pre_order_node(Node *root) {
if (root == NULL) return ;
printf("%d ", root->data);
pre_order_node(root->lchild);
pre_order_node(root->rchild);
return ;
}void pre_order(Tree *t) {
if (t == NULL) return ;
printf("pre_order : ");
pre_order_node(t->root);
printf("\n");
return ;
}// 中序：左->根->右
void in_order_node(Node *root) {
if (root == NULL) return ;
in_order_node(root->lchild);
printf("%d ", root->data);
in_order_node(root->rchild);
return ;
}void in_order(Tree *t) {
if (t == NULL) return ;
printf("in_order : ");
in_order_node(t->root);
printf("\n");
return ;
}// 后序：左->右->根
void post_order_node(Node *root) {
if (root == NULL) return ;
post_order_node(root->lchild);
post_order_node(root->rchild);
printf("%d ", root->data);
return ;
}void post_order(Tree *t) {
if (t == NULL) return ;
printf("post_order : ");
post_order_node(t->root);
printf("\n");
return ;
}// 从叶子节点开始删除
void clear_node(Node *node) {
if (node == NULL) return ;
clear_node(node->lchild);
clear_node(node->rchild);
free(node);
return ;
}void clear(Tree *t) {
if (t == NULL) return ;
clear_node(t->root);
}// 相当于前序遍历
void output_node(Node *root) {
if (root == NULL) return ;
printf("%d", root->data);
if (root->lchild == NULL && root->rchild == NULL) return ;
// 若是叶子节点，则结束
printf("(");
output_node(root->lchild);
printf(",");
output_node(root->rchild);
printf(")");
return ;
}void output(Tree *t) {
if (t == NULL) return ;
printf("tree(%d) : ", t->length);
output_node(t->root);
printf("\n");
}
// tree(1) : 6
// tree(2) : 6(,28)
// tree(3) : 6(,28(9,))
// tree(4) : 6(,28(9,87))
// tree(5) : 6(,28(9,87(61,)))
// tree(6) : 6(,28(9,87(61(34,),)))
// tree(7) : 6(,28(9,87(61(34(,40),),)))
// tree(8) : 6(,28(9,87(61(34(,40),65),)))
// tree(9) : 6(,28(9(,20),87(61(34(,40),65),)))
// tree(9) : 6(,28(9(,20),87(61(34(,40),65),)))
// pre_order : 6 28 9 20 87 61 34 40 65
// in_order : 6 9 20 28 34 40 61 65 87
// post_order : 20 9 40 34 65 61 87 28 6
3.2 广义表转二叉树
#include
#include
#include //?叉树的结构定义
typedef struct Node {
char data;
struct Node *lchild, *rchild;
} Node;
typedef struct Tree {
Node *root;
int length;
} Tree;
//栈的结构定义（存储?叉树节点地址）
typedef struct Stack {
Node **data;
// 定义二级指针的原因：使用数组来存放每个节点的地址，即数组的每个元素都是 Node*
int top, size;
// top: 标记栈顶位置，默认为-1；size: 当前栈空间的大小
} Stack;
Node *getNewNode(char);
// 节点的初始化
Tree *getNewTree();
// ?叉树的初始化
void clear_node(Node *);
// 销毁?叉树的节点
void clear_tree(Tree *);
// 销毁?叉树
Stack *init_stack(int);
// 栈的初始化
void clear_stack(Stack *);
// 栈的销毁
Node *top(Stack *);
// 输出栈顶元素
int empty(Stack *);
// 栈的判空
int push(Stack *, Node *);
// 压栈操作
int pop(Stack *);
// 弹栈操作
void pre_order_node(Node *);
void pre_order(Tree *);
// 前序遍历
void in_order_node(Node *);
void in_order(Tree *);
// 中序遍历
void post_order_node(Node *);
void post_order(Tree *);
// 后序遍历
Node *build(const char *, int *);
// 构建一颗二叉树int main() {
char str[1000] = { 0 };
int node_num = 0;
scanf("%[^\n]s", str);
getchar();
Tree *tree = getNewTree();
tree->root = build(str, &node_num);
tree->length = node_num;
pre_order(tree);
in_order(tree);
post_order(tree);
clear_tree(tree);
return 0;
}Node *getNewNode(char val) {
Node *p = (Node *)malloc(sizeof(Node));
p->lchild = p->rchild = NULL;
p->data = https://www.it610.com/article/val;
return p;
}Tree *getNewTree() {
Tree *t = (Tree *)malloc(sizeof(Tree));
t->root = NULL;
t->length = 0;
return t;
}void clear_node(Node *root) {
if (root == NULL) return;
clear_node(root->lchild);
clear_node(root->rchild);
free(root);
return;
}void clear_tree(Tree *t) {
if (t == NULL) return;
clear_node(t->root);
free(t);
return;
}Stack *init_stack(int n) {
Stack *s = (Stack *)malloc(sizeof(Stack));
s->data = https://www.it610.com/article/(Node **)malloc(sizeof(Node *) * n);
s->top = -1;
s->size = n;
return s;
}void clear_stack(Stack *s) {
if (s == NULL) return;
free(s->data);
free(s);
return;
}Node *top(Stack *s) {
return s->data[s->top];
}int empty(Stack *s) {
return s->top == -1;
}int push(Stack *s, Node *val) {
if (s == NULL) return 0;
if (s->top == s->size - 1) return 0;
s->data[++(s->top)] = val;
return 1;
}int pop(Stack *s) {
if (s == NULL) return 0;
if (empty(s)) return 0;
s->top -= 1;
return 1;
}// 二叉树的广义表表示：str = "A(B(, D), C(E))"
// '(': 根节点入栈，设置flag=0;
')': 出栈;
',': 设置flag=1;
// flag=0: 表示是左子节点, flag=1: 表示是右子节点
// 将广义表转化为二叉树
// 前序|后续遍历 && 中序遍历 ==> 二叉树
// 本方法：栈实现广义表转二叉树
// 方法2：系统栈（递归）实现广义表转二叉树
Node *build(const char *str, int *node_num) {
Stack *s = init_stack(strlen(str));
int flag = 0;
Node *temp = NULL, *p = NULL;
// temp：指向每层的父节点，p：指向根节点
while (str[0]) {
switch (str[0]) {
case '(':
push(s, temp);
flag = 0;
break;
case ')':
p = top(s);
pop(s);
break;
case ',': flag = 1;
break;
case ' ': break;
default:
temp = getNewNode(str[0]);
if (!empty(s) && flag == 0) {
top(s)->lchild = temp;
}
else if (!empty(s) && flag == 1) {
top(s)->rchild = temp;
}
++(*node_num);
break;
}
++str;
}
clear_stack(s);
if (temp && p == NULL) p = temp;
// 只有根节点的情况
return p;
}void in_order_node(Node *root) {
if (root == NULL) return;
in_order_node(root->lchild);
printf("%c ", root->data);
in_order_node(root->rchild);
return;
}void in_order(Tree *tree) {
if (tree == NULL) return;
printf("in_order(%d) : ", tree->length);
in_order_node(tree->root);
printf("\n");
return;
}void pre_order_node(Node *root) {
if (root == NULL) return;
printf("%c ", root->data);
pre_order_node(root->lchild);
pre_order_node(root->rchild);
return;
}void pre_order(Tree *tree) {
if (tree == NULL) return;
printf("pre_order(%d) : ", tree->length);
pre_order_node(tree->root);
printf("\n");
return;
}void post_order_node(Node *root) {
if (root == NULL) return;
post_order_node(root->lchild);
post_order_node(root->rchild);
printf("%c ", root->data);
return;
}void post_order(Tree *tree) {
if (tree == NULL) return;
printf("post_order(%d) : ", tree->length);
post_order_node(tree->root);
printf("\n");
return;
}推荐阅读
- HTML文件怎么写（简述构成HTML文件的几大元素）
- LeetCode编程题解法汇总|力扣解法汇总2045-到达目的地的第二短时间
- Java版顺序存储二叉树
- gateway|网关: springcloud-gateway 组件的使用
- 服务器|token的作用
- 和事故斗智斗勇的这些天|“不能初始化photoshop,因为暂存盘已满“问题的解决
- java|while循环示例（输出一批整数中的最大值和最小值）
- 怎么减少行锁对性能的影响（）
- 掌握这些招数，你也能写出HR眼中的高分简历
- 体验了一把当架构师的感觉