第6章树和二叉树数据结构.ppt

《第6章树和二叉树数据结构.ppt》由会员分享，可在线阅读，更多相关《第6章树和二叉树数据结构.ppt（185页珍藏版）》请在三一文库上搜索。

1、第5章 树,2019/3/12,2,第6章 树,6.1 树的概念及操作 6.2 二叉树 6.2.1 二叉树的概念及操作 6.2.2 二叉树的性质 6.2.3 二叉树的存储结构 6.3 二叉树的遍历 6.4 线索二叉树 6.5 树和森林 6.5.1 树的存储结构 6.5.2 森林、树、二叉树的相互转换 6.5.3 树和森林的遍历 6.6 哈夫曼树及其应用 6.6.1 最优二叉树(哈夫曼树) 6.6.2 哈夫曼编码 *6.7算法设计举例,2019/3/12,3,主要内容,知识点 树和二叉树定义 二叉树的性质，存储结构 二叉树的遍历及遍历算法的应用 * 线索二叉树 二叉树和树及森林的关系 Huffm

2、an树与Huffman编码 重点难点 二叉树的性质及应用 二叉树的遍历算法及应用 * 线索二叉树的算法 Huffman树的构造方法 树的算法,2019/3/12,4,树例与特征,社会的组织结构 家族的族谱 计算机中的目录组织,描述层次结构，是一种一对多的逻辑关系,2019/3/12,5,树的定义,树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。 （注：有人定义树不能为空） 有且仅有一个称为根的结点（Root）； n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树(SubTree),2019/3/12,6,树的定义,树的递归定义的各

3、子树T1,T2,Tm的相对次序是重要的，即树是有序的。,2019/3/12,7,树定义(图示),T1,T2,T3,2019/3/12,8,树的抽象数据类型的定义,ADT Tree 数据对象 D：D是具有相同特性的数据元素的集合。 数据关系 R：若D为空集，则称为空树； 若D仅含有一个数据元素，则R为空集，否则R=H，H是如下定义的二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root,则存在D-root的一个划分D1，D2,Dm（m0）,对任意jk(1j,km)有DjDk=,且对任意的i(1 i m ),存在唯一数据元素xi Di ,H; （3）

4、对应于D-root的划分，H-,有唯一的一个划分H1, H2,Hm(m0),对任意jk(1j,km)有HjHk=,且对任意i(1 i m )，Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。 （转下页）,2019/3/12,9,Tree (); Tree (); BuildRoot (const T /在结点 p 下插入值为 value 的新子女, 若插 /入失败, 函数返回false, 否则返回true,树的抽象数据类型(续),bool DeleteChild (position p, int i); /删除结点 p 的第 i 个子女及其全部子孙结 /点,

5、若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); /删除以 t 为根结点的子树 bool IsEmpty (); /判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p); /遍历以 p 为根的子树 ADT Tree,2019/3/12,10,树的抽象数据类型(续),2019/3/12,11,树的其它表示方式,凹入表示,嵌套集合,广义表,A(B(E,F),C,D(G(J),H,I),2019/3/12,12,结点：一个数据元素及若干指向其子树的分

6、支； 结点的度：结点拥有的子树的数目。 树的度：树内各结点的度的最大值； 叶子（终端结点）：度为0的结点； 分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点； 孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。,树的概念,2019/3/12,13,概念,祖先：从根结点到该结点所经分支上的所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。 层次：结点在树结构中的层（一般定义根为1层）。 深度：树中结点的最大层次称为树的深度。 有序树：结点的子树在树中的位置固定，不能互换，称有

7、序树。 无序树：子树在树中的位置可以互换。 树的度：结点度的最大值 森林：m(m0)棵互不相交的树的集合。,2019/3/12,14,概念示例,结点 结点的度(Degree) 叶子（Leaf)或终端结点 分支结点或非终端结点 树的度 层次(Level) 树的深度(Depth) 孩子（child) 双亲（Parent) 兄弟(Sibling) 祖先 子孙,树的示例,2019/3/12,15,自测题 1,n(n0)个结点的树的高度: 最低是多少？ 最高是多少？,2019/3/12,16,二叉树的概念,二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右

8、子树所组成的非空树，左子树和右子树同样也都是二叉树 特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。,2019/3/12,17,二叉树的抽象数据类型,ADT BinaryTree 数据对象D：D是具有相同特性的数据元素的集合。 数据关系R：若D=，则R=，称二叉树为空二叉树； 若D，则R=H，H是如下二元关系： （1）在D中存在唯一的称为根的数据元素root，它在关系H下无前驱； （2）若D-root,则存在D-root=D1,Dr,且 D1Dr； （3）若D1，则D1中存在唯一的元素x1,H,且存在D1上的关系H1H；若Dr,则Dr

9、中存在唯一的元素xr, H, 且存在Dr上的关系HrH；H=, H1, Hr; （4）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树， （Dr，Hr）是一棵符合本定义的二叉树，称为根的右子树。 基本操作如下：,2019/3/12,18,二叉树的抽象数据类型(续),BinTreeNode *Parent (BinTreeNode *t); /求结点 t 的双亲 BinTreeNode *LeftChild (BinTreeNode *t); /求结点 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t);/求结点 t 的右子女 BinTreeNo

10、de *getRoot (); /取根 void preOrder (void (*visit) (BinTreeNode *t);/前序遍历, visit是访问函数 void inOrder (void (*visit) (BinTreeNode *t);/中序遍历, visit是访问函数 void postOrder (void (*visit) (BinTreeNode *t); /后序遍历, (*visit)是访问函数 void levelOrder (void (*visit)(BinTreeNode *t); /层次序遍历, visit是访问函数 int Height ();/求树

11、深度或高度 int Size ();/求树中结点个数 bool Insert (T item); /在树中插入新元素 bool Remove (T item); /在树中删除元素 bool Find (T /取得结点数据 ADT BinaryTree,2019/3/12,19,二叉树的五种形态,2019/3/12,20,二叉树的性质,1.一个非空二叉树的第i层上至多有2i-1个结点（i1） 证明：i = 1, 只有根结点，显然成立 设i = k时成立，最多有2k-1个结点 当i= k+1时，最多的结点个数： 2k-1 * 2 = 2k-1+1 = 2k = 2( k+1)-1,2019/3/1

12、2,21,2.深度为k的二叉树至多有2k-1个结点(k1),二叉树的性质(续),证明：二叉树的结点个数为： 1 + 2 + + 2k-1= 2k-1,2019/3/12,22,二叉树的性质(续),3.对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。,证明：设n1为T中度为1的结点数，则总结点数： n = n0 + n1 + n2 (1) 另：除根结点外，所有结点都有且仅有一个双亲结点，也就是仅有一个分支进入，若B为分支数，则 n=B+1 =n1 + 2 * n2+1 (2) 由(1)和(2)有： n1 + 2 * n2 1 = n0 + n1 + n2 故

13、n0 = n2 + 1;,2019/3/12,23,满二叉树,满二叉树：深度为k且有2k-1个结点的二叉树,满二叉树,考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。,2019/3/12,24,完全二叉树,完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。,完全二叉树,2019/3/12,25,完全二叉树的树形特征,特征： 叶子结点只可能在层次最大的两层上出现。 任一结点，若其左分支下的子孙的最大层次为l，则其右分支下的最大层次为l或l-1，即若结点无左子女，

14、决不应有右子女。,2019/3/12,26,完全二叉树的特性（1）,1.具有n个结点的完全二叉树的深度: k =,证明：假设n个结点的完全二叉树的深度为k，则n的值应大于深度为k-1的满二叉树的结点数2k-1-1，小于等于深度为k的满二叉树的结点数2k-1，即 2k-1-1n2k-1 进一步可推导出 2k-1n+12k 两边取对数后，有 k-1log2(n+1)k 因为k是整数，所以有k,2019/3/12,27,完全二叉树的特性（2）,2.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,n,则对任一结点i（1in）有 （a）如果i=1,此结点为根结点，无双亲

15、；若i1,则其双亲结点是i/2。 （b）如果2in,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。 （c）如果2i+1n，则结点i无右孩子，否则其右孩子是结点2i+1。,2019/3/12,28,完全二叉树的特性（2）的示意图,2019/3/12,29,完全二叉树的特性（2）的示意图,2019/3/12,30,自测题 2,n(n0)个结点的二叉树的高度: 最低是多少？ 最高是多少？,2019/3/12,31,自测题 3,有关二叉树下列说法正确的是（ ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 【南京理工大学 2

16、000 一.11 （1.5分）】,2019/3/12,32,自测题,5. 已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是 A. 39 B. 52 C. 111 D. 119 【2009年全国硕士研究生入学计算机学科专业基础综合试题】,2019/3/12,33,完全二叉树性质的推论,n个结点的完全二叉树中： 度为1的结点数为(n+1)%2; 度为0的结点数为 (n+1)/2； 度为2的结点数为 (n+1)/2-1； 编号最大的分支结点是n/2； 编号最小的叶子结点是n/2+1。 n个结点的二叉树： 高最多为n； 最低为 （完全二叉树）。,2019/3/12

17、,34,树的叶子数与其它结点数的关系,设度为m的树中度为0,1,2,m的结点数分别为n0, n1, n2, nm，结点总数为n，分枝数为B，则下面二式成立 n= n0+ n1+n2+nm (1) n=B+1= n1+2n2 +mnm (2) 由(1)和(2)得叶子结点数n0=1+,2019/3/12,35,二叉树的存储结构,顺序存储结构 链式存储结构,2019/3/12,36,二叉树的顺序存储结构,整个二叉树可以按照从上到下，从左到右的顺序编号； 对于满/完全二叉树，可以从根结点开始按序号存放； 对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点为“虚结点”。,2019/3/1

18、2,37,顺序存储结构举例,完全二叉树,2019/3/12,38,顺序存储结构举例,一般二叉树,2019/3/12,39,顺序存储结构举例,A,B,C,非完全二叉树,X,2019/3/12,40,二叉树的链式存储结构,二叉链表 三叉链表 （线索链表）,data,lchild rchild,data,lchild rchild,parent,2019/3/12,41,链式存储结构示例,二叉链表,三叉链表,42,二叉树的类定义,/构造函数 lefttemplate struct BinTreeNode /二叉树结点类定义 T data; /数据域 BinTreeNode *leftChild, *

19、rightChild; /左子女、右子女链域 BinTreeNode () Child = NULL; rightChild = NULL; BinTreeNode (T x, BinTreeNode *l = NULL, BinTreeNode *r = NULL) data = x; leftChild = l; rightChild = r; ;,43,template class BinaryTree /二叉树类定义 public: BinaryTree () : root (NULL) /构造函数 BinaryTree (T value) : RefValue(value), roo

20、t(NULL) /构造函数 BinaryTree (BinaryTree /求结点数,44,BinTreeNode *Parent (BinTreeNode *t) return (root = NULL | root = t) ? NULL : Parent (root, t); /返回双亲结点 BinTreeNode *LeftChild (BinTreeNode *t) return (t != NULL)？t-leftChild : NULL; /返回左子女 BinTreeNode *RightChild (BinTreeNode *t) return (t != NULL)？t-ri

21、ghtChild : NULL; /返回右子女 BinTreeNode *getRoot () const return root; /取根,45,void preOrder (void (*visit) (BinTreeNode *t) preOrder (root, visit); /前序遍历 void inOrder (void (*visit) (BinTreeNode *t) inOrder (root, visit); /中序遍历 void postOrder (void (*visit) (BinTreeNode *t) postOrder (root, visit); /后序遍

22、历 void levelOrder (void (*visit)(BinTreeNode *t); /层次序遍历 int Insert (const T item); /插入新元素 BinTreeNode *Find (T item) const; /搜索,46,protected: BinTreeNode *root; /二叉树的根指针 T RefValue; /数据输入停止标志 void CreateBinTree (istream /查找,47,BinTreeNode *Copy (BinTreeNode *r); /复制 int Height (BinTreeNode *subTree

23、); /返回树高度 int Size (BinTreeNode *subTree); /返回结点数 BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); /返回父结点 BinTreeNode *Find (BinTreeNode * subTree, T /搜寻x,48,void Traverse (BinTreeNode *subTree, ostream /后序遍历,2019/3/12,49,自测题 4,一棵124个叶结点的完全二叉树，最多有( )个结点。 A.247 B.248 C.249; D.250; E.251 【

24、中国科学技术大学1995十四.3(2分)】,2019/3/12,50,自测题 5,已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。 A. 311 B. 312 C. 313 D. 314 E. 其它 【上海交通大学2005四.6(2分)】,2019/3/12,51,自测题 6,一个具有1025个结点的二叉树的高h为（ ） A11 B10 C11至1025之间 D10至1024之间 【南京理工大学1999 一.19(2分)】,2019/3/12,52,自测题 7,一棵树高为K的完全二叉树至少有（ ）个结点 A. 2k 1 B. 2k-1 1 C. 2k-1 D. 2k 【南京理工

25、大学 1998 一.3 （2分）】,2019/3/12,53,自测题 8,已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。 【厦门大学 2000 六.2 （16%/3分）】,2019/3/12,54,二叉树的遍历,二叉树的遍历的定义： 按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的操作。 遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系。 一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序列

26、唯一确定。,2019/3/12,55,二叉树的遍历,前序遍历二叉树 中序遍历二叉树 后序遍历二叉树,若二叉树为空，则空操作，否则：,层次遍历二叉树,2019/3/12,56,D L R,D L R,D L R,D L R,前序遍历序列：A B D C,前序遍历,2019/3/12,57,L D R,L D R,L D R,L D R,中序遍历序列：B D A C,中序遍历,2019/3/12,58,L R D,L R D,L R D,L R D,后序遍历序列： D B C A,后序遍历,2019/3/12,59,层次遍历序列： A B C D,层次遍历,2019/3/12,60,遍历图例,中序

27、序列为：DBEACF,前序序列为：ABDECF,后序序列为：DEBFCA,2019/3/12,61,自测题,3. 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是 A. LRN B. NRL C. RLN D. RNL 【2009年全国硕士研究生入学计算机学科专业基础综合试题】,2019/3/12,62,中序遍历二叉树的递归算法,template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode

28、*t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍历左子树 visit (subTree); /访问根结点 InOrder (subTree-rightChild, visit); /遍历右子树 ;,2019/3/12,63,图例,64,二叉树递归的前序遍历算法,template void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree); /访问

29、根结点 PreOrder (subTree-leftChild, visit); /遍历左子树 PreOrder (subTree-rightChild, visit); /遍历右子树 ;,65,二叉树递归的后序遍历算法,template void BinaryTree:PostOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t ) if (subTree != NULL ) PostOrder (subTree-leftChild, visit); /遍历左子树 PostOrder (subTree-rightChild,

30、visit); /遍历右子树 visit (subTree); /访问根结点 ;,2019/3/12,66,递归遍历举例,前序序列：abdefcg 中序序列：dfebagc 后序序列：fedbgca,前序序列：abcdef 中序序列：cbefda 后序序列：cfedba,67,template int BinaryTree:Size (BinTreeNode * subTree) const /私有函数：利用二叉树后序遍历算法计算二叉 /树的结点个数 if (subTree = NULL) return 0; /空树 else return 1+Size (subTree-leftChild)

31、 + Size (subTree-rightChild); ;,应用二叉树遍历的事例,68,template int BinaryTree:Height ( BinTreeNode * subTree) const /私有函数：利用二叉树后序遍历算法计算二叉 /树的高度或深度 if (subTree = NULL) return 0; /空树高度为0 else int i = Height (subTree-leftChild); int j = Height (subTree-rightChild); return (i j) ? j+1 : i+1; ;,69,利用二叉树前序遍历建立二叉树

32、,以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在RefValue中。例如用“”或用“-1”表示字符序列或正整数序列空结点。,70,如图所示的二叉树的前序遍历顺序为 A B C D E G F ,71,template void BinaryTree:CreateBinTree (ifstream,72,CreateBinTree (in, subTree-leftChild); /递归建立左子树 CreateBinTree (in, subTree-rightChild); /递归建立右子树 else

33、 subTree = NULL; /封闭指向空子树的指针 ;,2019/3/12,73,二叉树的中序非递归遍历,设S为一个栈，t为指向根结点的指针， 其处理过程为： （1）当t非空时，将t所指结点的地址进栈，并将t指向该结点的左子树； （2）当t为空时，弹出栈顶元素，显示结点元素，并将t指向该结点的右子树； （3）重复（1）、（2）步骤，直到栈空且t 也为空。,2019/3/12,74,非递归中序遍历栈S的变化,结束,2019/3/12,75,中序非递归遍历 算法,template void BinaryTree: InOrder (void (*visit) (BinTreeNode *t)

34、 stack* S; BinTreeNode *p = root; do while (p != NULL) /遍历指针向左下移动 S.Push (p); /该子树沿途结点进栈 p = p-leftChild; if (!S.IsEmpty() /栈不空时退栈 S.Pop (p); visit (p); /退栈, 访问 p = p-rightChild; /遍历指针进到右子女 while (p != NULL | !S.IsEmpty (); ;,76,在后序遍历过程中所用栈的结点定义 template struct stkNode BinTreeNode *ptr; /树结点指针 enum

35、tag L, R; /退栈标记 stkNode (BinTreeNode *N = NULL) : ptr(N), tag(L) /构造函数 ; tag = L, 表示从左子树退回还要遍历右子树; tag = R，表示从右子树退回要访问根结点。,利用栈的后序遍历非递归算法,77,78,后序遍历的非递归算法,template void BinaryTree: PostOrder (void (*visit) (BinTreeNode *t) Stack S; stkNode w; BinTreeNode * p = root; /p是遍历指针 do while (p != NULL) w.ptr

36、 = p; w.tag = L; S.Push (w); p = p-leftChild; int continue1 = 1; /继续循环标记, 用于R,79,while (continue1 ,2019/3/12,80,二叉树结构的性质,已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树。 已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树； 已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树； 已知二叉树的层次序列和中序序列，可以唯一确定一棵二叉树。,2019/3/12,81,自测题 9 构造二叉树,已知二叉树的 先序序列ABDFCEHG 中序序列DBFAHECG 请构造该二

37、叉树。,2019/3/12,82,自测题 10 构造二叉树,已知二叉树的 后序序列DMFBHELGCA 中序序列DBMFAHECGL 请构造该二叉树。,2019/3/12,83,自测题 11,一棵二叉树的先序、中序和后序序列如下，其中有部分未标出，试构造出该二叉树。 先序序列为：_ _ C D E _ G H I _ K 中序序列为：C B _ _ F A _ J K I G 后序序列为： _ E F D B _ J I H _ A 【电子科技大学2001三.1(5分)】 【厦门大学2002七.1(6分)】,2019/3/12,84,自测题 12 构造二叉树,试找出满足下列条件的二叉树 1）先

38、序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同,2019/3/12,85,自测题 13,一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。 ACABDEFG BABCDEFG CDACEFBG DADCFEGB 【北京工业大学2001一.2(2分)】,2019/3/12,86,自测题 14,一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个 【中南大学2005一

39、.7(2分)】,2019/3/12,87,自测题 15,某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树 A空或只有一个结点 B. 高度等于其结点数 C任一结点无左孩子 D. 任一结点无右孩子 【东华大学2003二.1(1分)】,2019/3/12,88,表达式的二叉树表示,用二叉树可以表示表达式,前序遍历：*+ab*c+def+gh 中序遍历：a+b+c*d+e+f*g+h 后序遍历：ab+cde+*+f+gh+*,表达式: (a+b)+c*(d+e)+f)*(g+h),2019/3/12,89,算法举例6.1 求二叉树深度,以二叉链表作存储结构，试编写求二叉树深度的算法

40、。 int BinTreeDepth(BiTree T) if(T=NULL) return 0; elsel=BinTreeDepth(T-lchild); r=BinTreeDepth(T-rchild); return(lr? l+1 :r+1); ,2019/3/12,90,算法举例6.2 求二叉树的叶子数(1),以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。 int LeafCount(BiTree T) if(!T) return 0; /空树没有叶子 else if(!T-lchild /左子树叶子数加上右子树叶子数 ,2019/3/12,91,算法举例6.2 求二叉树的

41、叶子数(2),以二叉链表作为存储结构，试编写求二叉树中 叶子数的算法。 int num=0; void LeafCount(BiTree T) if(T) LeafCount(T-lchild) ; /中序遍历左子树 if(!T-lchild /中序遍历右子树 ,2019/3/12,92,算法举例6.3 交换二叉树的子树,以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。 void change(BiTree T) if(T!=NULL) change(T-lchild); change(T-rchild); t=T-lchild; T-lchild=T-rchild; T-r

42、child=t; ,2019/3/12,93,算法举例6.4 以二叉链表作为存储 结构，设计算法拷贝二叉树。,BiTree copy(BiTree T) BiTree T1; if(T=null) T1=null; else T1=(BiTree)malloc(sizeof(BiNode); /申请结点 T1-data=T-data; T1-lchild=copy(T-lchild); T1-rchild=copy(T-rchild); return T1; ,2019/3/12,94,算法举例6.5 由顺序存储的n个结点的完全二叉树建立二叉链表存储的二叉树,BiTree creat(Elem

43、Type A ,int i) BiTree T; if(in) T=null; else T=(BiTree)malloc(sizeof(BiNode); /申请结点 T-data=Ai; T-lchild=creat(A,2*i); T-rchild=creat(A,2*i+1); return T; /初始调用：p=creat(A,1);,2019/3/12,95,void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2) /根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。 ro

44、ot=(BiTree)malloc(sizeof(BiNode); /申请结点 root-data=prel1; /prel1是根 for(i=l2;ilchild=null; /无左子树 else PreInCreat(root-lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)； /递归建立/左子树 if(i=h2) root-rchild=null; /无右子树 else PreInCreat(*root)-rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2) /递归建/立右子树 /结束PreInCreat,算法举例6.6 设一棵二叉树中各结点的

45、值互不相同，其前序序列和中序序列分别存于两个一维数组pre1n 和mid1n 中，试遍写算法建立该二叉树的二叉链表。,2019/3/12,96,线索二叉树,线索二叉树的提出： 1、遍历的实质：非线性结构线性化（前驱、后继）; 2、前驱和后继是在遍历中得到的; 3、知道前驱和后继，再遍历时就不需要栈; 4、可以在二叉链表结构中增加前驱和后继两个指针域; 5、n个结点的二叉树有n1个空指针，可以利用。,2019/3/12,97,线索二叉树,n个结点的二叉链表中含有n+1个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息,这样的指针称为“线索”，加上了线索的二叉链表称为线索链表，加上线索的

46、二叉树就是线索二叉树（Threaded Binary Tree）。将二叉树变为线索二叉树的过程称为线索化。,ltag=,rtag=,2019/3/12,98,线索二叉树,线索化,只有空指针才能加线索,2019/3/12,99,前序前驱线索化,前序前驱线索化,2019/3/12,100,中序（全）线索二叉树,NULL,为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，rchild域指向访问序列的最后一个结点，这样，就建立了一个双向线索链表。,2019/3/12,101,后序（全）线索化,2019/3/12,102,线索链表的类型定义,typedef struct BiThrNode ElemTyte data; struct BiThrNode *lchild, *rchild;左、右孩子指针 int ltag, rtag; BiThrNode，*BiThrTree,2019/3/12,103,算法举例6.7 中序线索化,BiThrTree