目录
一、相关概念
1.概念
- 线性结构：描述数据一对一的关系
- 非线性结构：描述数据一对多（树）、多对多（图）的关系【本章只学习树，大家学有余力的情况下自行学习图】
2.树形结构相关概念
- 节点：在树型结构中，组成树形结构的一个小单元被称为节点
节点的分类：
- 根节点：只有后继，没有前驱的节点【整个树型结构中只有一个根节点】
- 分支节点：既有前驱，又有后继的节点
- 叶子节点：只有前驱，没有后继的节点
上图中蓝色圈圈就被称为节点
- 前驱（祖先）：有哪个节点可以访问到该节点
- 后继（子孙）：有那个节点可以访问到后续的节点
- 层：根节点层数为1，后续每引申出一个节点就在该节点的层数+1
- 树的层数：树的层数由层数最高的节点对应的层数表示树的层数
- 高度：节点高度是由该节点到最远的叶子节点的距离表示该节点高度（该节点本身也要算进去）
- 深度：节点深度是由该节点到根节点的距离表示该节点深度（该节点本身也要算进去）
- 树的高度 == 树的深度 == 树的层数
- 度：后继节点的个数（在二叉树结构中基本都为初度）
二、二叉树（左0右1）
1.定义
树形结构中的所有节点度数最大为2，这样的树形结构被称为二叉树
2.二叉树节点状态
- 叶子节点（度数为0）
- 只有左孩子（度数为1）
- 只有右孩子（度数为1）
- 左右孩子都有（度数为2）
三、满二叉树和完全二叉树
1.满二叉树
1.概念
- 所有的叶子节点均在同一层且每层节点个数均为最大值（所有的除叶子节点的分支节点度数为2，除叶子节点外的每个分支节点都拥有左孩子和右孩子）
2.满二叉树的特性
- 满二叉树第k层节点2的k-1次方个【2^(k-1)】
- 满二叉树前k层有2的k次方-1个节点【(2^k)-1】
2.完全二叉树
1.概念
- 二叉树的编号展开后是连续的，称为完全二叉树
- 编号：如果节点编号为N,则左孩子编号为2N,右孩子编号为2N+1
2.完全二叉树的遍历形式
- 深度优先遍历（DFS）
- 前序遍历（先序遍历）：根节点——左孩子——右孩子
- 中序遍历：左——根——右
- 后序遍历：左——右——跟
以该图为例：
- 前序遍历（先序遍历）：【根左右】1-2-4-8-9-5-10-11-3-6-12-7
- 中序遍历：【左根右】8-4-9-2-10-5-11-1-12-6-3-7
- 后序遍历：【左右跟】8-9-4-10-11-5-2-12-6-7-3-1
- 广度优先遍历（BFS）
层序遍历：逐层从左到右依次遍历
以上图为例：
层序遍历：1-2-3-4-5-6-7-8-9-10-11-12
四、二叉树的相关操作及代码实现
1.节点的定义
2.创建完全二叉树
通过函数递归完成完全二叉树的创建
- 申请节点空间
- 存放数据编号
- 如果存在左子树递归创建左子树
- 如果存在右子树递归创建右子树
3.二叉树深度优先遍历
- 前序遍历（利用递归实现）
- 中序遍历（利用递归实现）
- 后序遍历（利用递归实现）
4.二叉树的广度优先遍历
层序遍历（利用队列实现）
利用队列实现原理图
5.二叉树的销毁
选用后序遍历进行销毁，从分支节点销毁到根节点【若从根节点开始销毁，会造成丢失从而找不到后续节点的地址】
- 销毁完全二叉树
6.创建非完全二叉树
非完全二叉树每个结构不一定相同，所以需要从终端接收用户输入决定二叉树的创建
/* 创建非完全二叉树 */
treenode *create_btree(void)
{
char ch = 0;
treenode *ptmpnode = NULL;
scanf(" %c", &ch);
if ('#' == ch)
{
return NULL;
}
ptmpnode = malloc(sizeof(treenode));
if (NULL == ptmpnode)
{
perror("fail to malloc");
return NULL;
}
ptmpnode->data = ch;
ptmpnode->pleftchild = create_btree();
ptmpnode->prightchild = create_btree();
return ptmpnode;
}7.获得树的深度/高度/层数
/* 获得树的高度、深度、层数 */
int get_bintree_height(treenode *proot)
{
int leftheight = 0;
int rightheight = 0;
if (NULL == proot)
{
return 0;
}
leftheight = get_bintree_height(proot->pleftchild);
rightheight = get_bintree_height(proot->prightchild);
return (leftheight > rightheight ? leftheight : rightheight)+1;
}8. 二叉树的深度优先遍历（非递归实现）
- 前序遍历
/* 非递归前序遍历 */
int preorder_btree_bystack(treenode *proot)
{
linknode *ptmpstack = NULL;
treenode *ptmpnode = NULL;
ptmpstack = create_empty_linkstack();
ptmpnode = proot;
while (1)
{
while (ptmpnode != NULL)
{
printf("%c ", ptmpnode->data);
push_linkstack(ptmpstack, ptmpnode);
ptmpnode = ptmpnode->pleftchild;
}
if (is_empty_linkstack(ptmpstack))
{
break;
}
ptmpnode = pop_linkstack(ptmpstack);
ptmpnode = ptmpnode->prightchild;
}
return 0;
}- 中序遍历
/* 非递归中序遍历 */
int inorder_btree_bystack(treenode *proot)
{
linknode *ptmpstack = NULL;
treenode *ptmpnode = NULL;
ptmpstack = create_empty_linkstack();
ptmpnode = proot;
while (1)
{
while (ptmpnode != NULL)
{
push_linkstack(ptmpstack, ptmpnode);
ptmpnode = ptmpnode->pleftchild;
}
if (is_empty_linkstack(ptmpstack))
{
break;
}
ptmpnode = pop_linkstack(ptmpstack);
printf("%c ", ptmpnode->data);
ptmpnode = ptmpnode->prightchild;
}
return 0;
}- 后序遍历
- 因为最后打印根节点，所以根节点需要2次入栈
- 第一次入栈，是为了出栈时找到该节点的右孩子，找到右孩子后，继续将节点入栈
- 第二次入栈，是为了打印该节点
/* 非递归后序遍历 */
int postorder_btree_bystack(treenode *proot)
{
linknode *ptmpstack = NULL;
treenode *ptmpnode = NULL;
ptmpstack = create_empty_linkstack();
ptmpnode = proot;
while (1)
{
while (ptmpnode != NULL)
{
ptmpnode->flag = 1;
push_linkstack(ptmpstack, ptmpnode);
ptmpnode = ptmpnode->pleftchild;
}
if (is_empty_linkstack(ptmpstack))
{
break;
}
ptmpnode = pop_linkstack(ptmpstack);
if (1 == ptmpnode->flag)
{
ptmpnode->flag = 0;
push_linkstack(ptmpstack, ptmpnode);
ptmpnode = ptmpnode->prightchild;
}
else if (0 == ptmpnode->flag)
{
printf("%c ", ptmpnode->data);
ptmpnode = NULL;
}
}
return 0;
}