2013-02-26 16:45
13. 树
tree是n(n>=0)个结点的有限集。n=0时称为空树。在任意一棵非空树中①有且仅有一个特定的称为根root的结点，②当n>1时，其余结点
可分为m(m>0)个互不相交的有限集，其中每一个集合本身又是一棵树。并且称为根的子树SubTree。
树的定义其实就是我们在讲解栈时提到的递归的方法。也就是在树的定义中还用到了树的概念。
13.1 树的定义中还需要强调两点
①n>0 时根结点时唯一的，不可能存在多个根结点。
②m>0 时，子树的个数没有限制，但是他们一定是互不相交的。
13.2 结点分类
13.2.1 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树称为结点的度degree。度为0的结点称为叶结点或终端结点。度不为0的结点称为非终端结点或分支结点。树的度是树内各结点的最大值。
13.2.2 结点之间的关系
结点的子树的根称为该结点的孩子child。相应地，该结点称为孩子的双亲parent。同一个双亲的孩子之间互成为兄弟sibling。
13.2.3 结点的层次level从根开始定义起，根为第一层，根的孩子为第2层。
树中结点的最大层次称为树的深度或高度。
如果将树中的结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序树，否则为无序树。
森林forest是m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。
14. 树结构和线性结构对比
①线性结构：第一个数据元素：无前驱；最后一个数据元素：无后继；中间元素：有且只有一个前驱和一个后继。
②树结构：根结点：无双亲，唯一；叶结点：可以多个，但叶结点无孩子；中间结点：一个双亲多个孩子，互不相交。
15. 树的存储结构：
首先，对于线性表的顺序存储结构，用一段地址连续的存储单元一次存储线性表的数据元素。
然而，树是一对多的结构。因此无论是任何顺序将树中所有结点存储到数组中，结点的存储位置都无法直接反映逻辑关系。因此，简单的顺序存储结构不能满足树的实现要求。
表示树的方法：
15.1 双亲表示法
除了根结点，其余的每个结点，它不一定有孩子，但是一定且仅有一个双亲。我们假设以一组连续空间存储树的结点，同时在每个节点中，附设一个指示器指示其双亲结点到链表中的位置。即每个结点除了知道自己是谁外，还知道它的双亲在哪里。结点结构为： data-parent。其中data是数据域，存储结点的数据信息；而parent是指针域，存储该结点的双亲在数组中的下标。
由于根结点没有双亲，所以我们约定根结点的位置域设置为-1。即，所有的结点都存有它双亲的位子。这样我们可以很容易的找到它的双亲结点，所用的时间复杂度为O（1）,直到parent为-1时，表示找到了树结点的根。但是，如果我们要直到结点的孩子是什么，那么只能遍历整个结构才行。所以就比较麻烦。
1 typedef struct pNode 2 { 3 int data; 4 int parent; 5 }; 6 7 typedef struct 8 { 9 pNode nodes[MAXSIZE]; 10 int root; 11 int num; 12 }PTree;
改进：我们增加一个结点最左边孩子的域，就叫长子域，这样就可以很容易得到结点的孩子。如果没有孩子的结点，这个长子域就设置为-1.另一种场景：我们关注各兄弟之间的关系，双亲表示法无法体现这样的关系，那么我们怎么办？可以增加一个右兄弟域来体现兄弟关系，也就是说，每个结点如果它存在右兄弟，则记录下右兄弟的下标，不存在，则赋值为-1.
15.2
换种完全不同的考虑方法。由于树中每个结点可能有多棵子树，可以考虑用多重链表。
多重链表表示法，即每个结点有多个指针域，其中每个指针指向一棵子树的根结点。不过，树的每个结点的度，也就是它的孩子个数是不同的。
方案一：
一种是指针域的个数就等于树的度。（树的度是树各个结点度的最大值。）
data-child1-child2-child3-。。。（data是数据域，child1-childn是指针域，用来指向该结点的孩子结点）。
首先看树的度是多少，则pNode的指针域则为度的个数。这种方法对于树中各结点的度相差很大时，显然是 很浪费空间的，因为有很多结点的指针域都是空的。不过如果树的各结点度相差很小时，那就意味着开辟的空间被充分利用了，这时存储结构的缺点反而变为了优点。
方案二：
既然很多指针域都可能为空，为什么我们不按需分配呢？
第二种方案每个结点指针域的个数等于该结点的度，我们专门取一个位置来存储结点指针域的个数，其结构为：
data-degree-child1-child2-。。。。（degree为度域，也就是存储该结点的孩子结点的个数，child1为指针域，指向该结点的各个孩子的结点）。
这种方法克服了浪费空间的缺点，对空间利用率是很高了，但是由于各几点的链表是不相同的结构，加上要维护结点的度的数值，在运算上就会带来时间上的损耗。
那么,有没有既可以减少空指针的浪费，又能使结点结构相同。仔细观察，我们为了要遍历整棵树，把每个结点放到一个顺序存储结构的数组中是合理的，但每个结点的孩子有多少是不确定的，所以我们再对每个结点的孩子建立一个单链表体现它们的关系。即孩子表示法！
15.3 孩子表示法
把每个结点的孩子排列起来，以单链表做存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空。
①孩子链表的孩子结点：child - next ；child是数据域，用来存储某结点在表头数组中的下标。next是指针域，用来存储指向某结点的下一个孩子结点的指针。
②另一个是表头数组的表头结点：data - firstchild ； data是数据域，存储某结点的数据信息。firstchild是头指针域，存储该结点的孩子链表的头指针。
1 typedef int dataype; 2 typedef struct ChildTNode 3 { 4 int child; //用来存储某结点在表头数组中的下标 5 struct ChildTNode *next;// 用来存储指向某个结点的next child pointer 6 }*ChildPtr; 7 8 typedef struct 9 { 10 datatype data; // 存储某结点的数据信息 11 ChildPtr firstchild; //存储该结点孩子链表的指针 12 }ChildTreeBox;
这样的结构对于我们要查找的某个结点的孩子。或者找某个结点的兄弟，只需要查找这个结点的孩子单链表即可。对于遍历整棵树也是很方便的，对头结点的数组循环即可。但这也是存在问题，我们如何知道某个结点的双亲是谁呢？比较麻烦，需要整棵树遍历才行，难道就不可以把双亲表示法和孩子表示法综合下嘛？嘿嘿，当然是可以的。
15.4 双亲孩子表示法
在孩子表示法的表头数组结构中，添加一个parent是指针域，存储该结点的双亲在数组中的下标。，root结点的双亲没有，则parent域为-1.这样表头数组结构为：
data-parent-firstchild
（data数据域，存结点数据信息，parent是指针域，存储该结点的双亲在数组中的下标。，firstchild为头指针域，存储该结点的孩子链表的头指针。）
1 typedef int datatype; 2 typedef struct ChildTNode 3 { 4 datatype data; 5 ChildTNode *next; 6 }*ChildPtr; 7 8 typedef struct 9 { 10 int data; 11 int parent; 12 ChildPtr firstchild; 13 }ChildParentTree;
15.5 孩子兄弟表示法
前面几个分别从双亲和孩子的角度研究树的存储结构，如果我们从树结点的兄弟的角度又该如何考虑呢？想想对于树的层级结构，只研究结点的兄弟是不行的，我们呢观察发现，任意一棵树，它的结点的第一个孩子如果存在就是唯一的，它的右兄弟如果存在也是唯一的。因此，我们设置两个指针，分别指向该结点的第一个孩子和此结点的右兄弟。
结点结构为：data-firstchild-rightsib
（data数据域，firstchild为指针域，存储该结点的第一个孩子结点的存储地址，rightsib是指针域，存储该结点的右兄弟的存储地址）
1 typedef int datatype; 2 typedef struct ChildRightsibNode 3 { 4 datatype data; 5 struct ChildRightsibNode *firstchild, *rightsib; 6 }CRNode, *CRTree;
这种方法给查找某个结点的某个孩子带来了方便，只需通过firstchild找到此结点的长子，然后再通过长子结点的rightsib找到它的二弟，接着一直下去，直到找到具体的孩子。如果想找某个结点的双亲，这个表示法也是有缺陷的，那怎么办呢？如果真有必要，那就再增加一个parent指针域来解决快速查找双亲的问题吧。
16. 二叉树
拆半查找的思想，对于在某个阶段都是两种结果的情形，比如开和关、0和1、真和假、上和下、对和错、正和反、都适合用树状结构来建模，而这种树是一种特殊的树状结构，叫做二叉树。
二叉树binary tree是n(n>=0)个结点的有限集合，该集合或者为空集（空二叉树），或由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树的二叉树组成。
16.1 二叉树的特点：
①每个结点最多有两棵子树（注意是最多只有两棵树），所以二叉树中不存在度大于2的结点。没有子树或者有一棵子树都是可以的。
②左子树和右子树是有序的，次序不能任意颠倒。
③即使树中某结点只有一棵树，也要区分它是左子树还是右子树。
16.2 二叉树具有5种形态：
①空二叉树
②只有一个根结点
③根结点只有左子树
④根结点只有右子树
⑤根结点既有左子树又有右子树
16.2.1 特殊二叉树
斜树：所有的结点都只有左子树的二叉树叫做左斜树；反之，右斜树；两者统称斜数。斜树有很明显的特点，就是每一层只有一个结点，结点的个数与二叉树的深度相同。
16.3 完美二叉树
在一棵树中，如果所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。
单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有的叶子都在同一层上，这就做到了整棵树的平衡。
满二叉树的特点：
①叶子只能出现在最下层，出现在其他层就不可能达成平衡。
②非叶子结点的度一定是2.
③在同样深度的二叉树中，满二叉树的结点个数最多，叶子树最多。
16.4 完全二叉树
对一棵具有n个结点的二叉树按层序编号，如果编号为i（1<= i <= n）的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置
完全相同，则这棵二叉树称为完全二叉树。
从字面上要区分，完全和满的差异，满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满的。其次，完全二叉树的所有结点与同样深度的满二叉树，它们按层次编号相同的结点，是一一对应的。
完全二叉树的特点：
1、叶子结点只能出现在最下两层。
2、最下层的叶子一定集中在左部连续位置。
3、倒数二层，若有叶子结点，一定都在右部连续位置。
4、如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
5、同样结点数的二叉树，完全二叉树的深度最小。
判断某二叉树是否是完全二叉树的办法，总的来说就是：看着树的示意图，心中默默给每个结点按照满二叉树的结构逐层顺序编号，如果编号出现空档，就说明不是完全二叉树，否则就是。
16.5 二叉树的性质
性质1：在二叉树的第i层上至多有2的i-1次幂个结点。(i>=1)
性质2：深度为k的二叉树至多有2的k次幂-1个结点。(k>=1)
性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1.
（终端结点数其实就是叶子结点数，而一棵而二叉树，除了叶子结点外，剩下的就是度为1或2的结点数了，我们设n1为度是1的结点数，
则T树结点总数n=n0+n1+n2。）
性质4：具有n个结点的完全二叉树的深度为log2n + 1
（由满二叉树的定义我们知道，深度为k的满二叉树的结点数n一定是2的k次幂-1. 因为这是最多的结点个数，那么对于n=2的k次幂-1推出满二叉树的度数k=log2（n+1）；而完全二叉树，它是一棵具有n个结点的二叉树，若按层序编号后其编号与同样深度的满二叉树中的编号结点在二叉树中位置相同，那么它就是完全二叉树，即，它的叶子结点只会出现在最下面的两层，它的结点数一定<=同样度数的满二叉树的结点数2的k次幂-1，但是一定多于2的k-1次幂-1，即：2的k-1次幂-1 < n <= 2的k次幂-1. ）
性质5：如果对一棵n个结点的完全二叉树的结点按层序编号，对任一结点i（1<=i<=n）
1、如果i = 1，则结点i是二叉树的根，无双亲；如i>1，则其双亲是结点i/2、
2、如果2i > n，则结点i无左孩子；否则其左孩子是结点2i
3、如果2i+1 > 2，则结点i无右孩子；否则其右孩子是结点2i+1
二叉树的存储结构：
二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构可以实现。二叉树的顺序存储结构就是用一维数组存储二叉树的结点，并且结点的存储位置，也就是数组的下标要能体现结点之间的逻辑关系，比如双亲与孩子的关系，左右孩子的关系等。如果是完全二叉树，用顺序存储，能够表现出二叉树的结构来。当然一般的二叉树，尽管层序编号不能反映逻辑关系，但是可以将其完全二叉树编号，只不过，把不存在的结点设置为空。
如果是一个深度为k的左、右斜树，其结点为k个，但是必须分配2的k次幂-1个存储单元空间。显然很浪费存储空间。因此，顺序存储一般只适用于完全二叉树。
16.6 二叉链表
顺序存储的实用性不强，考虑链式存储结构。
二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域。lchild-data-rchild（lchild和rchild分别存放指向左孩子和右孩子的指针）。如果需要知道其双亲是谁，则增加一个指向其双亲的指针域，那样就称之为三叉链表。
1 typedef int datatype; 2 typedef struct BiTNode 3 { 4 datatype data; 5 struct *BiTNode *lchild, *rchild; 6 }BiNode, *BiTree;
16.7 遍历二叉树
二叉树的遍历traversing binary tree是指从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被
访问一次。
关键词：访问和次序。
访问其实是要根据实际的需求来确定具体做什么，比如，对每个结点进行相关计算，输出打印等，它算作是一个抽象操作。二叉树的遍历次序不同于线性结构，最多也就是从头到尾、循环、双向等简单的遍历。树的结点之间不存在唯一的前驱和后继关系，在访问一个结点后，下一个被访问的结点面临着不同的选择。
①前序遍历。规则是：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，在前序遍历右子树。（根左右）
②中序遍历。规则是若树为空，则空操作返回，否则从根结点开始，中序遍历结点的左子树，然后是访问根结点，最后中序遍历右子树。
（左中右）
③后序遍历。规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点。（左右中）
④层次遍历。规则是若树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。
1 前序遍历-中左右 2 void PreOrderTravese(BiTree T) 3 { 4 if (T == NULL) 5 return ; 6 printf("%c", T->data); 7 PreOrderTravese(T->lchild); 8 PreOrderTravese(T->rchild); 9 } 10 11 中序遍历-左中右 12 void InOrderTravese(BiTree T) 13 { 14 if (T == NULL) 15 return ; 16 PreOrderTravese(T->lchild); 17 printf("%c", T->data); 18 PreOrderTravese(T->rchild); 19 } 20 21 后续遍历-左右中 22 void PostOrderTravese(BiTree T) 23 { 24 if (T == NULL) 25 return ; 26 PreOrderTravese(T->lchild); 27 PreOrderTravese(T->rchild); 28 printf("%c", T->data); 29 }
研究这么多遍历的方法有什么用呢？我们用图形的方式来表现树的结构，应该说是非常直观和容易理解的，但是对于计算机来说，它只有循环、判断等方式来处理，也就是说，它只会处理线性序列，而我们刚才的4种遍历方法，其实都是在把树中的结点变成某种意义的线性序列，这就给程序的实现带来了好处。
推导遍历结果：
如果已知一棵二叉树的前序遍历序列为ABCDEF,中序遍历序列为CBAEDF，请问这可二叉树的后续遍历的结果是多少？首先前序序列得出A为根结点，然后中序序列得出，C、B为A的左子树的结点，EDF为A的右子树的结点。然看前序序列中的C和B，它们顺序是BC，则说明是先打印B 后打印C，所以B应该是A的左孩子，而C就只可能是B 的孩子，此时左右还不确定。继续看中序中的序列，它们是CBA，则C很明显是B 的左孩子。接着分析A的右子树的结点EDF，在前序序列中它们3顺序为DEF，即D为A 的右孩子，EF为D的子孙（不一定就是孩子，可能是孙子）。接着看中序的排列EDF，所以E是D 的左孩子，F为右孩子。最终得出二叉树的图。
两个二叉树的性质：
1、已知前序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
2、已知后序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
已知前序和后序不能确定一棵二叉树。
建立二叉树利用了递归的原理。只不过在原来打印结点的地方，改成了生成结点，给结点赋值的操作。如果我们要在内存中建立一个树，为了能让每个结点确认是否是左右孩子，我们对它进行了拓展，也就是将二叉树中每个结点的空指针引出一个虚结点，其值为一特定值比如"#".我们称这种处理后的二叉树为原二叉树的拓展二叉树。拓展二叉树就可以做到一个遍历序列确定一棵二叉树。
1 前序序列创建一个二叉树 2 void CreateBiTree(BiTree *T) 3 { 4 char ch; 5 printf("please input:"); 6 scanf("%c", &ch); 7 if (ch == '#') 8 return ; 9 else 10 { 11 *T = (BiTree)malloc(sizeof(BiTNode)); 12 if (!*T) 13 printf("malloc error\n"); 14 (*T)->data = ch; 15 CreateBiTree(&((*T)->lchild)); 16 CreateBiTree(&((*T)->rchild)); 17 } 18 } 19 20 int main(void) 21 { 22 BiTree T; 23 CreateBiTree(&T); 24 .....各种序列输出 25 }
建立一个二叉树：
1 typedef int datatype; 2 typedef struct _BiTNode_ 3 { 4 datatype data; 5 struct _BiTNode_ *lchild, *rchild; 6 }BiTree; 7 8 BiTree *CreateBiTree(int i, int n) 9 { 10 BiTree *root; 11 root = (BiTree *)malloc(sizeof(BiTree)); 12 if (root == NULL) 13 printf("malloc error"); 14 root->data = i; 15 16 if (2*i <= n) 17 root->lchild = CreateBiTree(2*1, n); 18 else 19 root->lchild = NULL; 20 21 if (2*i + 1 <= n) 22 root->rchild = CreateBiTree(2*1 + 1, n); 23 else 24 root->rchild = NULL; 25 26 return root; 27 } 28 29 int main(void) 30 { 31 BiTree *root; 32 root = CreateBiTree(1, 10); 33 .....前序、后序、中序遍历..... 34 35 return 0; 36 }
参考学习资料：《大话数据结构》。