二叉树的定义、性质、存储

布满荆棘的人生 2022-09-26 01:53 157阅读 0赞

二叉树的定义

**二叉树**是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（*left subtree*）和“右子树”（*right subtree*）。二叉树常被用于实现二叉查找树和二叉堆。

![2012110117584421.jpg][]

二叉树的每个结点至多只有二棵子树(不存在度大于2的结点)，二叉树的子树有左右之分，次序不能颠倒。

特殊二叉树

1. **斜树**

所有结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树。斜树的每一层都只有一个结点，结点的个数与斜树的深度相同。

2. **满二叉树**

在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。（上图中所示的二叉树，就是一棵满二叉树）

3. **完全二叉树**

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1≤i≤n）的结点与同样深度的满二叉树中的编号为i的结点在二叉树中的位置完全相同，则这棵二叉树称为完全二叉树。

![2012110118012978.jpg][]

二叉树的性质

性质1：在二叉树的第i层上至多有2i-1个结点（i≥1）。（数学归纳法可证）

性质2：深度为k的二叉树最多有2k\-1个结点（k≥1）。（由性质1，通过等比数列求和可证）

性质3：一棵二叉树的叶子结点数为n0，度为2的结点数为n2，则n0 = n2 + 1。

证：结点总数n = n0 + n1 + n2。设B为分支总数，因为除根节点外，其余结点都有一个分支进入，所以n = B + 1。又因为分支是由度为1或2的结点射出，所以B = n1 + 2n2。综上：n = n0 + n1 + n2= B + 1 = n1 + 2n2 + 1，得出：n0 = n2 + 1。

性质4：具有n个结点的完全二叉树的深度为floor(log2n) + 1 。

性质5：如果对一棵有n个结点的完全二叉树（其深度为floor(log2n) + 1 ）的结点按层序编号，则对任一结点i（1≤i≤n）有：

（1） 如果i = 1，则结点i是二叉树的根，无双亲；如果i > 1，则其双亲PARENT(i)是结点 floor((i)/2)。

（2）如果2i > n，则结点i无左孩子；否则其左孩子LCHILD(i)是结点2i。

（3）如果2i + 1 > n，则结点i无右孩子；否则其右孩子RCHILD(i)是结点2i + 1。

二叉树的存储

1. 顺序存储结构

二叉树可以用一维数组或线性表来存储，而且如果这是完全二叉树，这种方法不会浪费空间。

![2012110118123552.jpg][]

并且这种紧凑排列，如果一个结点的索引为i，则它的子结点能在索引2i+1和2i+2找到，并且它的父节点（如果有）能在索引floor((i-1)/2)找到（假设根节点的索引为0）。

对于一般的二叉树，其层序编号不能反映出逻辑关系，但是可以将其按照完全二叉树编号，只不过把不存在的结点设置为NULL即可。但这么做有一个问题，就是会浪费存储空间。最坏情况下，一个深度为k的斜树（只有k个结点），却需要长度为2k\-1的一维数组。所以顺序存储结构一般只用于完全二叉树。

2. 链式存储结构

每个结点含有一个数据域和两个指针域（分别指向左右子树）。

![2012110118143952.jpg][]

// 二叉树的二叉链表存储表示

typedef struct BiTNode

TElemType data;

struct BiTNode \*lchild,\*rchild; // 左右孩子指针

\}BiTNode,\*BiTree;

利用这种结点结构所得的二叉树存储结构称之为二叉链表。在二叉链表中，如果想找到某个结点的双亲，需要从根节点开始遍历，所以有时为了便于找到结点的双亲，还可以在结点结构中增加一个指向其双亲结点的指针域，相应的二叉树存储结构称之为三叉链表。

![2012110118163749.jpg][]

Reference:

\[1\] 《大话数据结构》

\[2\] 《数据结构 严蔚敏》

\[3\]  wikipedia(二叉树)：http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%8F%89%E6%A0%91

[2012110117584421.jpg]: /images/20220717/b865cddedbc740b4a706a3ed92e6ffaa.png
[2012110118012978.jpg]: /images/20220717/f539901f32ca4f90a1763b623d8e2660.png
[2012110118123552.jpg]: /images/20220717/127259f313ce4236a715e35a37df2022.png
[2012110118143952.jpg]: /images/20220717/3a90d4ec91fb4641bc74acdc24b5b900.png
[2012110118163749.jpg]: /images/20220717/dbc63c554b6d43fdb9c1f770ee8070de.png