敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 2、性质2：深度为k的二叉树至多有2-1个结点（由性质1，将各层最多的结点数累加，再 结合等比数列的求和得出) 思考：深度为k的二叉树至少有多少个结点？(k个)深度为k的b叉树至多/至少有多少 个结点？((bk1)/b-1), 3、性质3：no=2+1(n:表示二叉树中度为i的结点个数) 从两个角度考虑：二叉树中结点的构成（根据度）n=+1+m 二叉树中充当其余结点的孩子的结点数-1（去掉根）=n1+2×2 满二叉树：达到性质1,2中所述的最大值情况 完全二叉树：去掉最下一层的结点，其余结点形成一棵满二叉树；叶子集中在最下2层（或 1层)，最下一层的结点总是尽可能地占满左边的位置 4性质4：具有n个结点的完全二叉树的深度为6g,m+1 5、性质5：结点间的编号关系 考虑二叉树的顺序映像问题，寻求一种将二叉树映像为向量的方法： 对完全二叉树从上至下，从左至右，从根开始依次编号(1.)。 孩子编号 双亲编号 求双亲 i/2>0) 求孩子 左：2*i(<n+1),右：2*i+1(<n+1) i 右孩子编号 左孩子编号 求左兄弟 i(奇数，i>) i-1>0) 求右兄弟 +1(<n+1) i(偶数，in) 思考：满k叉树中结点间的编号关系？ 孩子编号 双亲编号 求双亲 p+(k-2) p (k≥2) 求第i个孩子 p·k+i(k-1)(<m+1) P 结点 结点的左兄弟 求左兄弟 p((p-1)%k≠1) p1(>0) 求右兄弟 p+1(<n+1) p(p-1)%k≠0) 6.2.3二叉树的存储结构 1、二叉树的顺序存储结构 1)方法 二叉树→补虚结点形成完全二叉树→自上而下、自左至右存储 2)类型定义 #define MAX TREE SIZE 100 *二叉树的最大结点数/ typedef Elem'Type SqBiTree[MAX TREE SIZE];/体0号单元存储根结点 */ 必须引入特殊符号表示虚结点的值 上述类型定义的缺陷：未指明实际二叉树占用的长度，可改进为： typedef struct{ ElemType elem[MAX TREE SIZE+1];/体1号单元存储根结点/ 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第4页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 4 页 第六章 树和二叉树 基本概念、遍历算法及其应用 2、性质 2：深度为 k 的二叉树至多有 2 k-1 个结点（由性质 1，将各层最多的结点数累加，再 结合等比数列的求和得出） 思考：深度为 k 的二叉树至少有多少个结点？( k 个 ) 深度为 k 的 b 叉树至多/至少有多少 个结点？( (bk-1)/(b-1)，k) 3、性质 3：n0=n2+1 (ni 表示二叉树中度为 i 的结点个数) 从两个角度考虑：二叉树中结点的构成（根据度）n = n0 + n1 + n2 二叉树中充当其余结点的孩子的结点数 n-1(去掉根) = n1+2×n2 满二叉树：达到性质 1,2 中所述的最大值情况 完全二叉树：去掉最下一层的结点，其余结点形成一棵满二叉树；叶子集中在最下 2 层(或 1 层)，最下一层的结点总是尽可能地占满左边的位置 4、性质 4：具有 n 个结点的完全二叉树的深度为 5、性质 5：结点间的编号关系 考虑二叉树的顺序映像问题，寻求一种将二叉树映像为向量的方法： 对完全二叉树从上至下，从左至右，从根开始依次编号(1..n)。 孩子编号 双亲编号 求双亲 i i/2(>0) 求孩子 左：2*i(<n+1), 右：2*i+1(<n+1) i 右孩子编号 左孩子编号 求左兄弟 i(奇数，i>1) i-1(>0) 求右兄弟 i+1(<n+1) i(偶数，i<n) 思考：满 k 叉树中结点间的编号关系？ 孩子编号 双亲编号 求双亲 p + − k p (k 2) (k≥2) 求第 i 个孩子 p·k+ i-(k-1) (<n+1) p 结点 结点的左兄弟 求左兄弟 p ( (p-1)%k≠1) p-1(>0) 求右兄弟 p+1(<n+1) p((p-1)%k≠0) 6.2.3 二叉树的存储结构 1、二叉树的顺序存储结构 1) 方法 二叉树→补虚结点形成完全二叉树→自上而下、自左至右存储 2) 类型定义 #define MAX_TREE_SIZE 100 /* 二叉树的最大结点数 */ typedef ElemType SqBiTree[MAX_TREE_SIZE]; /* 0 号单元存储根结点 */ 必须引入特殊符号表示虚结点的值 上述类型定义的缺陷：未指明实际二叉树占用的长度，可改进为： typedef struct{ ElemType elem[MAX_TREE_SIZE+1]; /* 1 号单元存储根结点 */ log2 n +1
敦案 第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 int length; }SqBiTree: 3)不足：空间的利用率不高 如：若深度为5且仅含有5个结点的二叉树，必须要占用2425-1空间。 2、二叉树的链式存储结构 parent 1)引入辅助空间表示结点间的相对关系 双亲(1)一一孩子(2)（如右图） data Ichild data rchild parent Ichild data rchild 二叉链表 三叉链表 lchild rchild 若需要找指定结点的双亲，则用三叉链表可在O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode ElemType data: struct BiTNode *lchild,*rchild; /体左右孩子指针*/ }BiTNode,*BiTree; 3)二叉链表的链域 若有n个结点，则共有2n个链域：其中n-1不为空，指向孩子。 4) 二叉树（链式存储）的创建 输入序列与二叉树的映射关系 (1)完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2)二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3)二叉树的两种遍历序列：先序+中序，后序+中序 6.3树和森林 1、树的存储结构 1)双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX TREE SIZE 100 体树的最大结点数 typedef struct PTNode ElemType data, int parent; PTNode: typedef struct PTNode nodes[MAX TREE_SIZE]; int n; 体结点数 */ PTree; 2)孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 文档编号 完成时间 完成人张昱 修改时间2002-6-6 第5页
程序设计——数据结构 文档编号 完 成 人 张 昱 完成时间 修改时间 2002-6-6 第 5 页 第六章 树和二叉树 基本概念、遍历算法及其应用 int length; }SqBiTree; 3) 不足：空间的利用率不高 如：若深度为 5 且仅含有 5 个结点的二叉树，必须要占用 2 4~2 5-1 空间。 2、二叉树的链式存储结构 1) 引入辅助空间表示结点间的相对关系 双亲(1)——孩子(2) (如右图) lchild data rchild parent lchild data rchild 二叉链表 三叉链表 若需要找指定结点的双亲，则用三叉链表可在 O(1)时间内获得某结点的双亲；而用二 叉链表则需从根开始，采用一定的巡查方法进行搜索。 2) 二叉链表的类型定义 typedef struct BiTNode{ ElemType data; struct BiTNode *lchild, *rchild; /* 左右孩子指针 */ }BiTNode, *BiTree; 3) 二叉链表的链域 若有 n 个结点，则共有 2n 个链域；其中 n-1 不为空，指向孩子。 4) 二叉树(链式存储)的创建 输入序列与二叉树的映射关系 (1) 完全二叉树的顺序映射 通过补虚结点，将一般的二叉树转变成完全二叉树，再对该完全二叉树的结点按 自上而下、自左至右进行输入。 (2) 二叉树的先序遍历 通过补虚结点，使二叉树中各实际结点均具有左右孩子，再对该二叉树按先序遍 历进行输入。 (3) 二叉树的两种遍历序列：先序+中序，后序+中序 6.3 树和森林 1、树的存储结构 1) 双亲表示法 针对每一结点，附设指示其双亲位置的数据域。采用顺序表（非顺序映像）。 #define MAX_TREE_SIZE 100 /* 树的最大结点数 */ typedef struct PTNode{ ElemType data; int parent; }PTNode; typedef struct{ PTNode nodes[MAX_TREE_SIZE]; int n; /* 结点数 */ }PTree; 2) 孩子表示法 各结点的孩子数是不定的，用顺序表表示必须给出树的度的最大值，以及每一结点的 data parent lchild rchild
第六章树和二叉树 程序设计—数据结构 基本概念、遍历算法及其应用 实际度数，空间浪费大。故以链表存储每一结点的所有孩子的位置信息。 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 遍历路径 先序访问 中序访问 后序访问