树和二叉树数据结构.ppt

第5章 树,2019/5/18,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/5/18,3,主要内容,知识点 树和二叉树定义 二叉树的性质，存储结构 二叉树的遍历及遍历算法的应用 * 线索二叉树 二叉树和树及森林的关系 Huffman树与Huffman编码 重点难点 二叉树的性质及应用 二叉树的遍历算法及应用 * 线索二叉树的算法 Huffman树的构造方法 树的算法,2019/5/18,4,树例与特征,社会的组织结构 家族的族谱 计算机中的目录组织,描述层次结构，是一种一对多的逻辑关系,2019/5/18,5,树的定义,树(Tree)是n(n=0)个结点的有限集。n=0时称为空树。 （注：有人定义树不能为空） 有且仅有一个称为根的结点（Root）； n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树(SubTree),2019/5/18,6,树的定义,树的递归定义的各子树T1,T2,Tm的相对次序是重要的，即树是有序的。,2019/5/18,7,树定义(图示),T1,T2,T3,2019/5/18,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）对应于D-root的划分，H-,有唯一的一个划分H1, H2,Hm(m0),对任意jk(1j,km)有HjHk=,且对任意i(1 i m )，Hi是Di上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根root的子树。 （转下页）,2019/5/18,9,Tree (); Tree (); BuildRoot (const T /在结点 p 下插入值为 value 的新子女, 若插 /入失败, 函数返回false, 否则返回true,树的抽象数据类型(续),bool DeleteChild (position p, int i); /删除结点 p 的第 i 个子女及其全部子孙结 /点, 若删除失败, 则返回false, 否则返回true void DeleteSubTree (position t); /删除以 t 为根结点的子树 bool IsEmpty (); /判树空否, 若空则返回true, 否则返回false void Traversal (void (*visit)(position p); /遍历以 p 为根的子树 ADT Tree,2019/5/18,10,树的抽象数据类型(续),2019/5/18,11,树的其它表示方式,凹入表示,嵌套集合,广义表,A(B(E,F),C,D(G(J),H,I),2019/5/18,12,结点：一个数据元素及若干指向其子树的分支； 结点的度：结点拥有的子树的数目。 树的度：树内各结点的度的最大值； 叶子（终端结点）：度为0的结点； 分支结点（非终端结点）：度不为0的结点；除根结点外，也称内部结点； 孩子，双亲，兄弟，堂兄：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。,树的概念,2019/5/18,13,概念,祖先：从根结点到该结点所经分支上的所有结点。 子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。 层次：结点在树结构中的层（一般定义根为1层）。 深度：树中结点的最大层次称为树的深度。 有序树：结点的子树在树中的位置固定，不能互换，称有序树。 无序树：子树在树中的位置可以互换。 树的度：结点度的最大值 森林：m(m0)棵互不相交的树的集合。,2019/5/18,14,概念示例,结点 结点的度(Degree) 叶子（Leaf)或终端结点 分支结点或非终端结点 树的度 层次(Level) 树的深度(Depth) 孩子（child) 双亲（Parent) 兄弟(Sibling) 祖先 子孙,树的示例,2019/5/18,15,自测题 1,n(n0)个结点的树的高度: 最低是多少？ 最高是多少？,2019/5/18,16,二叉树的概念,二叉树(Binary Tree)：或者是一棵空树，或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子树和右子树同样也都是二叉树 特征： 每个结点最多只有两棵子树 子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清是左、右子树。,2019/5/18,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中存在唯一的元素xr, H, 且存在Dr上的关系HrH；H=, H1, Hr; （4）（D1，H1）是一棵符合本定义的二叉树，称为根的左子树， （Dr，Hr）是一棵符合本定义的二叉树，称为根的右子树。 基本操作如下：,2019/5/18,18,二叉树的抽象数据类型(续),BinTreeNode *Parent (BinTreeNode *t); /求结点 t 的双亲 BinTreeNode *LeftChild (BinTreeNode *t); /求结点 t 的左子女 BinTreeNode *RightChild (BinTreeNode *t);/求结点 t 的右子女 BinTreeNode *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 ();/求树深度或高度 int Size ();/求树中结点个数 bool Insert (T item); /在树中插入新元素 bool Remove (T item); /在树中删除元素 bool Find (T /取得结点数据 ADT BinaryTree,2019/5/18,19,二叉树的五种形态,2019/5/18,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/5/18,21,2.深度为k的二叉树至多有2k-1个结点(k1),二叉树的性质(续),证明：二叉树的结点个数为： 1 + 2 + + 2k-1= 2k-1,2019/5/18,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 故 n0 = n2 + 1;,2019/5/18,23,满二叉树,满二叉树：深度为k且有2k-1个结点的二叉树,满二叉树,考虑到有序性，任一结点在树中都有确切的位置，因此可以对满二叉树进行编号。编号方式为：从上到下，从左到右。,2019/5/18,24,完全二叉树,完全二叉树：深度为k，有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树编号从1到n的结点一一对应时，称为完全二叉树。,完全二叉树,2019/5/18,25,完全二叉树的树形特征,特征： 叶子结点只可能在层次最大的两层上出现。 任一结点，若其左分支下的子孙的最大层次为l，则其右分支下的最大层次为l或l-1，即若结点无左子女，决不应有右子女。,2019/5/18,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/5/18,27,完全二叉树的特性（2）,2.如果将一棵有n个结点的完全二叉树自顶向下，同一层自左向右连续给结点编号1,2,3,n,则对任一结点i（1in）有 （a）如果i=1,此结点为根结点，无双亲；若i1,则其双亲结点是i/2。 （b）如果2in,则结点i无左孩子，i为叶子结点,否则其左孩子是结点2i。 （c）如果2i+1n，则结点i无右孩子，否则其右孩子是结点2i+1。,2019/5/18,28,完全二叉树的特性（2）的示意图,2019/5/18,29,完全二叉树的特性（2）的示意图,2019/5/18,30,自测题 2,n(n0)个结点的二叉树的高度: 最低是多少？ 最高是多少？,2019/5/18,31,自测题 3,有关二叉树下列说法正确的是（ ） A二叉树的度为2 B一棵二叉树的度可以小于2 C二叉树中至少有一个结点的度为2 D二叉树中任何一个结点的度都为2 【南京理工大学 2000 一.11 （1.5分）】,2019/5/18,32,自测题,5. 已知一棵完全二叉树的第6层（设根是第1层）有8个叶结点，则该完全二叉树的结点个数最多是 A. 39 B. 52 C. 111 D. 119 【2009年全国硕士研究生入学计算机学科专业基础综合试题】,2019/5/18,33,完全二叉树性质的推论,n个结点的完全二叉树中： 度为1的结点数为(n+1)%2; 度为0的结点数为 (n+1)/2； 度为2的结点数为 (n+1)/2-1； 编号最大的分支结点是n/2； 编号最小的叶子结点是n/2+1。 n个结点的二叉树： 高最多为n； 最低为 （完全二叉树）。,2019/5/18,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/5/18,35,二叉树的存储结构,顺序存储结构 链式存储结构,2019/5/18,36,二叉树的顺序存储结构,整个二叉树可以按照从上到下，从左到右的顺序编号； 对于满/完全二叉树，可以从根结点开始按序号存放； 对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点为“虚结点”。,2019/5/18,37,顺序存储结构举例,完全二叉树,2019/5/18,38,顺序存储结构举例,一般二叉树,2019/5/18,39,顺序存储结构举例,A,B,C,非完全二叉树,X,2019/5/18,40,二叉树的链式存储结构,二叉链表 三叉链表 （线索链表）,data,lchild rchild,data,lchild rchild,parent,2019/5/18,41,链式存储结构示例,二叉链表,三叉链表,42,二叉树的类定义,/构造函数 lefttemplate struct BinTreeNode /二叉树结点类定义 T data; /数据域 BinTreeNode *leftChild, *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), root(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-rightChild : 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); /后序遍历 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); /返回树高度 int Size (BinTreeNode *subTree); /返回结点数 BinTreeNode *Parent (BinTreeNode * subTree, BinTreeNode *t); /返回父结点 BinTreeNode *Find (BinTreeNode * subTree, T /搜寻x,48,void Traverse (BinTreeNode *subTree, ostream /后序遍历,2019/5/18,49,自测题 4,一棵124个叶结点的完全二叉树，最多有( )个结点。 A.247 B.248 C.249; D.250; E.251 【中国科学技术大学1995十四.3(2分)】,2019/5/18,50,自测题 5,已知一棵完全二叉树中共有626个结点，叶子结点的个数应为( )。 A. 311 B. 312 C. 313 D. 314 E. 其它 【上海交通大学2005四.6(2分)】,2019/5/18,51,自测题 6,一个具有1025个结点的二叉树的高h为（ ） A11 B10 C11至1025之间 D10至1024之间 【南京理工大学1999 一.19(2分)】,2019/5/18,52,自测题 7,一棵树高为K的完全二叉树至少有（ ）个结点 A. 2k 1 B. 2k-1 1 C. 2k-1 D. 2k 【南京理工大学 1998 一.3 （2分）】,2019/5/18,53,自测题 8,已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有_个叶子结点。 【厦门大学 2000 六.2 （16%/3分）】,2019/5/18,54,二叉树的遍历,二叉树的遍历的定义： 按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的操作。 遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系。 一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序列唯一确定。,2019/5/18,55,二叉树的遍历,前序遍历二叉树 中序遍历二叉树 后序遍历二叉树,若二叉树为空，则空操作，否则：,层次遍历二叉树,2019/5/18,56,D L R,D L R,D L R,D L R,前序遍历序列：A B D C,前序遍历,2019/5/18,57,L D R,L D R,L D R,L D R,中序遍历序列：B D A C,中序遍历,2019/5/18,58,L R D,L R D,L R D,L R D,后序遍历序列： D B C A,后序遍历,2019/5/18,59,层次遍历序列： A B C D,层次遍历,2019/5/18,60,遍历图例,中序序列为：DBEACF,前序序列为：ABDECF,后序序列为：DEBFCA,2019/5/18,61,自测题,3. 给定二叉树如下图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,1,7,5,6,2,4，则其遍历方式是 A. LRN B. NRL C. RLN D. RNL 【2009年全国硕士研究生入学计算机学科专业基础综合试题】,2019/5/18,62,中序遍历二叉树的递归算法,template void BinaryTree:InOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) InOrder (subTree-leftChild, visit); /遍历左子树 visit (subTree); /访问根结点 InOrder (subTree-rightChild, visit); /遍历右子树 ;,2019/5/18,63,图例,64,二叉树递归的前序遍历算法,template void BinaryTree:PreOrder (BinTreeNode * subTree, void (*visit) (BinTreeNode *t) if (subTree != NULL) visit (subTree); /访问根结点 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, visit); /遍历右子树 visit (subTree); /访问根结点 ;,2019/5/18,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) + 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,利用二叉树前序遍历建立二叉树,以递归方式建立二叉树。 输入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 此值在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 subTree = NULL; /封闭指向空子树的指针 ;,2019/5/18,73,二叉树的中序非递归遍历,设S为一个栈，t为指向根结点的指针， 其处理过程为： （1）当t非空时，将t所指结点的地址进栈，并将t指向该结点的左子树； （2）当t为空时，弹出栈顶元素，显示结点元素，并将t指向该结点的右子树； （3）重复（1）、（2）步骤，直到栈空且t 也为空。,2019/5/18,74,非递归中序遍历栈S的变化,结束,2019/5/18,75,中序非递归遍历 算法,template void BinaryTree: InOrder (void (*visit) (BinTreeNode *t) 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 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 = p; w.tag = L; S.Push (w); p = p-leftChild; int continue1 = 1; /继续循环标记, 用于R,79,while (continue1 ,2019/5/18,80,二叉树结构的性质,已知二叉树的先序序列和中序序列，可以唯一确定一棵二叉树。 已知二叉树的后序序列和中序序列，可以唯一确定一棵二叉树； 已知二叉树的先序序列和后序序列，不能唯一确定一棵二叉树； 已知二叉树的层次序列和中序序列，可以唯一确定一棵二叉树。,2019/5/18,81,自测题 9 构造二叉树,已知二叉树的 先序序列ABDFCEHG 中序序列DBFAHECG 请构造该二叉树。,2019/5/18,82,自测题 10 构造二叉树,已知二叉树的 后序序列DMFBHELGCA 中序序列DBMFAHECGL 请构造该二叉树。,2019/5/18,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/5/18,84,自测题 12 构造二叉树,试找出满足下列条件的二叉树 1）先序序列与后序序列相同 2）中序序列与后序序列相同 3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同,2019/5/18,85,自测题 13,一棵二叉树的前序遍历序列为ABCDEFG，它的中序遍历序列可能是（ ）。 ACABDEFG BABCDEFG CDACEFBG DADCFEGB 【北京工业大学2001一.2(2分)】,2019/5/18,86,自测题 14,一棵非空的二叉树的先序序列和后序序列正好相反，则该二叉树一定满足( )。 A. 其中任意一个结点均无左孩子 B. 其中任意一个结点均无右孩子 C. 其中只有一个叶子结点 D. 其中度为2的结点最多为一个 【中南大学2005一.7(2分)】,2019/5/18,87,自测题 15,某二叉树的先序序列和后序序列正好相反，则该二叉树一定是( )的二叉树 A空或只有一个结点 B. 高度等于其结点数 C任一结点无左孩子 D. 任一结点无右孩子 【东华大学2003二.1(1分)】,2019/5/18,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/5/18,89,算法举例6.1 求二叉树深度,以二叉链表作存储结构，试编写求二叉树深度的算法。 int BinTreeDepth(BiTree T) if(T=NULL) return 0; elsel=BinTreeDepth(T-lchild); r=BinTreeDepth(T-rchild); return(lr? l+1 :r+1); ,2019/5/18,90,算法举例6.2 求二叉树的叶子数(1),以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。 int LeafCount(BiTree T) if(!T) return 0; /空树没有叶子 else if(!T-lchild /左子树叶子数加上右子树叶子数 ,2019/5/18,91,算法举例6.2 求二叉树的叶子数(2),以二叉链表作为存储结构，试编写求二叉树中 叶子数的算法。 int num=0; void LeafCount(BiTree T) if(T) LeafCount(T-lchild) ; /中序遍历左子树 if(!T-lchild /中序遍历右子树 ,2019/5/18,92,算法举例6.3 交换二叉树的子树,以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。 void change(BiTree T) if(T!=NULL) change(T-lchild); change(T-rchild); t=T-lchild; T-lchild=T-rchild; T-rchild=t; ,2019/5/18,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/5/18,94,算法举例6.5 由顺序存储的n个结点的完全二叉树建立二叉链表存储的二叉树,BiTree creat(ElemType 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/5/18,95,void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2) /根据二叉树前序序列pre和中序序列in建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。 root=(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 设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组pre1n 和mid1n 中，试遍写算法建立该二叉树的二叉链表。,2019/5/18,96,线索二叉树,线索二叉树的提出： 1、遍历的实质：非线性结构线性化（前驱、后继）; 2、前驱和后继是在遍历中得到的; 3、知道前驱和后继，再遍历时就不需要栈; 4、可以在二叉链表结构中增加前驱和后继两个指针域; 5、n个结点的二叉树有n1个空指针，可以利用。,2019/5/18,97,线索二叉树,n个结点的二叉链表中含有n+1个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息,这样的指针称为“线索”，加上了线索的二叉链表称为线索链表，加上线索的二叉树就是线索二叉树（Threaded Binary Tree）。将二叉树变为线索二叉树的过程称为线索化。,ltag=,rtag=,2019/5/18,98,线索二叉树,线索化,只有空指针才能加线索,2019/5/18,99,前序前驱线索化,前序前驱线索化,2019/5/18,100,中序（全）线索二叉树,NULL,为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，rchild域指向访问序列的最后一个结点，这样，就建立了一个双向线索链表。,2019/5/18,101,后序（全）线索化,2019/5/18,102,线索链表的类型定义,typedef struct BiThrNode ElemTyte data; struct BiThrNode *lchild, *rchild;左、右孩子指针 int ltag, rtag; BiThrNode，*BiThrTree,2019/5/18,103,算法举例6.7 中序线索化,BiThrTree pre=null;/设置前驱 void InOrderThreat(BiThrTree T) if (T) InOrderThreat(T-lchild); /左子树中序线索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左线索为pre; if (T-rchild=null) T-rtag=1; /置右标记，为右线索作准备 if (pre!=null /右子树中序线索化 /结束InOrderThreat,2019/5/18,104,算法举例6.8 前序线索化,BiThrTree pre=null;/设置前驱 void PreOrderThreat(BiThrTree T) if (T!=null) if (T-lchild=null) T-ltag=1; T-lchild=pre; /设置左线索 if (T-rchild=null) T-rtag=1; /为建立右链作准备 if (pre!=null /右子树前序线索化 ,2019/5/18,105,算法举例6.9 后序线索化,BiThrTree pre=null;/设置前驱 void PostOrderThreat(BiThrTree T) if (T) PostOrderThreat(T-lchild); /左子树后序线索化 PostOrderThreat(T-rchild); /右子树后序线索化 if (T-lchild=null) T-ltag=1; T-lchild=pre; /左线索为pre; if (T-rchild=null) T-rtag=1;/置右标记，为右线索作准备 if (pre!=null /前驱指针后移 /结束PostOrderThreat,2019/5/18,106,算法举例6.10 线索二叉树的中序遍历,void InorderTraverseThr(BiThrTree p) while(p) 二叉树非空 while (p-tag=0) 找中序序列的开始结点 p=p-lchild; printf(p-data); while(p /while InorderTraverseThr,2019/5/18,107,算法举例6.11 带头结点的线索二叉树 的中序遍历,void InorderTraverseThr(BiThrTree thrt) p=thrt-lchild; while(p!=thrt) 二叉树非空 while (p-ltag=0) 找中序序列的开始结点 p=p-lchild; printf(p-data); while(p-rtag=1 / while(p!=thrt) InorderTraverseThr,2019/5/18,108,前序线索树上找前驱和后继,找前驱： 困难,找后继： 若结点有左子女，则左子女是后继；否则，rchild指向后继。,2019/5/18,109,算法举例6.12 前序线索树上找后继,BiThrTree PreorderNext(BiThrTree p) if (p-ltag= =0) 结点有左子女 return(p-lchild); 结点的左子女为其前序后继 else return(p-rchild) ; PreorderNext,2019/5/18,110,中序线索树上找前驱和后继,中序的前驱和后继都往上指向祖先,找前驱： 若左标记为1，则lchild指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。,找后继： 若右标记为1，则rchild指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。,2019/5/18,111,算法举例6.13 中序线索树上找前驱,BiThrTree InorderPre(BiThrTree p) BiThrTree q; if (p-ltag= =1) 结点的左子树为空 q=p-lchild 结点的左指针域为左线索，指向其前驱 else q=p-lchild; p结点的中序前驱是左子树中最右边结点 while (q-rtag=0 ) q=q-rchild; if return (q); InorderPre,2019/5/18,112,算法举例6.14 中序线索树上找后继,BiThrTree InorderNext(BiThrTree p) BiThrTree q; if (p-rtag= =1) 结点的右子树为空 q=p-rchild 结点的右指针域为右线索，指向其后继 else q=p-rchild; P结点的中序后继是其右子树中最左边结点 while (q-ltag=0 ) q=q-lchild; if return (q); InorderNext,2019/5/18,113,后序线索树上找前驱和后继,找前驱： 若结点有右子女，则右子女是其前驱；否则，lchild指向其前驱。,找后继： 困难，需要知道其双亲。,2019/5/18,114,算法举例6.15 后序线索树上找前驱,BiThrTree PostorderPre(BiThrTree p) if (p-rtag= =0) 结点有右子女 return(p-rchild); 结点的右子女为其后序前驱 else return(p-lchild) ; PreorderPre,2019/5/18,115,线索树上结点的插入与删除,除修改结点指针外，还需要修改线索。,2019/5/18,116,自测题 16,二叉树在线索化后，仍不能有效求解的问题是（ ）。 A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前驱 D. 后序线索二叉树中求后序后继 【北方交通大学2003一.4(2分)】,2019/5/18,117,自测题 17,引入二叉线索树的目的是（ ） A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除 C为了能方便的找到双亲 D使二叉树的遍历结果唯一,2019/5/18,118,自测题 18,若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为( ) A. X的双亲 B. X的右子树中最左的结点 C. X的左子树中最右结点 D. X的左子树中最右叶结点 【南京理工大学1996 一.6 (2分)】,2019/5/18,119,自测题 19,一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是：( )。 A. 0 B. 1 C. 2 D. 不确定 【合肥工业大学 2000 一.5 （2分）】,2019/5/18,120,树的存储结构,考虑存储结构时，主要考虑逻辑结构： 数据元素 数据元素之间的关系,2019/5/18,121