5.C_数据结构_树
概述
树的逻辑结构：
树中任何节点都可以有0个或多个直接后继节点，但最多只有一个直接前驱节点。根节点没有直接前驱节点，叶节点没有直接后继节点。
相关名词：
- 空树：树中没有节点
- 节点的度数：一个节点的子树的个数
- 树的度数：该树中节点的最大度数
- 树叶、终端节点：度数为0的节点
- 分支节点：度数不为0的节点
- 内部节点：除根节点以外的分支节点
- 路径：能够找到节点的方式，例如：A到L的路径是ABEL
- 路径的长度：路径中的边数，边有A-B、B-E、E-L，即：长度为3
- 节点的层数：节点的层数 = 父节点的层数+1，根节点的层数为1
- 树的高度、深度：树中节点层数的最大值。例如：下图中深度为4
- 祖先：路径中前面的节点为后面的祖先，例如：A是K的祖先
- 子孙：路径中后面的节点为前面的子孙
- 堂兄弟：层级一样但父节点不一样的节点为堂兄弟，例如：F、G
- 兄弟：层级一样，父节点也一样的节点为兄弟，例如：E、F
- 有序树：兄弟之间是有序的、不能交换位置的树
- 森林：m棵互不相交的树，树去掉根节点就是森林，森林加上根节点就是树
二叉树：
二叉树是树的度数为2的有序树，即：一个父节点最多有2个子节点，且这两个节点是有顺序的。除此之外，子节点也没有指向父节点的指针。
- 二叉树第 i 层上的节点最多有：2^(i-1)个。
- 对于深度为k的二叉树，节点最多有：2^0 + 2^1 + ... + 2^(k-1) = 2^k -1 个
- 满二叉树：深度为k时，有2^k-1个节点的二叉树，即每一层都是满的。
- 完全二叉树：只有最下面两层有度数小于2的节点，且最下面的叶节点集中在最左边的位置上
- 有n个节点的完全二叉树的深度为：log2n + 1 或 log2(n+1)
二叉树顺序存储：
编号方法是从上到下，从左到右进行编号，规定根节点的编号为1。这种方法只适用于完全二叉树，如果是不完全二叉树需要添加虚节点构成完全二叉树，这会大大增加冗余的内存使用。
假设总共有 n 个节点，当前节点的编号为 i 。则有以下结论：
- 当编号 i ≠ 1时，有父节点，父节点的编号为 i/2
- 当 2*i < n 时，代表有左孩子。当 2*i+1 < n 时，代表有右孩子。
- 当 i 为奇数且不为1时，一定有左兄弟。当 i 为偶数且 i < n 时，一定有右兄弟
顺序存储的特点：
- 二叉树的顺序存储是用数组的方式进行存储，它的空间连续。
- 只有当二叉树为完全二叉树时，顺序存储才不会有空间浪费，否则需要先添加虚节点构成完全二叉树，再进行顺序存储。
二叉树链式存储：
由下一章详细讲解。
二叉树链式存储
1、基本内容
二叉树的链式存储是以链表的形式存储每一个节点。每一个节点都可以看成一个根，在这个根中存放了一些数据data，并且这个根中有两个树叶，即：左孩子和右孩子。具体的节点结构如下：
二叉树结点结构体声明如下：
typedef char tree_data_t;
typedef struct tree{
tree_data_t data; //root中存放的数据
struct tree* left; //左孩子
struct tree* right; //右孩子
}bitree;二叉树代码的文件构成：
- bitree.h：数据结构的定义、运算函数接口
- bitree.c：运算函数接口的实现
- linkqueue.c：分层遍历二叉树会用到队列
- test.c：使用数据结构实现的应用功能代码
2、二叉树遍历代码实现
2.1 先序、中序、后序
二叉树的遍历方法：
- 先序遍历：先访问树根，再访问左子树，最后访问右子树
- 中序遍历：先访问左子树，再访问树根，最后访问右子树
- 后序遍历：先访问左子树，再访问右子树，最后访问树根
可以看到这是一个递归问题，以后序遍历为例，每一个结点都是先访问左子树，再访问右子树，最后访问树根。例如下图，从A出发，先访左子树，左子树为B。之后再访问B的左子树，为空；之后访问B的右子树，为C；之后访问C的左子树为D；之后访问D的左子树，为空；之后访问D的右子树，为空；之后访问D的根，为D。这时才访问到第一个结点D。可以看到当结点为A时，是先访问左子树，访问到后，就开始第二次重复的操作。对B结点同样是先访问左子树。这个就是递归。
先序遍历代码编写思路：
从上述分析可以看出，对于二叉树的遍历，我们只需要专注与一个结点该如何遍历，之后所有结点遍历的方式都是一样的。
递归函数的前提是有一个退出条件，当我们发现需要继续往下遍历的结点为空时，这就不再需要遍历，最终递归退出。
具体代码实现如下：
/*
* preorder:先序遍历
* param root:根指针
* */
void preorder(bitree* root){
//停止条件:当根节点为空时,不再访问
if(root == NULL){
return;
}
printf("%c",root->data);//访问根
preorder(root->left); //左结点以同样的方式访问
preorder(root->right); //右结点以同样的方式访问
}
中序遍历与后续遍历代码：
中序遍历与后续遍历的思路与先序遍历完全一致，都是先规定好递归退出条件，之后递归的处理每一个结点。
具体代码实现如下：
/*
* inorder:中序遍历
* param root:根指针
* */
void inorder(bitree* root){
//停止条件:当根节点为空时,不再访问
if(root == NULL){
return;
}
inorder(root->left); //左
printf("%c",root->data);//根
inorder(root->right); //右
}
/*
* postorder:后序遍历
* param root:根指针
* */
void postorder(bitree* root){
//停止条件:当根节点为空时,不再访问
if(root == NULL){
return;
}
postorder(root->left); //左
postorder(root->right); //右
printf("%c",root->data); //根
}
2.2 层次遍历
二叉树的层次遍历需要用到队列。我们首先从队列中取出一个结点，这就代表访问了这个结点；之后将这个结点左右孩子非空，哪就入队列。之后循环操作，继续取出一个结点，继续将结点的左右孩子入队列。
具体代码实现如下：
/*
* layorder:层级遍历
* param root:根指针
* */
void layerorder(bitree* root){
bitree* tmp = NULL;
linkqueue* pQueue = NULL;
if(root == NULL){
return;
}
//1.建立队列
pQueue = queue_create();
if(pQueue == NULL){
return;
}
//2.初始化队列,将根入队
enter_queue(pQueue,root);
//3.开始层级遍历
while(out_queue(pQueue,&tmp) != -1){
if(tmp!=NULL){
printf("%c",tmp->data);
enter_queue(pQueue,tmp->left);
enter_queue(pQueue,tmp->right);
}
}
puts("");
}3、二叉树创建代码实现
二叉树的创建代码，就是按照遍历的逻辑依次写入数据，比如写入的数据为char型，那就需要规定一个停止向下遍历的字符，以下代码中规定字符为' # '
具体代码实现如下：
/*
* bitree_creat:一次性创建出一个树
* @ret 根的指针
* */
bitree* bitree_create(void){
char data = '#';
bitree* root = NULL;
//停止条件:规定data=#时代表结点不存在
scanf("%c",&data);
if(data == '#'){
return NULL;
}
//结点存在，申请根结点空间
root = (bitree*)malloc(sizeof(bitree));
if(root == NULL){
printf("malloc err\n");
return NULL;
}
root->data = data;
//初始化左右孩子
root->left = bitree_create();
root->right = bitree_create();
return root;
}
原文地址：https://blog.csdn.net/Fresh_man111/article/details/142284186
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！