二叉树及存储结构
2018-11-01 本文已影响17人
下页天
二叉树的定义
二叉树T:一个有穷的结点集合。
这个集合可以为空
若不为空，则它是由根结点和称为其左子树TL和右子树TR的
两个不相交的二叉树组成。
二叉树的子树有左右顺序之分
特殊二叉树
- 斜二叉树（树的分支只有一个方向 类似于数组和单向链表）
- 完美二叉树或满二叉树（结点和层数满足 结点=2^(层数)- 1）
- 完全二叉树（有n个结点的二叉树，对树中结点按 从上至下、从左到右顺序进行编号， 编号为i(1 ≤ i ≤ n)结点与满二叉树 中编号为 i 结点在二叉树中位置相同）
二叉树几个重要性质
- 一个二叉树第 i 层的最大结点数为:2 i-1，i >= 1。
- 深度为k的二叉树有最大结点总数为: 2 k-1，k >= 1。
- 任何非空二叉树 T，若n0表示叶结点的个数、n2是 度为2的非叶结点个数，那么两者满足关系n0 = n2 +1。(边相等理论证明)
二叉树的存储结构
- 顺序存储结构
完全二叉树:按从上至下、从左到右顺序存储
n个结点的完全二叉树的结点父子关系:
TreeArr1.png
一般二叉树也可以采用这种结构，但会造成空间浪费...... 需要先补全成完全二叉树
-
链表存储
TreeList1.png
二叉树的遍历
先序遍历 （根结点--> 左结点--> 右结点）
PreOrder.png
中序遍历 （左结点--> 根结点--> 右结点）
Inorder.png
后序遍历 （左结点--> 右结点--> 根结点）
PostOrder.png
