59_树到二叉树的转换

关键词：双亲孩子表示法、孩子兄弟表示法、二叉树的定义、特殊的二叉树、完全二叉树的特性

0. 双亲孩子表示法

• 每个结点都有一个指向其双亲的指针
• 每个结点都有若干个指向其孩子的指针

1. 孩子兄弟表示法

• 每个结点都有一个指向其第一个孩子的指针
• 每个结点都有一个指向其第一个右兄弟的指针
  双亲孩子表示法转换为孩子兄弟表示法

2. 孩子兄弟表示法的特点

• 能够表示任意的树形结构
• 每个结点包含一个数据成员和两个指针成员
• 孩子结点指针和兄弟结点指针构成了树杈

3. 二叉树的定义

二叉树是由n(n>=0)个结点组成的有限集合，该集合或者为空，或者是由一个根结点加上两颗分别称为左子树和右子树的、互不相交的二叉树组成。

二叉树的5种形态

4. 特殊的二叉树

• 满二叉树：如果二叉树所有分支结点的度数都为2，且叶子结点都在同一层次上，则称这类二叉树为满二叉树。
• 完全二叉树： 如果一颗具有n个结点的高度为k的二叉树，它的每一个结点都与高度为k的满二叉树中编号为1-n的结点一一对应，则称这颗二叉树为完全二叉树。（从上到下从左到右编号）

5. 完全二叉树的特性

• 同样结点数的二叉树，完全二叉树的高度最小
• 完全二叉树的叶结点仅出现在最下两层
• 最底层的叶结点一定出现在左边
• 倒数第二层的叶结点一定出现在右边
• 完全二叉树中度为1的结点只有左孩子

6. 小结

• 通用树结构采用了双亲结点表示法进行描述
• 孩子兄弟表示法有能力描述任意类型的树结构
• 孩子兄弟表示法能够将通用树转化为二叉树
• 二叉树是最多只有两个孩子的树

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4