概述

树的逻辑结构：

树中任何节点都可以有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;
}