第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 typedef struct CTNode /*孩子结点 利 int child; 体孩子结点的位置编号*/ struct CTNode *next; 体下一个孩子结点制 }*ChildPtr: typedef struct TElemType data; ChildPtr firstchild; /体孩子链表的头指针/ CTBox: typedef struct{ CTBox nodes[MAX TREE SIZE]; int n,r; /体结点数和根的位置/ }CTree; 3)孩子兄弟法 二叉链表表示。针对每一结点，引入其第一个孩子和下一个右兄弟的位置域。 typedef struct CSNode ElemType data struct CSNode *firstchild,*nextsibling; 体第一个孩子、下一个兄弟指针*/ CSNode.*CSTree: 2、森林与二叉树的转换 森林用孩子兄弟法表示，形成二叉链表，可以将它理解为一个二叉树的二叉链表： 二叉树用二叉链表表示，可以将该二叉链表理解为孩子兄弟链表，从而获得森林。 6.4二叉树的先中后序遍历算法 1、遍历 ·对于二叉树中的结点，有且仅访问一次 ·遍历的规律性：（左子树）、D(根)、R(右子树)的排列上 限定L在R前访问（有对称关系的，只须考虑其中的一种） ·先（根）序遍历 DLR ·中（根）序遍历 LDR ·后（根）序遍历 LRD 2、二叉树遍历的递归实现 遍历路径 二叉树的递归定义性质，决定了它的很多算法都可用递归实现， 遍历就是其中之一。 先序访问 对于二叉树的遍历，可以不去具体考虑各子问题（左子树、根、右 子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原 问题（二叉树）的遍历结果一一递归规律的确定。必须注意的是，当二 叉树小到一定程度，即空树时，应直接给出解答一一递归结束条件及 处理。 三种遍历的区别（右图）：所经过的搜索路线是相同的：只是访问中序访问)后序访问 结点的时机不同。每一结点在整个搜索路线中会经过3次（第一次进入到该结点、由左子树回 溯到该结点、由右子树回溯到该结点)，如在第一次遇到时就访问该结点，那么称之为先序：第 二次经过时访问为中序：第三次经过时访问则为后序。 1)先序遍历 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第6页程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 6 页 第六章 树和二叉树 基本概念、遍历算法及其应用 实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 typedef struct CTNode{ /* 孩子结点 */ int child; /* 孩子结点的位置编号*/ struct CTNode *next; /* 下一个孩子结点 */ }*ChildPtr; typedef struct{ TElemType data; ChildPtr firstchild; /* 孩子链表的头指针 */ }CTBox; typedef struct{ CTBox nodes[MAX_TREE_SIZE]; int n, r; /* 结点数和根的位置 */ }CTree; 3) 孩子兄弟法 二叉链表表示。针对每一结点，引入其第一个孩子和下一个右兄弟的位置域。 typedef struct CSNode{ ElemType data; struct CSNode *firstchild, *nextsibling; /* 第一个孩子、下一个兄弟指针 */ }CSNode, *CSTree; 2、森林与二叉树的转换 森林用孩子兄弟法表示，形成二叉链表，可以将它理解为一个二叉树的二叉链表； 二叉树用二叉链表表示，可以将该二叉链表理解为孩子兄弟链表，从而获得森林。 6.4 二叉树的先|中|后序遍历算法 1、遍历 ·对于二叉树中的结点，有且仅访问一次 ·遍历的规律性：L(左子树)、D(根)、R(右子树)的排列上 限定 L 在 R 前访问(有对称关系的，只须考虑其中的一种) ·先(根)序遍历 DLR ·中(根)序遍历 LDR ·后(根)序遍历 LRD 2、二叉树遍历的递归实现 二叉树的递归定义性质，决定了它的很多算法都可用递归实现， 遍历就是其中之一。 对于二叉树的遍历，可以不去具体考虑各子问题(左子树、根、右 子树)的遍历结果是什么，而去考虑如何由各子问题的求解结果构成原 问题(二叉树)的遍历结果——递归规律的确定。必须注意的是，当二 叉树小到一定程度，即空树时，应直接给出解答——递归结束条件及 处理。 三种遍历的区别(右图)：所经过的搜索路线是相同的；只是访问 结点的时机不同。每一结点在整个搜索路线中会经过 3 次（第一次进入到该结点、由左子树回 溯到该结点、由右子树回溯到该结点），如在第一次遇到时就访问该结点，那么称之为先序；第 二次经过时访问为中序；第三次经过时访问则为后序。 1) 先序遍历 - * c a b 遍历路径 先序访问 中序访问 后序访问