大话数据结构-树( 二 ) _前序遍历

1
1
B
0
3
2
C
0
5
3
D
1
-1
4
E
1
-1
5
F
2
8
6
G
2
9
7
H
2
10
8
I
5
-1
9
J
6
-1
10
K
7
-1
当然，也可以按需要，添加其他域，比如添加右兄弟域来体现兄弟关系等。
6.2 孩子表示法
孩子表示法，即把每个结点的孩子结点排列起来，以单链表作存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放进一个一维数组中。
为此，设计两种结点结构，一个是孩子链表的孩子结点：
其中child是数据域，用来存储某个结点在表头数组中的下标， next是指针域，用来存储指向下一个孩子结点的指针。
另一个是表头数组的表头结点，如下所示：
其中data是数据域，存储某结点的数据信息，是头指针域，存储该结点的孩子链表的头指针。
同样，如果为了提高查询某结点的双亲时，可以在这个结构中，添加双亲指针，类似：
这种结构叫双亲孩子表示法。
6.3 孩子兄弟表示法
任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的，因此我们设置两个指针，分别指向该结点的长子和右兄弟：
对于下面的树来说，结构变更为：
这种表示法，给查找某个结点的某个孩子带来了方便，只需要通过找到此结点的长子，然后再通过长子结点的，找到它的二弟，接着一直下去，直到找到具体的孩子。
实际上，这种处理方式，直接把一棵复杂的树，变更成了一棵二叉树：
7 二叉树 7.1 概述
二叉树（ Tree）是n（n >= 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
二叉树的特点：
(1) 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点；
(2) 左子树与右子树是有顺序的，次序不能任意颠倒；
(3) 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树；
二叉树具有五种形态：
(1) 空二叉树；
(2) 只有一个根结点；
(3) 根结点只有左子树；
(4) 根结点只有右子树；
(5) 根结点既有左子树也有右子树；
7.2 特殊二叉树
(1) 斜树：所有的结点都只有左子树的二叉树叫左斜树，所有结点都只有右子树的二叉树叫右斜树，两者统称斜树。线性表结构就可以理解为是树的一种极其特殊的表现形式；
如下为左斜树：
如下为右斜树：
(2) 满二叉树：在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树：

文章插图
单是每个结点都存在左右子树，不能算是满二叉树，还必须所有的叶子都在同一层上，这就做到了整棵树的平衡，因此满二叉树的特点有：