一、树形结构相关概念
- 树形结构：是一种常见的数据组织形式，具有层级和分支的特点
- 前驱：由前驱节点可以访问到当前节点
- 后续：当前节点可以访问到的节点
- 节点：组成树形结构的一个小单元
- 分支节点：既有前驱，又有后续的节点
- 根节点：只有后续，没有前驱
- 叶子节点：只有前驱，没有后续
- 层：根节点层数尾 0 ，在此基础上延伸一个节点，层数 + 1，其中层数最高节点对应的层数为树的层数
- 高度：当前节点到最远结点的距离
- 深度：当前节点到根节点的距离
- 度：后继结点的个数
二、二叉树
1、相关概念
- 二叉树：若树形结构中的所有节点度数最大为 2 则称为二叉树
- 左孩子：二叉树节点两个后继节点中的左节点
- 右孩子：二叉树节点两个后继节点中的右节点
- 满二叉树：所有叶子节点均在同一层，且每层节点个数均为最大值
- 完全二叉树：二叉树的编号（如果节点编号为n，左孩子编号:2n，右孩子编号为:2n+1）展开后是连续的， 称为完全二叉树
2.完全二叉树的遍历
深度优先遍历
前序遍历：访问节点，然后遍历左子树，最后遍历右子树（根左右）
中序遍历：遍历左子树，访问节点，然后遍历右子树（主要用于二叉搜索树，得到排序序列）（左根右）
- 后序遍历：遍历左子树，遍历右子树，最后访问节点（左右根）
广度优先遍历
- 层序遍历：逐层从左到右依次遍历
3、二叉树的操作
1.节点的定义
typedef struct node{
int no; //二叉树节点编号
struct node *leftchild; //左孩子地址
struct node *leftchild; //右孩子地址
}treenode;2.创建完全二叉树
思路：
- 使用函数递归完成二叉树的创建
- 首先申请节点空间，存放数据编号
- 如果存在左子树 / 右子树，创建左子树 / 右子树
代码实现：
//startno:创建起始节点编号
//endno:结束节点编号
treenode *create_treenode(int startno,int endno)
{
treenode *proot = NULL;
proot = malloc(sizeof(treenode)); //申请变量空间
if(NULL == proot)
{
perror("error to malloc");
return NULL;
}
proot->no = startno;
proot->leftchild = proot->rightchile = NULL;
if(startno*2 <= endno) //判断是否有左子树
{
proot->leftchild = create_terrnode(starno*2,endno); //函数递归调用
}
if(startno*2 + 1 <= endno) //判断是否有右子树
{
proot->rightchild = create_terrnode(starno*2 + 1,endno)；//函数递归调用
}
return proot;
}3.二叉树的深度优先遍历（使用递归函数）
/* 前序遍历 */
treenode *head_treenode(treenode *proot)
{
printf("%d ",proot->no);
if(proot->pleftchild != NULL)
{
head_treenode(proot->pleftchild);
}
if(proot->prightchild != NULL)
{
head_treenode(proot->prightchild);
}
}
/* 中序遍历 */
int inorder_btree(treenode *proot)
{
if (proot->pleftchild != NULL)
{
inorder_btree(proot->pleftchild);
}
printf("%d ", proot->no);
if (proot->prightchild != NULL)
{
inorder_btree(proot->prightchild);
}
return 0;
}
/* 后序遍历 */
int postorder_btree(treenode *proot)
{
if (proot->pleftchild != NULL)
{
postorder_btree(proot->pleftchild);
}
if (proot->prightchild != NULL)
{
postorder_btree(proot->prightchild);
}
printf("%d ", proot->no);
return 0;
}4.二叉树的层序遍历
思路 ：
- 利用二叉树中数据出入队列过程实现二叉树的层序遍历
- 上一层节点入队，判断左子树 / 右子树是否为空，若不是则让左子树 / 右子树入队，若两个子树均为空，则让该节点出队，并打印该节点标签号
代码实现：
void layout_treenode(treenode *proot)
{
treenode *ptmptree = NULL; //存储二叉树
linknode *ptmplink = NULL; //存储队列
ptmplink = malloc(sizeof(linknode)); //申请队列空间
if(ptmplink == NULL)
{
perror("error to malloc");
}
enter_linknode(ptmplink,proot); //将根节点插入队列
while(!is_empty_linklist(ptmlink)) //判断队列是否为空
{
treenode = quit_linklist(ptmlink); //将队头元素一处队列，并将队头元素地址赋treenode
printt("%d ",treenode->no); //打印树节点编号
//当左右子树都为空时，不再有新节点插入队列，退出循环
if(treenode->leftchild != NULL)
{
//若节点左子树不为空，则将左子树插入队列
enter_linknode(ptmplink,treenode->leftchild);
}
if(treenode->rightchild != NULL)
{
//若节点左子树不为空，则将左子树插入队列
enter_linknode(ptmplink,treenode->rightchild);
}
}
}
5.二叉树的销毁
思路：在后序遍历代码的基础上，将打印改为释放节点空间即可
代码：
/* 后序遍历 */
int postorder_btree(treenode *proot)
{
if (proot->pleftchild != NULL)
{
postorder_btree(proot->pleftchild);
}
if (proot->prightchild != NULL)
{
postorder_btree(proot->prightchild);
}
free(proot);
return 0;
} 6.非完全二叉树的创建
因非完全二叉树结构不固定，所以需要通过终端输入的方式创建非完全二叉树
代码实现：
treenode *creat_uptreenode(void)
{
treenode *ptmpnode = NULL;
int data = 0;
scanf("%d",&data);
if(data == -1)
{
return NULL;
}
ptreenode = malloc(sizeof(treenode));
if(ptreenode == NULL)
{
perror("error to malloc");
return NULL;
}
ptreenode->no = data;
ptrernode->leftchild = creak_uptreenode();
ptreenode->rightchild = creak_uptreenode();
return ptreenode;
}7.获得树的高度 / 最大层数
/* 获得树的高度（最大层数） */
int get_bintree_height(treenode *proot)
{
int leftheight = 0; // 初始化左子树的高度变量
int rightheight = 0; // 初始化右子树的高度变量
// 如果当前节点为空，说明到达了一片空树或叶子的下一层
if (NULL == proot)
{
return 0; // 空树的高度为0
}
// 递归调用自身，计算左子树的高度
leftheight = get_bintree_height(proot->pleftchild);
// 递归调用自身，计算右子树的高度
rightheight = get_bintree_height(proot->prightchild);
// 两个子树中较高的高度 + 1（加上当前节点所在的层）
// 这样递归返回到上层，就会得到整棵树的最大深度
return (leftheight > rightheight ? leftheight : rightheight) + 1;
}8.二叉树的深度遍历实现（非递归实现）
思路：
- 前序遍历与中序遍历
- 从根结点出发到叶子节点，将所有左孩子压入栈中
- 出栈一个节点，将该节点的右孩子按上一步的方法压入栈中
- 重复上述步骤，直到栈空停止
- 前序遍历在入栈时打印数据，中序遍历在出栈时打印数据
- 后序遍历
- 因为最后打印根节点，所以需要让根节点入栈两次
- 第一次出栈是为了找到根节点的右孩子
- 第二次如展示打印数据即为后序遍历的结果
代码实现：
/* 前序遍历与中序遍历 */
void preorder_tree(treenode *proot)
{
linknode *ptmpstack = NULL;
treenode *ptmptree = NULL;
ptmpstack = create_linkstack(); //申请栈空间
ptmptree = proot;
while(1)
{
while(ptmptree != NULL)
{
printf("%d ",ptmptree->data); //前序遍历打印点
push_linkstack(ptmstack,ptmptree);//找到最下端的左孩子
ptmptree = ptmptree->liftchild;
}
if(is_empty_linkstack)
{
break;
}
ptmptree = pop_linkstack(ptmstack); //元素出栈
printf("%d ",ptmptree->data); //中序遍历打印点
ptmptree = ptmptree->rightchild;
}
}
/* 非递归后序遍历 */
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;
}