🙊🙊作者主页：🔗求不脱发的博客
📔📔 精选专栏：🔗数据结构与算法
📋📋 精彩摘要：在二叉树的一些应用中，常常要求在数中查找具有某种特征的结点，或者是对树中的全部结点逐一进行处理，这就提出了一个遍历二叉树的问题。本章将详细介绍二叉树的存储和遍历。
💞💞觉得文章还不错的话欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞
📚目录
📖【数据结构与算法】第十一章：二叉树深入浅出
📝1️⃣二叉树的存储
✨二叉树的顺序存储
【实现】
对于二叉树的顺序存储，需要按满二叉树的结点层次编号，依次存放二叉树中的数据元素。
编辑
【特点】
- 结点间关系蕴含在其存储位置中。
- 浪费空间，适合存满二叉树或完全二叉树。
✨二叉树的链式存储
对于二叉树的链式存储，需借助左右指针用来存放结点间的关系位置。
编辑
【结构定义】
typedef struct BiNode { TElemType data;//存放数据 struct BiNode *lchild,*rchild;//左右孩子指针 }BiNode,*BiTree;
【练习】
在n个结点的二叉链表中，有 ———个空指针域。
【分析】
n个结点的二叉链表必有2n个指针域。除根结点外，每个结点有且仅有一个双亲，所以只会有，-1个结点的链域存放指针，指向非空子女结点。
即 ：空指针域 = 2n - (n-1)。
✨三叉链表
三叉链表类似二叉链表，不同的是三叉链表多出一个parent指针，用来存储上一个结点即父结点的地址。
【结构定义】
typedef struct TriTNode { TelemType data; struct TriTNode *lchild,*rchild,*parent; }TriTNode,*TriTree;
例如：
编辑
📝2️⃣二叉树的遍历
✨遍历
【定义】：指按照某条搜索路线遍历每个接地那且不重复（又称为周游）
【用途】：它是树结构插入、删除、修改、查找和排序运算的前提，是二叉树一切运算的基础和核心。
【规则】：先序遍历、中序遍历、后序遍历。
编辑
例如，对于上图中的树
- 先序遍历：ABEKLFDHMJ
- 中序遍历：KELBFAHMDJ
- 后续遍历：KLEFBMHJDA
✨先序遍历
【分析】
- 若果二叉树为空，则空操作。
- 否则：
- 先访问根结点，
- 先序遍历左子树，
- 先序遍历右子树。
【实现】
Status PreOrderTraverse(BiTree T) { if(T==NULL) return OK; else { cout<<T->data;//访问根结点 PreOrderTraverse(T->lchild);//递归遍历左子树 PreOrderTraverse(T->rchild);//递归遍历右子树 } }
✨先序遍历
【分析】
- 若果二叉树为空，则空操作。
- 否则：
- 中序遍历左子树
- 访问根节点
- 中序遍历右子树
【实现】
Status InOrderTraverse(BiTree T) { if(T==NULL) return OK; else { InOrderTraverse(T->lchild);//递归遍历左子树 cout<<T->data;//访问根结点 InOrderTraverse(T->rchild);//递归遍历右子树 } }
✨后序遍历
【分析】
- 若果二叉树为空，则空操作。
- 否则：
- 后序遍历左子树
- 后序遍历右子树
- 访问根结点
【实现】
Status PostOrderTraverse(BiTree T) { if(T==NULL) return OK; else { PostOrderTraverse(T->lchild);//递归遍历左子树 PostOrderTraverse(T->rchild);//递归遍历右子树 cout<<T->data;//访问根结点 } }
✨遍历算法分析
如果去掉输出语句，从递归的角度来看，三种算法是完全相同的，或说这三种算法的访问路径是相同的，只是访问结点的实际不同。
【时间效率】：O(n)，每个结点访问一次。
【空间效率】：O(n)，栈占用的最大辅助空间。
✨二叉树的建立
按照先序遍历序列建立二叉树的二叉链表。
例如：已知先序序列为：
A B C ∅ ∅ D E ∅ G ∅ ∅ F ∅ ∅ ∅
编辑
【实现】
void CreatBiTree(BiTree &T) { cin>>ch; if(ch == '#') T=NULL;//遇到 # 字符 递归结束，建立空树 else { T = new BiTNode; T->data = ch;//生成根结点 CreatBiTree(T->lchild)//递归创建左子树 CreatBiTree(T->rchild)//递归创建右子树 } }
✨遍历算法应用
一、计算二叉树结点总数
【分析】
如果二叉树为空树，则结点个数为0。否则，结点个数为左子树结点数+右子树结点数+1
【实现】
int NodeCount(BiTree T) { if(T==NULL) return 0; else { return NodeCount(T->lchild) + NodeCount(T->rchild) + 1; } }
二、计算二叉树叶子结点总数
【分析】
如果二叉树为空树，则叶子结点总数为0。否则，结点总数为左子树叶子结点总数+右子树叶子结点总数
【实现】
int LeadCount(BiTree T) { if(T==NULL) return 0; if(T->lchild == NULL && T->rchild == NULL) return 1; else return LeadCount(T->lchild) + LeadCount(T->rchild); }
三、计算二叉树的深度
【分析】
如果二叉树为空树，则叶子结点总数为0。否则，递归左子树，深度即为m。递归右子树，深度记为n，二叉树的深度为m和 n中较大者 + 1 。
【实现】
int Depth(BiTree T) { if(T==NULL) retunr 0; else { int m = Depth(T->lchild); int n = Depth(T->rchild); if(m > n) return m + 1; else return n + 1; } }
重要结论：
若二叉树中各结点的值不同，则由二叉树的前序序列和中序序列，或由其后序序列和中序序列均能唯一的确定一颗二叉树。
但由前序序列和后序序列却不一定能唯一的确定一颗二叉树。
