孙丽云数据结构树和叉树(讲).pptVIP

3、孩子兄弟链表表示法 用二叉链表作为树的存储结构，每个结点的左链域指向该结点的第一个孩子，右链域指向下一个兄弟结点。由于结点中的两个指针指示的分别为“孩子”和“兄弟”，故称为“孩子-兄弟链表”。 树的孩子兄弟链表的存储结构描述为： typedef struct CSNode { ElemType data; 　struct CSNode *firstchild,*nextsibling; } CSNode, *CSTree; ^ R A D ^ B ^ ^ E ^ ^ C ^ F G ^ H ^ ^ K ^ 树的二叉链表表示法 孩子兄弟存储结构的优点是可以方便地实现树和二叉树的相互转换和树的各种操作；缺点是查找当前结点的双亲结点比较麻烦。 R A B C D E F G H K 6.1.5 树和森林的遍历 1．树的遍历 所谓树的遍历，就是按照某种顺序依次访问树中各个结点，并使得每个结点只被访问一次。也就是把非线性结构的树结点变成线性序列的一种方式。 树的遍历方法有： 按广度优先遍历（即按层次遍历） 按深度优先遍历，又可分为：前序遍历和后序遍历 ①前序遍历一棵树恰好等价于前序遍历该树所对应的二叉树。 ②后序遍历树恰好等价于中序遍历该树所对应的二叉树。 R A D B E C F G H K 1、按广度优先遍历（即按层次遍历） 2、按深度优先遍历： (1)前序遍历(2)后序遍历 例： R A B C D E F G H K 2．森林的遍历 A B C D E F G H I J 森林的遍历可分为前序遍历与后序遍历 例： ①前序遍历森林恰好等价于前序遍历该森林所对应的二叉树。 ②后序遍历森林恰好等价于中序遍历该森林所对应的二叉树。 A B E C D F G H I J 6.5 二叉树的应用 1 二叉排序树 二叉排序树T是一棵二叉树，或者为空，或者满足下面条件： （1）若T的根结点的左子树非空，则左子树中所有结点的值均小于根结点值； （2）若T的根结点的右子树非空，则右子树中所有结点的值均大于根结点值； （3）T的左右子树也分别为二叉排序树。 50 30 80 20 90 10 85 40 35 25 23 88 例如: 是二叉排序树。 66 不 第9章中应用 路径长度和哈夫曼树 1．二叉树的路径长度 从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称为路径长度。树的路径长度是指从树根到树中每一结点的路径长度之和。 在结点数目相同的二叉树中，完全二叉树的路径长度最短。 二叉树的链式存储结构 根据二叉树的非线性结构的特点，常用链式存储方式来表示二叉树。 把每个结点分成三个域：一个域存放结点本身的信息，另外两个是指针域，分别存放左、右孩子的地址。每个结点的结构表示为： lchild data rchild A D E B C F ? ? ? ? ? ? ? root lchild data rchild 结点结构: 二叉链表 typedef struct Node { // 结点结构 ElemType data; struct Node *lchild, *rchild; // 左右孩子指针 } BTNode, *Tree; 二叉链表的C 语言类型描述如下: 说明： 一个二叉链表由根指针root唯一确定。若二叉树为空，则root=NULL；若结点的某个孩子不存在，则相应的指针为空。 具有n个结点的二叉链表中，共有2n个指针域。其中只有n-1个用来指示结点的左、右孩子，其余的n+1个指针域为空。 A D E B C F ? ? ? ? ? ? ? root ? 带双亲指针的二叉链表 parent lchild data rchild 结点结构: 6.3 遍历二叉树和线索二叉树 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条有哪些信誉好的足球投注网站路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 “遍历”是任何类型均有的操作，对线性结构而言，只有一条有哪些信誉好的足球投注网站路径(因为每个结点均只有一个后继)，故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的有哪些信誉好的足球投注网站路径遍历的问题。 遍历二叉树和线索二叉树 b c a (根结点) (右子树) (左子树) 由二叉树的递归定义， 二叉树的三个基本组成 单元是：根结点、左子 树和右子树。 假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，遍历整个二叉树则有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案