第六章树和二叉树 第一节树的类型定义 为“根 °T1、12和T3都是一棵树,称为A的子树。 称根和子树根之间的连线为“分支 结点分支的个数定义为“结点的度”,如结点B的度为2,D的度为3。 树中所有结点度的最大值定义为树的度”。 称度为零的结点为“叶子” 或“终端结点 所有度不为零的结点 被称作”分支结点 基本定义 森林为m(m≥0)棵互不相交的树的集合。 树的深度定义为树中叶子结点所在最大层次数。 称根结点为子树根的”双亲”。 称子树根为根结点的孩子“ 根的所有子树根互为“兄弟”。 °有序树、无序树如果树中 每棵子树从左向右的排列拥有 定的顺序,不得互换,则称 为有序树,否则称为无序树。 树的抽象数据类型: .ADT Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系 若D为空集,则称为空树 若D中仅含一个数据元素,则关系R为空集; 否则R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)当n>1时,其余数据元素可分为m(m>0)个互不相交的非空有限集T1,T2,,Tm 其中每一个子集本身又是一棵符合本定义的树,称为根root的子树,每一棵子树的根xi都 是根root的后继,即H,=1,2,,m。 基本操作: {结构初始化} 操作结果:构造空树T CreateTree(&T, definition) 初始条件: definition给出树T的定义。 操作结果:按 definition构造树T
第六章 树和二叉树 第一节 树的类型定义 •A 为“根” •T1、T2 和 T3 都是一棵树，称为 A 的子树。 •称根和子树根之间的连线为“分支” •结点分支的个数定义为“结点的度”，如结点 B 的度为 2，D 的度为 3。 •树中所有结点度的最大值定义为“树的度”。 •称度为零的结点为“叶子” 或“终端结点” •所有度不为零的结点 被称作"分支结点" 基本定义 •森林为 m(m≥0) 棵互不相交的树的集合。 •树的深度定义为树中叶子结点所在最大层次数。 •称根结点为子树根的"双亲"。 •称子树根为根结点的"孩子“ •根的所有子树根互为“兄弟”。 •有序树、无序树 如果树中 每棵子树从左向右的排列拥有 一定的顺序，不得互换，则称 为有序树，否则称为无序树。 树的抽象数据类型： •ADT Tree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，则称为空树； 若 D 中仅含一个数据元素，则关系 R 为空集； 否则 R={H}， (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) 当 n>1 时，其余数据元素可分为 m(m>0) 个互不相交的(非空)有限集 T1,T2,…,Tm, 其中每一个子集本身又是一棵符合本定义的树，称为根 root 的子树，每一棵子树的根 xi 都 是根 root 的后继，即 H,i=1,2,…,m。 •基本操作： {结构初始化} InitTree(&T); 操作结果：构造空树 T。 CreateTree(&T,definition); 初始条件：definition 给出树 T 的定义。 操作结果：按 definition 构造树 T
{销毁结构 DestroyTree(&T) 初始条件:树T存在。 操作结果:销毁树T。 {引用型操作 初始条件:树T存在 操作结果:若T为空树,则返回TRUE,否则返回 FALSE。 IreeDepth(t); 初始条件:树T存在。 操作结果:返回T的深度。 Root(D); 初始条件:树T存在 操作结果:返回T的根 cur 初始条件:树T存在,cure是T中某个结点。 操作结果:返回cure的值。 初始条件:树T存在,cure是T中某个结点。 操作结果:若cure是T的非根结点,则返回它的双亲,否则返回"空"。 LeftChild (t, cur e) 初始条件:树T存在,cure是T中某个结点 操作结果:若cure是T的非叶子结点,则返回它的最左孩子,否则返回"空"。 Rightsibling(l, cur e); 初始条件:树T存在,cure是T中某个结点。 操作结果:若cure有右兄弟,则返回它的右兄弟,否则返回"空 TraverseTree(T, visit(); 初始条件:树T存在,vsi是对结点操作的应用函数 操作结果:按某种次序对T的每个结点调用函数vsi0一次且至多一次。一且vsit0失 败,则操作失败 {加工型操作} Assign(T, cur e, value); 初始条件:树T存在,cure是T中某个结点。 操作结果:结点cure赋值为 value 初始条件:树T存在
{销毁结构} DestroyTree(&T); 初始条件：树 T 存在。 操作结果：销毁树 T。 •{引用型操作} TreeEmpty(T); 初始条件：树 T 存在。 操作结果：若 T 为空树，则返回 TRUE，否则返回 FALSE。 TreeDepth(T); 初始条件：树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：树 T 存在。 操作结果：返回 T 的根。 Value(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：返回 cur_e 的值。 •Parent(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是 T 的非根结点，则返回它的双亲，否则返回"空"。 LeftChild(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 是 T 的非叶子结点，则返回它的最左孩子，否则返回"空"。 RightSibling(T, cur_e); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：若 cur_e 有右兄弟，则返回它的右兄弟，否则返回"空"。 TraverseTree(T, visit()); 初始条件：树 T 存在，visit 是对结点操作的应用函数。 操作结果：按某种次序对 T 的每个结点调用函数 visit() 一次且至多一次。一旦 visit() 失 败，则操作失败。 •{加工型操作} Assign(T, cur_e, value); 初始条件：树 T 存在，cur_e 是 T 中某个结点。 操作结果：结点 cur_e 赋值为 value。 ClearTree(&T); 初始条件：树 T 存在
操作结果:将树T清为空树。 InsertChild(&T,&p, i, c) 初始条件:树T存在,p指向T中某个结点,1≤长p所指结点的度+1,非空树c与 T不相交 操作结果:插入c为T中p所指结点的第i棵子树。 Delete Child (&T,&p, i); 初始条件:树T存在,p指向T中某个结点,1≤i≤p指结点的度。 操作结果:删除T中p所指结点的第i棵子树 3 ADT Tree 树和线性结构对照: 第二节二叉树类型 ·定义:二叉树是另一种树形结构。它与树形结构的区别是: (1)每个结点最多有两棵子树; (2)子树有左右之分 叉树也可以用递归的形式定义。即:二叉树是n(n≥0)个结点的有限集合。 当n=0时,称为空二叉树;当n>时,有且仅有一个结点为二叉树的根,其余结点被分成两个 互不相交的子集,一个作为左子集,另一个作为右子集,每个子集又是一个二叉树。 621二叉树的类型定义 ADT Binary Tree i 数据对象:D是具有相同特性的数据元素的集合 数据关系: 若D为空集,称 Binary Tree为空二叉树; 否则关系R={H} (1)在D中存在唯一的称为根的数据元素root,它在关系H下无前驱; (2)D中其余元素必可分为两个互不相交的子集L和R,每一个子集都是一棵符合本 定义的二叉树,并分别为root的左子树和右子树。如果左子树L不空,则必存在一个根结点, 它是root的"左后继"∈H),如果右子树R不空,则必存在一个根结点为root的 右后继"(∈H) °基本操作P 结构初始化} Init BiTree(&I 操作结果:构造空二叉树T。 Create BiTree(&T, definition); 初始条件: definition给出二叉树T的定义 操作结果:按 definition构造二叉树T。 销毁结构} Destroy BiTree(&T); 初始条件:二叉树T存在
操作结果：将树 T 清为空树。 InsertChild(&T, &p, i, c); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 所指结点的度＋1，非空树 c 与 T 不相交。 操作结果：插入 c 为 T 中 p 所指结点的第 i 棵子树。 DeleteChild(&T, &p, i); 初始条件：树 T 存在，p 指向 T 中某个结点，1≤i≤p 指结点的度。 操作结果：删除 T 中 p 所指结点的第 i 棵子树。 } ADT Tree 树和线性结构对照： 第二节 二叉树类型 •定义：二叉树是另一种树形结构。它与树形结构的区别是： • （1）每个结点最多有两棵子树； • （2）子树有左右之分。 • 二叉树也可以用递归的形式定义。即：二叉树是 n（n≥0）个结点的有限集合。 当 n=0 时，称为空二叉树；当 n>0 时，有且仅有一个结点为二叉树的根，其余结点被分成两个 互不相交的子集，一个作为左子集，另一个作为右子集，每个子集又是一个二叉树。 6.2.1 二叉树的类型定义 ADT BinaryTree { 数据对象：D 是具有相同特性的数据元素的集合。 数据关系： 若 D 为空集，称 BinaryTree 为空二叉树； 否则 关系 R={H}： (1) 在 D 中存在唯一的称为根的数据元素 root，它在关系 H 下无前驱； (2) D 中其余元素必可分为两个互不相交的子集 L 和 R，每一个子集都是一棵符合本 定义的二叉树，并分别为 root 的左子树和右子树。如果左子树 L 不空，则必存在一个根结点 ， 它是 root 的"左后继"(∈H)，如果右子树 R 不空，则必存在一个根结点 为 root 的 "右后继"(∈H)。 •基本操作 P： {结构初始化} InitBiTree(&T); 操作结果：构造空二叉树 T。 CreateBiTree(&T, definition); 初始条件：definition 给出二叉树 T 的定义。 操作结果：按 definition 构造二叉树 T。 {销毁结构} DestroyBiTree(&T); 初始条件：二叉树 T 存在
操作结果:销毁二叉树T °{引用型操作} BiTreeempty (t 初始条件:二叉树T存在。 操作结果:若T为空二叉树,则返回TRUE,否则返回 FALSE。 reeDepth(D); 初始条件:二叉树T存在。 操作结果:返回T的深度 Root(D); 初始条件:二叉树T存在 操作结果:返回T的根 Value(T, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的值。 ° Parent(T,e); 初始条件:二叉树T存在,e是T中某个结点 操作结果:若e是T的非根结点,则返回它的双亲,否则返回"空"。 LeftChild(t, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的左孩子。若e无左孩子,则返回”空"。 Right Child(t, e) 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的右孩子。若e无右孩子,则返回空”。 LeftSibling(t, e); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:返回e的左兄弟。若e是其双亲的左孩子或无左兄弟,则返回"空 · Rightsibling(T,e); 初始条件:二叉树T存在,e是T的结点。 操作结果:返回e的右兄弟。若e是其双亲的右孩子或无右兄弟,则返回"空 PreOrderTraverse(T, visitO); 初始条件:二叉树T存在,vsi是对结点操作的应用函数 操作结果:先序遍历T,对每个结点调用函数visi-次且仅一次。一且vsit0失败,则 操作失败 InOrderTraverse(T, sito); 初始条件:二叉树T存在,vsit是对结点操作的应用函数 操作结果:中序遍历T,对每个结点调用函数Ⅴi一次且仅一次。一且vsit(失败, 则操作失败
操作结果：销毁二叉树 T。 •{引用型操作} BiTreeEmpty(T); 初始条件：二叉树 T 存在。 操作结果：若 T 为空二叉树，则返回 TRUE，否则返回 FALSE。 BiTreeDepth(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的深度。 Root(T); 初始条件：二叉树 T 存在。 操作结果：返回 T 的根。 Value(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的值。 •Parent(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：若 e 是 T 的非根结点，则返回它的双亲，否则返回"空"。 LeftChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左孩子。若 e 无左孩子，则返回"空"。 RightChild(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的右孩子。若 e 无右孩子，则返回"空"。 LeftSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：返回 e 的左兄弟。若 e 是其双亲的左孩子或无左兄弟，则返回"空"。 •RightSibling(T, e); 初始条件：二叉树 T 存在，e 是 T 的结点。 操作结果：返回 e 的右兄弟。若 e 是其双亲的右孩子或无右兄弟，则返回"空"。 PreOrderTraverse(T, visit()); 初始条件：二叉树 T 存在,visit 是对结点操作的应用函数。 操作结果：先序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则 操作失败。 InOrderTraverse(T, vsit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：中序遍历 T，对每个结点调用函数 Visit 一次且仅一次。一旦 visit() 失败， 则操作失败
PostOrderTraverse(l, visitO); 初始条件:二叉树T存在,vsit是对结点操作的应用函数。 操作结果:后序遍历T对每个结点调用函数vsi一次且仅一次。一且 visit0失败,则 操作失败。 LevelOrderTraverse(T, visitO); 初始条件:二叉树T存在,vit是对结点操作的应用函数 操作结果:层序遍历T对每个结点调用函数vsi一次且仅一次。一且vsi0失败, 则操作失败。 {加工型操作} ClearBiTree(&T 初始条件:二叉树T存在 操作结果:将二叉树T清为空树 Assign(&t, &e, value); 初始条件:二叉树T存在,e是T中某个结点。 操作结果:结点e赋值为 value. Insert Child(&T, p, LR, c) 人,初始条件:二又树T存在,p指向T中某个结点,IR为0或1,非空二又树与 操作结果:根据LR为0或1,插入c为T中p所指结点的左或右子树。p所指 结点原有左或右子树成为c的右子树 Delete Child(&T, p, LR) 初始条件:二叉树T存在,p指向T中某个结点,LR为0或1 操作结果:根据LR为0或1,删除T中p所指结点的左或右子树。 3 ADT Binary Tree 622二叉树的几个特性 在二叉树的第i层上至多有21个结点(i≥1) 二、深度为k的二叉树中至多含有2k-1个结点,(k≥1) 三、对任何一棵二叉树T,如果其终端结点数为n,度为2的结点数为m,则 若二叉树中所有的分支结点的度数都为2,且叶子结点都在同一层次上,则称这类二叉树为满 二叉树 假如一棵包含n个结点的二叉树中每个结点都可以和满二叉树中编号为1至n的结点一、 对应,则称这类二叉树为完全二叉树。 第三节二叉树的存储表示 63.1顺序存储结构 二叉树的顺序存储结构的定义如下
PostOrderTraverse(T, visit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：后序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败，则 操作失败。 • LevelOrderTraverse(T, visit()); 初始条件：二叉树 T 存在，visit 是对结点操作的应用函数。 操作结果：层序遍历 T，对每个结点调用函数 visit 一次且仅一次。一旦 visit() 失败， 则操作失败。 {加工型操作} ClearBiTree(&T); 初始条件：二叉树 T 存在。 操作结果：将二叉树 T 清为空树。 Assign(&T, &e, value); 初始条件：二叉树 T 存在，e 是 T 中某个结点。 操作结果：结点 e 赋值为 value。 •InsertChild(&T, p, LR, c); 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1，非空二叉树 c 与 T 不相交且右子树为空。 • 操作结果：根据 LR 为 0 或 1，插入 c 为 T 中 p 所指结点的左或右子树。p 所指 结点原有左或右子树成为 c 的右子树。 DeleteChild(&T, p, LR); 初始条件：二叉树 T 存在，p 指向 T 中某个结点，LR 为 0 或 1。 操作结果：根据 LR 为 0 或 1，删除 T 中 p 所指结点的左或右子树。 } ADT BinaryTree 6.2.2 二叉树的几个特性 •一、在二叉树的第 i 层上至多有 2 i-1 个结点(i≥1)。 •二、深度为 k 的二叉树中至多含有 2 k -1 个结点，(k≥1)。 •三、对任何一棵二叉树 T，如果其终端结点数为 n0，度为 2 的结点数为 n2，则 n0 =n2+ 1 •若二叉树中所有的分支结点的度数都为 2，且叶子结点都在同一层次上，则称这类二叉树为满 二叉树。 •假如一棵包含 n 个结点的二叉树中每个结点都可以和满二叉树中编号为 1 至 n 的结点一、 一对应，则称这类二叉树为完全二叉树。 第三节 二叉树的存储表示 •6.3.1 顺序存储结构 •二叉树的顺序存储结构的定义如下：
const maXsize=100;∥暂定二叉树中结点数的最大值为100 typedef struct i ElemType*data;∥存储空间基址(初始化时分配空间) int nodeN ∥二叉树中结点数 3 Sq Bitree ∥二叉树的顺序存储结构 632链式存储结构 二叉树的二叉链表存储表示 typedef struct BiTNode ElemType data struct binOde *Lchild, Rchild;∥左、右孩子指针 3*BiTree; 二叉树的三叉链表存储表示 typedef struct TriTNode i struct BiTNode *Lchild,* Child;∥左、右孩子指针 struct BiTNode"parent ∥双亲指针 二叉树的双亲链表存储表示 typedef struct BPTNode i ∥结点结构 ElemType data int parent ∥指向双亲的指针 char lrtag ∥左、右孩子标志域 1 BPTNode 第四节二叉树的遍历 遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。 由于二叉树中每个结点都有两个后继,则可以有三条搜索路径 1)先左(子树)后右(子树); 2)先右(子树)左(子树); 3)按层次从上到下 641先左后右的遍历6-41遍历swf 先序遍历递归算法 void PreOrder(bTree BT) if (BT) Visit(BT); Pre Order(bT->Lchild); PreOrder(BT->Rchild); j 6-4-2-1.swf 中序遍历递归算法 void In Order(BTree BT) if (BT)i In Order(BT->lchild);
•const MAXSIZE = 100; // 暂定二叉树中结点数的最大值为 100 typedef struct { ElemType *data; // 存储空间基址(初始化时分配空间) int nodeNum; // 二叉树中结点数 } SqBiTree; // 二叉树的顺序存储结构 6.3.2 链式存储结构 •二叉树的二叉链表存储表示 •typedef struct BiTNode { ElemType data; struct BiTNode *Lchild, *Rchild;// 左、右孩子指针 } *BiTree; 二叉树的三叉链表存储表示 •typedef struct TriTNode { ElemType data; struct BiTNode *Lchild, *Rchild; //左、右孩子指针 struct BiTNode *parent; // 双亲指针 } *TriTree; 二叉树的双亲链表存储表示 •typedef struct BPTNode { // 结点结构 ElemType data; int *parent; // 指向双亲的指针 char LRTag; // 左、右孩子标志域 } BPTNode 第四节 二叉树的遍历 •“遍历”的含义是对结构中的每个数据元素都访问一次且仅仅访问一次。 •由于二叉树中每个结点都有两个后继，则可以有三条搜索路径： 1) 先左(子树)后右(子树)； 2) 先右(子树)后左(子树)； 3) 按层次从上到下。 6.4.1 先左后右的遍历 6-4-1 遍历.swf 先序遍历递归算法 •void PreOrder(BTree BT) • { • if (BT) { Visit(BT); • PreOrder(BT->Lchild); • PreOrder(BT->Rchild); } • } •6-4-2-1.swf 中序遍历递归算法 •void InOrder(BTree BT) •{ • if (BT) { • InOrder(BT->Lchild);
Visit(B); InOrder(bT->Rchild); °}6-4-2-2swf 后序遍历递归算法 void PostOrder(bTree BT) f(Br& PostOrder(bt->lchild PostOrder(BT->Rchild); 6-4-2-3.swf 按层次遍历二叉树 按层次遍历该二叉树的序列为: ABCDEFGH 二叉树用链式存储结构表示时,按层遍历的算法实现 (1)访问根结点,并将根结点入队; (2)当队列不空时,重复下列操作: 从队列退出一个结点 ●若其有左孩子,则访问左孩子,并将其左孩子入队; ●若其有右孩子,则访问右孩子,并将其右孩子入队; void LevelOrder(bTree"BT) f BT) exit; InitQueue(Q);p=BT;/初始化 Visite(p); EnQueue(&Q, p): ∥访问根结点,并将根结点入队 while( QueueEmpty(Q) ·∥当队非空时重复执行下列操作 DeQueue(&Q,&p);∥出队 {Ⅴ isite(p→> Lchild); En Queue(&Q,p-> Lchild);}∥处理左孩子 if c p->Rchild) Ⅴste(p> Rchild); EnQueue(&Q,p-> Rchild;}∥处理右孩子 .void Create BiTree(bitree i;{ ;/ OUiEDoteAu ]'aeE=uy" IODAtE p2eEp" TOxo.t'画"￡ ; io,oeltHA'pa士e: EDOXO-U'RODE ;×6·#±i为:OE士道XOA,×O,%aAEy2YOEO iii:cin>>ch￡
• Visit(BT); • InOrder(BT->Rchild); • } •} 6-4-2-2.swf 后序遍历递归算法 •void PostOrder(BTree BT) •{ • if (BT) { • PostOrder(BT->Lchild); • PostOrder(BT->Rchild); • Visit(BT); • } •} 6-4-2-3.swf 按层次遍历二叉树 • 按层次遍历该二叉树的序列为： • ABCDEFGH •二叉树用链式存储结构表示时，按层遍历的算法实现 •（1）访问根结点，并将根结点入队； •（2）当队列不空时，重复下列操作： ⚫从队列退出一个结点； ⚫若其有左孩子，则访问左孩子，并将其左孩子入队； ⚫若其有右孩子，则访问右孩子，并将其右孩子入队； •void LevelOrder(BTree *BT) •{ • if (!BT) exit; • InitQueue(Q); p=BT; //初始化 • Visite(p); EnQueue(&Q,p); • //访问根结点，并将根结点入队 • while (!QueueEmpty(Q)) • {//当队非空时重复执行下列操作 • DeQueue(&Q,&p); //出队 • if (!p->Lchild) •{ Visite(p->Lchild) ; EnQueue(&Q,p->Lchild); } //处理左孩子 • if (!p->Rchild) •{ Visite(p->Rchild);EnQueue(&Q,p->Rchild); } //处理右孩子 • } •} ½¨Á¢¶þ²æÊ÷ •void CreateBiTree(BiTree &T) ¡¡{ ¡¡¡¡// ÔÚÏÈÐò±éÀú¶þ²æÊ÷µÄ¹ý³ÌÖÐÊäÈë¶þ²æÊ÷µÄ"ÏÈÐò×Ö·û´®"£¬ ¡¡¡¡// ½¨Á¢¸ùÖ¸ÕëΪ TµÄ¶þ²æÁ´±í´æ´¢½á¹¹¡£ÔÚÏÈÐò×Ö·û´®ÖУ¬ ¡¡¡¡// ×Ö·û'#'±íʾ¿ÕÊ÷£¬Æ äËü×Öĸ×Ö·ûΪ½áµãµÄÊý¾ÝÔªËØ ¡¡¡¡cin >> ch £»
imm: if(ch==#)T=NULL; I :: //7"G OE gilels i ;!r= new binOde;∥"A"x-fE畝a iiiiiiT->data=ch; ; Create bitree(I> Lchild);/Ye±A山)x6×OE ;! CreateBitree(I-> Rchild);/μY'e/(eA)OO×OE iiii 统计二叉树中叶子结点的个数 .void CountLeaf (BiTree t, int& count) ∥先序遍历二叉树,以 count返回二叉树中叶子结点的数目 if(T)i if(T->Lchild)&&(T->Rchild)) count++: ∥对叶子结点计数 CountLeaf( T->Lchild, count); CountLeaf( T->Rchild, count) }∥if 求二叉树的深度 void BiTree Depth(BiTree T, int level, int &depth) T指向二叉树的根, level为T所指结点所在层次,其初值为1, depth为当前求得的最 大层次其初值为0 if if (level>depth)depth=level BiTreeDepth(T->Lchild, level+l, depth); BiTree Depth(T->Rchild, level+1, depth); }6-4-3求二叉树的深度sw 复制二叉树 生成一个二叉树的结点的算法 BiTNode*Get Node(TElem Type item, Bi TNode*Iptr, BiTNode*rptr) {生成一个其元素值为item,左指针为lpr,右指针为rptr的结点 T=new BiTNode: T-> data= item: T->Lchild=lptr; T->Rchild= rptr; return T 后序遍历复制二叉树的操作为 BiTNode* Copy Tree (BinOde*T ∥已知二叉树的根指针为T,本算法返回它的复制品的根指针 return NULL ∥复制一棵空树 if(T->Lchild) newlptr= Copy Tree(-> Lchild;∥复制(遍历左子树 else newlptr= NU
¡¡¡¡if (ch=='#') T=NULL;¡¡¡¡// ½¨¿ÕÊ÷ ¡¡¡¡else { ¡¡¡¡¡¡T = new BiTNode ; // "·ÃÎÊ"²Ù×÷ΪÉú³É¸ù½áµã ¡¡¡¡¡¡T->data = ch; ¡¡¡¡¡¡CreateBiTree(T->Lchild); ¡¡// µÝ¹é½¨(±éÀú)×ó×ÓÊ÷ ¡¡¡¡¡¡CreateBiTree(T->Rchild); ¡¡¡¡// µÝ¹é½¨(±éÀú)ÓÒ×ÓÊ÷ ¡¡¡¡} ¡¡} •6-4-6.swf 统计二叉树中叶子结点的个数 •void CountLeaf (BiTree T, int& count) { // 先序遍历二叉树，以 count 返回二叉树中叶子结点的数目 if ( T ) { if ((!T->Lchild)&& (!T->Rchild)) count++; // 对叶子结点计数 CountLeaf( T->Lchild, count); CountLeaf( T->Rchild, count); } // if } 求二叉树的深度 •void BiTreeDepth(BiTree T, int level, int &depth) {// T 指向二叉树的根，level 为 T 所指结点所在层次，其初值为 1，depth 为当前求得的最 大层次,其初值为 0 if (T){ if (level>depth) depth=level; BiTreeDepth(T->Lchild, level+1, depth); BiTreeDepth(T->Rchild, level+1, depth); } } 6-4-3 求二叉树的深度 .swf 复制二叉树 •生成一个二叉树的结点的算法： •BiTNode *GetTreeNode(TElemType item,BiTNode *lptr, BiTNode *rptr) {// 生成一个其元素值为 item，左指针为 lptr，右指针为 rptr 的结点 T = new BiTNode; T-> data = item; T-> Lchild = lptr; T-> Rchild = rptr; return T; } •后序遍历复制二叉树的操作为: •BiTNode *CopyTree(BiTNode *T) { // 已知二叉树的根指针为 T，本算法返回它的复制品的根指针 if (!T ) return NULL; // 复制一棵空树 if (T->Lchild) newlptr = CopyTree(T->Lchild); // 复制(遍历)左子树 else newlptr = NULL;
if(T->Rchild) newrptr= Copy Tree((I> Rchild);∥复制(历右子树 else newrptr= NULL newnode:= GetTreeNodel(I->daa, newlptr, newrptr);∥生成根结点 return newnode; 5复 a,aua void locate( BiTree T, ElemType x, BiTree& p) :// Eo ]- T OD'aeouoi x lai-HAOEOf-oo HA sOul NULL pO.loA%￡→iO0pμAO士涯p if T) iif if(T->data==x)p=Tf iii: locate (T-lchild, x, P); iiiilocate(T->rchild, x, P); 中序遍历(非递归) · Initstack(S) Push(S,D);∥根入栈 while(StackEmpty(s) while(get Top(s, p)&& p) Push(S,p-> lchild);/向左到尽头 Pop(S, p) ∥空指针出栈 if(Stack Empty(S)/问,向右 Pop(S, P) if( visit(p->data))return ERROR Push(S, p->rchild); return OK: 表达式的二叉树 二叉树的线索链表 °将在二叉树中每个结点(除第一个和最后一个外)的直接前驱和直接后继保存起来。这种信息 是在历的动态过程中产生的,如果将这些信息在第一次遍历时就保存起来,则在以后再次需 要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。 定义指针想,以tm表步分m typedef struct BiThrNodet ElemType data; struct BiThrNode *Lchild, Rchild;∥右指针 PointerType LTag,RIag;∥左右指针类型标志 )*BiThrTree 在线索链表中添加了一个”头结点”,头结点的左指针指向二叉树的根结点,其右线索指向中 序序列中的最后一个结点
if (T->Rchild) newrptr = CopyTree(T->Rchild); // 复制(遍历)右子树 else newrptr = NULL; newnode = GetTreeNode(T->data, newlptr, newrptr); // 生成根结点 return newnode; } 6-4-5 后序遍历复制.swf ÔÚ¶þ²æÊ÷Éϲéѯij¸ö½áµã •void locate(BiTree T,ElemType x,BiTree& p) { ¡¡// Èô¶þ²æÊ÷ T ÖдæÔÚºÍ x ÏàͬµÄÔªËØ£¬Ôò p Ö¸Ïò¸Ã½áµã£¬·ñÔò p µÄÖµ²»±ä£¬p µÄ³õֵΪ NULL ¡¡if (T) ¡¡{ if (T->data==x) p=T; ¡¡¡¡locate(T->lchild, x, p); ¡¡¡¡locate(T->rchild, x, p); ¡¡} } 中序遍历（非递归） •InitStack(S); Push(S,T); //根入栈 while(!StackEmpty(S)) { while(GetTop(S,p) && p) Push(S,p->lchild);//向左到尽头 Pop(S,p); //空指针出栈 if(!StackEmpty(S)) //访问，向右 { Pop(S,p); if(!Visit(p->data))return ERROR; Push(S,p->rchild); } } return OK; 表达式的二叉树 二叉树的线索链表 •将在二叉树中每个结点（除第一个和最后一个外）的直接前驱和直接后继保存起来。这种信息 是在遍历的动态过程中产生的，如果将这些信息在第一次遍历时就保存起来，则在以后再次需 要对二叉树进行“遍历”时就可以将二叉树视作线性结构进行访问操作了。 •typedef enum PointerType{ Link=0, Thread=1 }; // 定义指针类型，以 Link 表示指针，Thread 表示线索 typedef struct BiThrNode{ ElemType data; struct BiThrNode *Lchild, *Rchild; //左右指针 PointerType LTag, RTag; // 左右指针类型标志 } *BiThrTree; •在线索链表中添加了一个"头结点"，头结点的左指针指向二叉树的根结点，其右线索指向中 序序列中的最后一个结点
以中序线索链表为存储结构的中序遍历 void In Traverse Thr( BiThrTree T, void (Visit)(Elem Type e)) {∥T指向中序线索链表中的头结点,头结点的左指针 Lchild指向二叉树的根结点,头结 点的右线索 Child指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历,对 树中每个元素调用函数vsit进行访问操作 p=T->Lchild; ∥p指向二叉树的根结点 while(p]=T) ∥空树或遍历结束时,p= Thead while(p->LTag==Link)p=p->lchild; Visit(p->data); ∥访问其左子树为空的结点 while(p->RTag==Thread & p->Rchild!=T p=p> rchild; visit(p->data);∥访问“右线索”所指后继结点 p= p->Rchild; ∥Pp进至其右子树根 ·p=T-> Lchild; ∥p指向二叉树的根结点 while(!=T) ∥空树或遗历结束时,p= Thead while(p->LTag==Link)p=p->Lchild ∥访问其左子树为空的结点 while(p->RTag==Thread & p->Rchild =T) p=p> rchild;vsi(p→>data);∥访问“右线索所指后继结点 p= p->Rchild ∥p进至其右子树根 线索链表的生成 .void In Threading(biThrTree p, BiThrTree& pre) ∥对p指向根结点的二叉树进行中序遍历,遍历过程中进行“中序线索化”。若p所指结 点的左指针为空,则将它改为“左线索”,若pe所指结点的右指针为空,则将它改为“右线索 指针pre在遍历过程中紧随其后,即始终指向p所指结点在中序序列中的前驱 if (p)i Threading(> Lchild4me)∥对左子树进行线索化 if (p->Lchild) {p>LIag= Thread;p-> Lchild=pre;}∥建前驱线索 if (pre->Rchild) pre>RIag= Thread;pre-> Rchild=p;}∥建后继线索 pre- p; 保持pre指向p的前驱 n Threading(mp-> Rchild, pre)∥对右子树进行线索化 .void InOrderThreading( bithrTree &Th, BiThrTree Br ∥BT为指向二叉树根结点的指针,由此二叉链表建立二叉树的中序线索链表, Thead指 向线索链表中的头结点
以中序线索链表为存储结构的中序遍历 •void InOrderTraverse_Thr(BiThrTree T ,void (*Visit)(ElemType e)) {// T 指向中序线索链表中的头结点，头结点的左指针 Lchild 指向二叉树的根结点，头结 点的右线索 Rchild 指向中序遍历访问的最后一个结点。本算法对此二叉树进行中序遍历，对 树中每个元素调用函数 Visit 进行访问操作 p = T->Lchild; // p 指向二叉树的根结点 while (p!= T) { // 空树或遍历结束时，p==Thead while (p->LTag==Link) p = p->Lchild; Visit(p->data); // 访问其左子树为空的结点 while (p->RTag==Thread && p->Rchild!=T) { p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点 } p = p->Rchild; // p 进至其右子树根 } } •p = T->Lchild; // p 指向二叉树的根结点 while (p!= T) •{ // 空树或遍历结束时，p==Thead while (p->LTag==Link) p = p->Lchild; Visit(p->data); // 访问其左子树为空的结点 while (p->RTag==Thread && p->Rchild!=T) • { p = p->rchild; Visit(p->data); // 访问“右线索”所指后继结点 } p = p->Rchild; // p 进至其右子树根 } 6-5-1.swf 线索链表的生成 •void InThreading(BiThrTree p，BiThrTree& pre) { // 对 p 指向根结点的二叉树进行中序遍历，遍历过程中进行“中序线索化”。若 p 所指结 点的左指针为空，则将它改为“左线索”，若 pre 所指结点的右指针为空，则将它改为“右线索”。 指针 pre 在遍历过程中紧随其后，即始终指向 p 所指结点在中序序列中的前驱。 if (p) { InThreading(p->Lchild, pre); // 对左子树进行线索化 if (!p->Lchild) { p->LTag = Thread; p->Lchild = pre; } // 建前驱线索 if (!pre->Rchild) { pre->RTag = Thread; pre->Rchild = p; } // 建后继线索 pre = p; // 保持 pre 指向 p 的前驱 InThreading(p->Rchild, pre); // 对右子树进行线索化 } } •void InOrderThreading(BiThrTree &Th, BiThrTree BT) { // BT 为指向二叉树根结点的指针，由此二叉链表建立二叉树的中序线索链表，Thead 指 向线索链表中的头结点
