二叉树的定义
二叉树T:一个有穷的结点集合。
- 这个集合可以为空
- 若不为空,则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树具体五种基本形态:
- 空二叉树;
- 只有根结点的二叉树;
- 只有根结点和左子树TL的二叉树;
- 只有根结点和右子树TR的二叉树;
- 具有根结点、左子树TL和右子树TR的二叉树。
二叉树的子树有左右顺序之分
几种特殊的二叉树
- 斜二叉树(Skewed Binary Tree)、退化二叉树
- 一条线的形状
- 完美二叉树(Perfect Binary Tree) / 满二叉树(Full Binary Tree)
- 所有子节点都是满的
- 完全二叉树(Complete Binary Tree)
- 子节点不一定满,但是从上到下,从左到右和满二叉树相同
几个重要性质
- 一个二叉树第 i 层的最大结点数为:\(2^{i-1}\) (\(i \ge 1\))
- 深度为k的二叉树有最大结点总数为: \(2^k - 1\) (\(k \ge 1\))
- 对任何非空二叉树 T,若n0表示叶结点的个数、n2是度为2的非叶结点个数,那么两者满足关系 \(n0 = n2 +1\)
抽象数据类型定义
类型名称:二叉树
数据对象集:一个有穷的结点集合。
若不为空,则由根结点和其左、右二叉子树组成。
操作集: BT ∈ BinTree, Item ∈ ElementType,重要操作有:
- BinTree CreatBinTree( ):创建一个二叉树
- Boolean IsEmpty( BinTree BT ): 判别BT是否为空
- void Traversal( BinTree BT ):遍历,按某顺序访问每个结点
四种常用的遍历方法:
- void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树;
- void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树;
- void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
- void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右
存储结构
顺序存储结构
按从上至下、从左到右顺序存储,适合完全二叉树,一般二叉树也可以采用这种结构,但会造成空间浪费
n个结点的完全二叉树的结点父子关系:
- 非根结点(序号 i > 1)的父结点的序号是 i/2
- 结点(序号为 i )的左孩子结点的序号是 2i, (若 \(2*i \le n\),说明有左孩子);
- 结点(序号为 i )的右孩子结点的序号是 2i+1, (若 \(2*i+1 \le n\),说明有右孩子);
链表存储
typedef struct TreeNode *BinTree;
typedef BinTree Position;
struct TreeNode {
ElementType Data;
BinTree Left;
BinTree Right;
}
标签:左子,结点,20230314,右子,BT,3.2,二叉树,BinTree
From: https://www.cnblogs.com/huangwenjie/p/17490494.html