二叉树及存储结构
分类:
文章
•
2022-10-06 14:30:37
定义
- 二叉树T：一个有穷的结点集合。
这个集合可以为空
若不为空，则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成
- 特殊的二叉树
斜二叉树（Skewed Binary Tree)
完美二叉树（Perfect Binary Tree）/满二叉树（Full Binary Tree）
完全二叉树（Complete Binary Tree）：有n个结点的二叉树，对树中结点按从上至下、从左到右顺序进行编号， 编号为i（1 ≤ i ≤ n）结点与满二叉树中编号为 i 结点在二叉树中位置相同
- 二叉树的重要性质
- 一个二叉树第 i 层的最大结点数为： 2^(i-1)，i>=1。
- 对任何非空二叉树 T，若n0表示叶结点的个数、n2是度为2的非叶结点个数，那么两者满足关系: n0 = n2 +1。 (推导）
- 深度为k的二叉树有最大结点总数为： 2^k-1，k >=1。
- 二叉树的抽象数据类型
操作集：
1、Boolean IsEmpty( BinTree BT )： 判别BT是否为空；
2、void Traversal( BinTree BT )：遍历，按某顺序访问每个结点；
3、BinTree CreatBinTree( )：创建一个二叉树。
常用的遍历方法有：
void PreOrderTraversal( BinTree BT )：先序----根、左子树、右子树；
void InOrderTraversal( BinTree BT )： 中序—左子树、根、右子树；
void PostOrderTraversal( BinTree BT )：后序—左子树、右子树、根
void LevelOrderTraversal( BinTree BT )：层次遍历，从上到下、从左到右
- 二叉树的存储结构
1.顺序存储
2.链表存储
