数据结构树和二叉树

第6章 树 陈守孔陈守孔 孟佳娜孟佳娜 陈卓陈卓第6章 树w 6.1 树的概念及操作树的概念及操作w 6.2 二叉树二叉树 n 6.2.1 二叉树的概念及操作二叉树的概念及操作 n 6.2.2 二叉树的性质二叉树的性质n6.2.3 二叉树的存储结构二叉树的存储结构w 6.3 二叉树的遍历二叉树的遍历w 6.4 线索二叉树线索二叉树w 6.5 树和森林树和森林 n6.5.1 树的存储结构树的存储结构 n 6.5.2 森林、树、二叉树的相互转换森林、树、二叉树的相互转换 n 6.5.3 树和森林的遍历树和森林的遍历w 6.6 哈夫曼树及其应用哈夫曼树及其应用 n 6.6.1 最优二叉树最优二叉树(哈夫曼树哈夫曼树)n 6.6.2 哈夫曼编码哈夫曼编码 w 6.7算法设计举例算法设计举例主要内容 w 知识点知识点n树和二叉树定义树和二叉树定义n二叉树的性质，存储结构二叉树的性质，存储结构n二叉树的遍历及遍历算法的应用二叉树的遍历及遍历算法的应用n*线索二叉树线索二叉树n二叉树和树及森林的关系二叉树和树及森林的关系nHuffmanHuffman树与树与HuffmanHuffman编码编码w 重点难点重点难点n二叉树的性质及应用二叉树的性质及应用n二叉树的遍历算法及应用二叉树的遍历算法及应用n*线索二叉树的算法线索二叉树的算法nHuffmanHuffman树的构造方法树的构造方法n树的算法树的算法树例与特征n社会的组织结构社会的组织结构n家族的族谱家族的族谱n计算机中的目录组织计算机中的目录组织描述层次结构，是一种一对多的逻辑关系描述层次结构，是一种一对多的逻辑关系树的定义 w 树树(Tree)(Tree)是n(n=0)个结点的有限集。n=0时称为空树。w（注：有人定义树不能为空）（注：有人定义树不能为空）n有且仅有一个称为根的结点（Root）；nn1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,Tm,其中每个集合又是一棵树，称为子树(SubTree)FGIJABCEDH树的定义 w 树树的递归定义的各子树的递归定义的各子树T1,T2,Tm的相对次序是重要的，即树是有序的。树定义ACBGFEHIJDMKLAT1T2T3树的抽象数据类型树的抽象数据类型ADT Tree数据对象数据对象 D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系 R：若：若D为空集，则称为空树；为空集，则称为空树；若若D仅含有一个数据元素，则仅含有一个数据元素，则R为空集，否则为空集，否则R=H，H是如下定义的二元关系：是如下定义的二元关系：（1 1）在在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关，它在关系系H下无前驱；下无前驱；（2）若）若D-root,则存在则存在D-root的一个划分的一个划分D1，D2,Dm（m0）,对任意对任意j k(1 j,k m)有有Dj Dk=,且对任意的且对任意的i(1 i m),存在唯一数据元素存在唯一数据元素xi Di,H;（3）对应于）对应于D-root的划分，的划分，H-,有唯一的一个划分有唯一的一个划分H1,H2,Hm(m0),对任意对任意j k(1 j,k m)有有Hj Hk=,且对任意且对任意i(1 i m)，Hi是是Di上的二元关系，（上的二元关系，（Di，Hi）是一棵符合本定义的树，称为根）是一棵符合本定义的树，称为根root的子树。的子树。（转下页）（转下页）TreeInit(T);TreeChild(T,x,i);Treebuild(T,F);TreeClear(T);Traverse(T);TreeRoot(T);TreeParent(T,x);TreeRightBrother(T,x);TreeLeftBrother(T,x);TreeInsert(T,y,i,x);ADT Tree树的抽象数据类型树的其它表示方式凹入表示凹入表示嵌套集合嵌套集合广义表广义表A(B(E,F),C,D(G(J),H,I)AE FBIJGHCDAB E FCD G J H IFGIJABCEDHw 结点结点：一个数据元素一个数据元素及及若干指向其子树的分支；若干指向其子树的分支；w 结点的度结点的度：结点拥有的子树的数目。结点拥有的子树的数目。w 树的度树的度：树内各结点的度的最大值；：树内各结点的度的最大值；w 叶子叶子（终端结点）：度为（终端结点）：度为0的结点；的结点；w 分支结点分支结点（非终端结点）：度不为（非终端结点）：度不为0的结点；除的结点；除根结点外，也称内部结点；根结点外，也称内部结点；w 孩子，双亲，孩子，双亲，兄弟，兄弟，堂兄堂兄：结点的子树的根称：结点的子树的根称为该结点的孩子；该结点称为孩子的双亲；同为该结点的孩子；该结点称为孩子的双亲；同一个双亲的孩子之间互称兄弟；其父结点是兄一个双亲的孩子之间互称兄弟；其父结点是兄弟的结点互称堂兄。弟的结点互称堂兄。树的概念概念w 祖先祖先：从根结点到该结点所经分支上的所有结：从根结点到该结点所经分支上的所有结点。点。w 子孙子孙：以某结点为根的子树中的任一结点都称：以某结点为根的子树中的任一结点都称为该结点的子孙。为该结点的子孙。w 层次层次：结点在树结构中的层（：结点在树结构中的层（一般定义根为一般定义根为1层）。层）。w 深度深度：树中结点的最大层次称为树的深度。：树中结点的最大层次称为树的深度。w 有序树有序树：结点的子树在树中的位置固定，不能：结点的子树在树中的位置固定，不能互换，称有序树。互换，称有序树。w 无序树无序树：子树在树中的位置可以互换。：子树在树中的位置可以互换。w 森林森林：m(m0)棵互不相交的树的集合。棵互不相交的树的集合。概念示例w 结点结点w 结点的度结点的度(Degree)w 叶子（叶子（Leaf)或终端结点或终端结点w 分支结点或非终端结点分支结点或非终端结点w 树的度树的度w 层次层次(Level)w 树的深度树的深度(Depth)w 孩子（孩子（child)w 双亲（双亲（Parent)w 兄弟兄弟(Sibling)w 祖先祖先w 子孙子孙ACBGFEHIJDMKL树的示例树的示例二叉树的概念 w 二叉树二叉树(Binary Tree)(Binary Tree)：或者是一棵空树，或者是一棵空树，或者是一棵由一个根结点和两棵互不相交或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树，左子的左子树和右子树所组成的非空树，左子树和右子树又同样都是二叉树树和右子树又同样都是二叉树 w 特征特征：n每个结点最多只有两棵子树每个结点最多只有两棵子树n子树有左右之分，其次序不能任意颠倒，只有子树有左右之分，其次序不能任意颠倒，只有一棵子树时也必须分清左右子树。一棵子树时也必须分清左右子树。二叉树的抽象数据类型ADT BinTree 数据对象数据对象D：D是具有相同特性的数据元素的集合。是具有相同特性的数据元素的集合。数据关系数据关系R：若：若D=，则，则R=，称二叉树为空二叉树；，称二叉树为空二叉树；若若D，则，则R=H，H是如下二元关系：是如下二元关系：（1）在）在D中存在唯一的称为根的数据元素中存在唯一的称为根的数据元素root，它在关系，它在关系H下无下无前驱；前驱；（2）若）若D-root,则存在则存在D-root=D1,Dr,且且 D1 Dr；（3）若）若D1，则，则D1中存在唯一的元素中存在唯一的元素x1,H,且存在且存在D1上的关系上的关系H1 H；若；若Dr,则则Dr中存在唯一的元素中存在唯一的元素xr,H,且存在且存在Dr上的关系上的关系Hr H；H=,H1,Hr;（4）（）（D1，H1）是一棵符合本定义的二叉树，称为根的左子）是一棵符合本定义的二叉树，称为根的左子树，（树，（Dr，Hr）是一棵符合本定义的二叉树，称为根的右子）是一棵符合本定义的二叉树，称为根的右子树。树。基本操作如下：基本操作如下：二叉树的抽象数据类型BiTreeInit(BT);BiTreeRoot(BT);BiTreeParent(BT,x);BiTreeLeftChild(BT,x);BiTreeRightChild(BT,x);BiTreeBuild(BT,LBT,RBT);BiTreeInsertLeft(BT,y,x);BiTreeInsertRight(BT,y,x);BiTreeDeleteLeft(BT,x);BiTreeDeleteRight(BT,x);BiTreeClear(BT);BiTraverse(BT);ADT BinTree 二叉树的五种形态(a)(a)(b)(b)(c)(c)(d)(d)(e)(e)二叉树的性质1.1.一个非空二叉树的第一个非空二叉树的第i i层上层上至多至多有有2 2i-1i-1个结个结点（点（i i 1 1）证明：i=1,只有根结点，显然成立 设i=k时成立，最多有2k-1 当i=k+1时，最多的结点个数：2k-1*2=2k-1+1=2k=2(k+1)-12.2.深度为深度为k k的二叉树的二叉树至多至多有有2 2k k-1-1个结点个结点(k(k 1)1)二叉树的性质证明：二叉树的结点个数为：1+2+2k-1=2k-1二叉树的性质3.3.对任何一棵二叉树对任何一棵二叉树T T，如果其终端结点数，如果其终端结点数为为n0n0，度为，度为2 2的结点数为的结点数为n2n2，则，则n0=n2+1n0=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;满二叉树w 满二叉树满二叉树：深度为深度为k且有且有2k-1个结点的二叉树个结点的二叉树189101112131415452673满二叉树满二叉树w考虑到有序性，考虑到有序性，任一结点在树中任一结点在树中都有确切的位置，都有确切的位置，因此可以对满二因此可以对满二叉树进行编号。叉树进行编号。编号方式为：从编号方式为：从上到下，从左到上到下，从左到右。右。完全二叉树w 完全二叉树：完全二叉树：深度为深度为k，有，有n个结点的二叉个结点的二叉树，当且仅当树，当且仅当其每一个结点其每一个结点都与深度为都与深度为k的的满二叉树编号满二叉树编号从从1到到n的结点的结点一一对应时，一一对应时，称为完全二叉称为完全二叉树。树。189101112452673完全二叉树完全二叉树完全二叉树w特征：特征：n叶子结点只可能在层次最大的两层上叶子结点只可能在层次最大的两层上出现。出现。n任一结点，若其左分支下的子孙的最任一结点，若其左分支下的子孙的最大层次为大层次为l，则其右分支下的最大层次，则其右分支下的最大层次为为l或或l-1，即若结点，即若结点无左子女无左子女，决不决不应有右子女应有右子女。完全二叉树的特性（1）1.1.具有具有n n个结点的完全二叉树的深度个结点的完全二叉树的深度:k=k=1nlog2证明：假设证明：假设n个结点的完全二叉树的深度为个结点的完全二叉树的深度为k，则，则n的值应的值应大于深度为大于深度为k-1的满二叉树的结点数的满二叉树的结点数2k-1-1，小于等于深度，小于等于深度为为k的满二叉树的结点数的满二叉树的结点数2k-1，即，即2k-1-1n2k-1 进一步可推导出进一步可推导出 2k-1n+12k两边取对数后，有两边取对数后，有 k-11,则其双亲结点是则其双亲结点是 i/2。（b）如果）如果2in,则结点则结点i无左孩子，无左孩子，i为叶子结点为叶子结点,否则其左孩子是结点否则其左孩子是结点2i。（c）如果）如果2i+1n，则结点，则结点i无右孩子，否则其右无右孩子，否则其右孩子是结点孩子是结点2i+1。示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1 i/2i/2 j层j+1层示意图2i2i2i+12i+1i i2i+22i+22i+32i+3i+1i+1LCHILD(i)LCHILD(i+1)RCHILD(i)RCHILD(i+1)i/2i/2 完全二叉树性质的推论w n个结点的完全二叉树个结点的完全二叉树中：中：n 度为度为1的结点数为的结点数为(n+1)%2;n 度为度为0的结点数为的结点数为 (n+1)/2；n 度为度为2的结点数为的结点数为 (n+1)/2-1；n 编号最大的分支结点是编号最大的分支结点是 n/2；n 编号最小的叶子结点是编号最小的叶子结点是 n/2+1。w n个结点的二叉树：个结点的二叉树：n高最多为高最多为n；n最低为最低为 （完全二叉树）。（完全二叉树）。1nlog2树的叶子与其它结点的关系树的叶子与其它结点的关系w 设设度为度为m的树中度为的树中度为0,1,2,m的结点数分的结点数分别为别为n0,n1,n2,nm，结点总数为，结点总数为n，分枝，分枝数为数为B，则下面二式成立，则下面二式成立w n=n0+n1+n2+nm (1)w n=B+1=n1+2n2+mnm (2)w 由由(1)和和(2)得叶子结点数得叶子结点数n0=1+mii1in)1(二叉树的存储储结构w顺序存储结构w链式存储结构二叉树的顺序存储结构n整个二叉树可以按照从上到下，从左到整个二叉树可以按照从上到下，从左到右的顺序编号；右的顺序编号；n对于满对于满/完全二叉树，可以从根结点开始完全二叉树，可以从根结点开始按序号存放；按序号存放；n对于一般的二叉树，可以参照满二叉树对于一般的二叉树，可以参照满二叉树的编号方法进行编号，位置空的结点为的编号方法进行编号，位置空的结点为“虚结点虚结点”。顺序存储结构举例123456789101 18 89 910104 45 52 26 67 73 3完全二叉树完全二叉树顺序存储结构举例1234578101 18 810104 45 52 27 73 3一般二叉树一般二叉树顺序存储结构举例ABC非完全二叉树非完全二叉树XABCA B C 二叉树的链式存储结构w 二叉链表二叉链表w 三叉链表三叉链表w（线索链表）（线索链表）lchilddatarchilddatalchild rchildlchilddatarchildparentdatalchild rchildparent链式存储结构示例ACFEDBADBCEFABCDEF二叉链表二叉链表三叉链表三叉链表二叉链表的类C表示 二叉树的二叉链表存储表示二叉树的二叉链表存储表示typedef struct BiNode ElemTyte data;struct BiNode *lchild,*rchild;左右孩子指针左右孩子指针 BiNode,*BiTree；二叉树的遍历二叉树的遍历 二叉树的遍历的定义二叉树的遍历的定义：按某种规律，访问二叉树的结点，使每个结点按某种规律，访问二叉树的结点，使每个结点被访问一次且仅一次。访问的含义包括查询、打被访问一次且仅一次。访问的含义包括查询、打印、计算、修改等对结点的操作。印、计算、修改等对结点的操作。遍历的过程，实际上是按某种规律，将一个遍历的过程，实际上是按某种规律，将一个非线性结构的结点排成一个线性序列，使每个结非线性结构的结点排成一个线性序列，使每个结点在这种遍历中有唯一前驱和后继关系。点在这种遍历中有唯一前驱和后继关系。一棵二叉树的遍历序列（在某种遍历方式下）一棵二叉树的遍历序列（在某种遍历方式下）是唯一的，但一般说，二叉树不能由某一遍历序是唯一的，但一般说，二叉树不能由某一遍历序列唯一确定。列唯一确定。二叉树的遍历二叉树的遍历 w 前序遍历二叉树前序遍历二叉树w 中序遍历二叉树中序遍历二叉树w 后序遍历二叉树后序遍历二叉树访问根结点；访问根结点；前序遍历左子树；前序遍历左子树；前序遍历右子树前序遍历右子树；中序遍历左子树；中序遍历左子树；访问根结点；访问根结点；中序遍历右子树；中序遍历右子树；后序遍历左子树；后序遍历左子树；后序遍历右子树；后序遍历右子树；访问根结点；访问根结点；D DL LR RLDRLDR、LRDLRD、DLRDLRRDLRDL、RLDRLD、DRLDRL若二叉树为空，则空操作，否则：若二叉树为空，则空操作，否则：层次遍历二叉树层次遍历二叉树ADBCD L RAD L RD L RBDCD L R前序遍历序列：前序遍历序列：A B D CA B D C前序遍历ADBCL D RBL D RL D RADCL D R中序遍历序列：中序遍历序列：B D A CB D A C中序遍历ADBC L R DL R DL R DADCL R D后序遍历序列：后序遍历序列：D B C AD B C A后序遍历B遍历图例ACFEDB中序序列为：中序序列为：DBEACFDBEACF 前序序列为：前序序列为：ABDECFABDECF 后序序列为：后序序列为：DEBFCADEBFCA 中序遍历二叉树的递归算法void InOrderTraverse(BiTree T)if(T)二叉树非空二叉树非空 InOrderTraverse(T-lchild);中序遍历左子树中序遍历左子树 visit(T-data);访问根结点访问根结点 InOrderTraverse(T-rchild);中序遍历右子树中序遍历右子树 if InOrderTraverse 图例CFEDBA递归遍历举例abcdgefABCDEF前序序列：前序序列：abdefcg中序序列：中序序列：dfebagc后序序列：后序序列：fedbgca前序序列：前序序列：abcdef中序序列：中序序列：cbefda后序序列：后序序列：cfedba二叉树的中序非递归遍历 设设S为一个栈，为一个栈，t为指向根结点的指针，为指向根结点的指针，其处理其处理过程为：过程为：（1）当）当t非空时，将非空时，将t所指结点的地址进栈，并所指结点的地址进栈，并将将t指向该结点的左子树；指向该结点的左子树；（2）当）当t为空时，弹出栈顶元素，显示结点元素为空时，弹出栈顶元素，显示结点元素，并将，并将t指向该结点的右子树；指向该结点的右子树；（3）重复（）重复（1）、（）、（2）步骤，直到栈空且）步骤，直到栈空且t 也为也为空空。非递归中序遍历栈S的变化cbat”t”t”a”at”NULL”a出栈出栈t”NULL”出栈出栈bt”b”t”NULL”b出栈出栈t”NULL”出栈出栈t”c”ct”NULL”c出栈出栈t”NULL”栈空栈空结束结束void InOrderTraverse1(BiTree T)中序遍历二叉树的非递归算法，中序遍历二叉树的非递归算法，Visit是访问元素的函数是访问元素的函数 StackInit(S);建栈建栈 p=T;while(p|!StackEmpty(S)while(p)Push(S，p);二叉树非空，根结点进栈二叉树非空，根结点进栈 p=p-lchild;遍历左子树遍历左子树 if if（！（！StackEmpty(S)）Pop(S，p);Visit(p-data);p=p-rchild;遍历右子树遍历右子树 if 中序非递归遍历 算法void postorder(BiTree t)typedef struct node BiTree t;int tag;/tag 0.1 stack;stack sn+1;top=0;while(t!=null|top!=0)while(t!=null)s+top.t=t;stop.tag=0;t=t-lchild;while(top!=0&stop.tag=1)printf(stop-.t-data:3);if(top)stop.tag:=1;t=stop.t-rchild;postorder后序非递归遍历 算法建立二叉树BiTree CreatBiTree()按前序构造二叉链表表示的二叉树按前序构造二叉链表表示的二叉树T BiTree T;scanf(&ch);if(ch=*)T=NULL;*表示空表示空 else T=(BiNode*)malloc(sizeof(BiNode);T-data=ch;生成根结点生成根结点 T-lchild=CreatBiTree();生成左子树生成左子树 T-rchild=CreatBiTree();生成左子树生成左子树 if return T;CreatBiTree 二叉树结构的性质w 已知二叉树的已知二叉树的先序序列和中序序列先序序列和中序序列，可，可以唯一确定一棵二叉树。以唯一确定一棵二叉树。w 已知二叉树的已知二叉树的后序序列和中序序列后序序列和中序序列，可，可以唯一确定一棵二叉树；以唯一确定一棵二叉树；w 已知二叉树的已知二叉树的先序序列和后序序列先序序列和后序序列，不，不能唯一确定一棵二叉树；能唯一确定一棵二叉树；w 已知二叉树的已知二叉树的层次序列和中序序列层次序列和中序序列，可，可以唯一确定一棵二叉树。以唯一确定一棵二叉树。构造二叉树w w已知二叉树的已知二叉树的w 先序序列先序序列ABDFCEHGw 中序序列中序序列DBFAHECGw请构造该二叉树。请构造该二叉树。构造二叉树w w已知二叉树的已知二叉树的w 后序序列后序序列DMFBHELGCAw 中序序列中序序列DBMEAHECGLw请构造该二叉树。请构造该二叉树。构造二叉树试找出满足下列条件的二叉树试找出满足下列条件的二叉树1）先序序列与后序序列相同）先序序列与后序序列相同 2）中序序列与后序序列相同）中序序列与后序序列相同3）先序序列与中序序列相同）先序序列与中序序列相同 4）中序序列与层次遍历序列相同）中序序列与层次遍历序列相同 表达式的二叉树表示+*+fhg*+abc+de用二叉树可以表示表达式用二叉树可以表示表达式前序遍历：前序遍历：*+ab*c+def+gh中序遍历：中序遍历：a+b+c*d+e+f*g+h后序遍历：后序遍历：ab+cde+*+f+gh+*表达式表达式:(a+b)+c*(d+e)+f)*(g+h)二叉树遍历算法的应用(1)w 以二叉链表作存储结构，试编写求二叉树深度以二叉链表作存储结构，试编写求二叉树深度的算法。的算法。w int BinTreeDetth(BiTree T)w if(T=NULL)return 0;w elsel=BinTreeDetth(T-lchild);w r=BinTreeDetth(T-rchild);w return(lr?l+1:r+1);w w 二叉树遍历算法的应用(2)w 以二叉链表作为存储结构，试编写求二叉树中叶子数以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。的算法。w int LeafCount(BiTree T)w if(!T)return 0;/空树没有叶子空树没有叶子 w else w if(!T-lchild&!T-rchild)return 1;/叶子结点叶子结点 w else return LeafCount(T-lchild)+w LeafCount(T-rchild);w /左子树叶子数加上右子树叶子数左子树叶子数加上右子树叶子数 w 二叉树遍历算法的应用(3)w 以二叉链表作为存储结构，试编写求二叉树中以二叉链表作为存储结构，试编写求二叉树中 叶子数的算法。叶子数的算法。w int num=0;w void LeafCount(BiTree T)w if(T)w LeafCount(T-lchild);/中序遍历左子树中序遍历左子树w if(!T-lchild&!T-rchild)num+;/访问根结点访问根结点w LeafCount(T-rchild);/中序遍历右子树中序遍历右子树w w 二叉树遍历算法的应用(4)w 以二叉链表作为存储结构，设计算法交换二以二叉链表作为存储结构，设计算法交换二叉树中所有结点的左、右子树。叉树中所有结点的左、右子树。w void change(BiTree*T)w if(*T!=NULL)w change(&(*T)-lchild);w change(&(*T)-rchild);w*t=(*T)-lchild;w(*T)-lchild=(*T)-rchild;w(*T)-rchild=*t;ww 二叉树遍历算法的应用(5)w 以二叉链表作为存储结构，设计算法拷贝二叉树以二叉链表作为存储结构，设计算法拷贝二叉树。w BiTree copy(BiTree T)w BiTree T1;w if(T=null)T1=null;w elsew T1=(BiTree)malloc(sizeof(BiNode);/申请结点申请结点w T1-data=T-data;w T1-lchild=copy(T-lchild);w T1-rchild=copy(T-rchild);ww return T1;w 二叉树遍历算法的应用(6)w 由顺序存储的由顺序存储的n个结点的完全二叉树建立二叉链表存储的二个结点的完全二叉树建立二叉链表存储的二叉树。叉树。w BiTree creat(ElemType A,int i)w BiTree T;w if(in)T=null;w elsew T=(BiTree)malloc(sizeof(BiNode);/申请结点申请结点w T-data=Ai;w T-lchild=creat(A,2*i);w T-rchild=creat(A,2*i+1);ww return T;w /初始调用：初始调用：p=creat(A,1);二叉树遍历算法的应用(7)w 设一棵二叉树中各结点的值互不相同，其前序序列和中序序设一棵二叉树中各结点的值互不相同，其前序序列和中序序列分别存于两个一维数组列分别存于两个一维数组pre1.n 和和mid1.n 中，试遍写算中，试遍写算法建立该二叉树的二叉链表。法建立该二叉树的二叉链表。w void PreInCreat(BiTree root,ElemType pre,in,int l1,h1,l2,h2)w/根据二叉树前序序列根据二叉树前序序列pre和中序序列和中序序列in建立二叉树。建立二叉树。l1,h1,l2,h2是序列第一和最后元素下标。是序列第一和最后元素下标。w root=(BiTree)malloc(sizeof(BiNode);/申请结点申请结点w root-data=prel1;/prel1是根是根w for(i=l2;ilchild=null;/无左子树无左子树w else PreInCreat(root-lchild,pre,in,l1+1,l1+(i-l2),l2,i-1)；w /递归建立递归建立/左子树左子树w if(i=h2)root-rchild=null;/无右子树无右子树w else PreInCreat(*root)-rchild,pre,in,l1+(i-l2)+1,h1,i+1,h2)/递归建递归建/立右子树立右子树w/结束结束PreInCreat线索二叉树线索二叉树 线索二叉树的提出：线索二叉树的提出：1、遍历的实质：非线性结构线性化（前驱、遍历的实质：非线性结构线性化（前驱、后继）后继）;2、前驱和后继是在遍历中得到的、前驱和后继是在遍历中得到的;3、知道前驱和后继，再遍历时就不需要栈、知道前驱和后继，再遍历时就不需要栈;4、可以在二叉链表结构中增加前驱和后继两、可以在二叉链表结构中增加前驱和后继两个指针域个指针域;5、n个结点的二叉树有个结点的二叉树有n1个空指针，可以个空指针，可以利用。利用。线索二叉树线索二叉树 n个结点的二叉链表中含有个结点的二叉链表中含有n+1个空指针域，可以利用这个空指针域，可以利用这些空指针域来存放结点的前驱和后继的信息些空指针域来存放结点的前驱和后继的信息,这样的的指针这样的的指针称为称为“线索线索”，加上了线索的二叉链表称为，加上了线索的二叉链表称为线索链表线索链表，加上，加上线索的二叉树就是线索的二叉树就是线索二叉树线索二叉树（Threaded Binary Tree）。）。将二叉树变为线索二叉树的过程称为将二叉树变为线索二叉树的过程称为线索化线索化。lchildltagdata rtag rchild指向结点前驱指向结点的左孩子lchildlchild:1:0ltag=指向结点后继指向结点的右孩子rchildrchild:1:0rtag=线索二叉树线索二叉树 线索化线索化只有空指针才能加线索只有空指针才能加线索前序前驱线索化前序前驱线索化w 前序前驱线索化前序前驱线索化ABECFGHIDABECFGHID中序（全）线索二叉树中序（全）线索二叉树NULLACFEDBNULLA 00E 11C 01D 11F 11B 00NULLA 为方便起见，在线索链表中增加一个头结点，令其为方便起见，在线索链表中增加一个头结点，令其lchild域指向二叉树的根结点，域指向二叉树的根结点，rchild域指向访问序列的最域指向访问序列的最后一个结点，这样，就建立了一个后一个结点，这样，就建立了一个双向线索链表双向线索链表。后序（全）线索化后序（全）线索化AEDCBHGFAEDCBHGFnull类型定义typedef struct BiThrNode ElemTyte data;struct BiThrNode *lchild,*rchild;左、右孩子指针左、右孩子指针 int ltag,rtag;BiThrNode，*BiThrTree 前序线索化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&pre-rtag=1)pre-rchild=T;/设置前驱的右线索；设置前驱的右线索；pre=T;/前驱后移前驱后移 if(T-ltag=0)PreOrderThreat(T-lchild);/左子树前序线索化左子树前序线索化 PreOrderThreat(BT-rchild);/右子树前序线索化右子树前序线索化 中序线索化二叉树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&pre-rtag=1)pre-rchild=T;/给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 InOrderThreat(T-rchild);/右子树中序线索化右子树中序线索化 /结束结束InOrderThreat 后序线索化二叉树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&pre-rtag=1)pre-rchild=T;/给前驱加后继线索给前驱加后继线索 pre=T;/前驱指针后移前驱指针后移 /结束结束PostOrderThreat 线索二叉树的中序遍历w void InorderTraverseThr(BiThrTree p)w while(p)二叉树非空二叉树非空w while(p-tag=0)找中序序列的开始结点找中序序列的开始结点 p=p-lchild;printf(p-data);wwhile(p&p-rtag=1)w p=p-rchild;printf(p-data);/找找P的中序后继结点的中序后继结点w if(p)p=p-rchild;w /whilew InorderTraverseThr带头结点的线索二叉树的中序遍历w void InorderTraverseThr(BiThrTree thrt)w p=thrt-lchild;w while(p!=thrt)二叉树非空二叉树非空w while(p-ltag=0)找中序序列的开始结点找中序序列的开始结点w p=p-lchild;w printf(p-data);wwhile(p-rtag=1&p-rchild!=thrt)w p=p-rchild;printf(p-data);/找找P的中序后继结点的中序后继结点w p=p-rchild;w /while(p!=thrt)w InorderTraverseThr前序线索树上找前驱和后继找前驱：找前驱：困难困难找后继找后继：若结点有左子女，则左子女是后继；否则，若结点有左子女，则左子女是后继；否则，rchild指向后继。指向后继。前序线索树上找后继BiThrTree PreorderNext(BiThrTree p)if(p-ltag=0)结点有左子女结点有左子女 return(p-lchild);结点的左子女为其前序后继结点的左子女为其前序后继 else return(p-rchild);PreorderNext中序线索树上找前驱和后继 中序的前驱和后继都往上指向祖先找前驱：找前驱：若左标记为若左标记为1，则，则lchild指向其前驱；否则，指向其前驱；否则，其前驱是其左子树上按中序遍历的最后一个结点。其前驱是其左子树上按中序遍历的最后一个结点。找后继找后继：若右标记为若右标记为1，则，则rchild指向其后继；否则，指向其后继；否则，其后继是其右子树上按中序遍历的第一个结点。其后继是其右子树上按中序遍历的第一个结点。中序线索树上找前驱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中序线索树上找后继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后序线索树上找前驱和后继找前驱：找前驱：若结点有右子女，则右子女是其前驱；否若结点有右子女，则右子女是其前驱；否则，则，lchild指向其前驱。指向其前驱。找后继找后继：困难，需要知道其双亲。困难，需要知道其双亲。后序线索树上找前驱BiThrTree PostorderPre(BiThrTree p)if(p-rtag=0)结点有右子女结点有右子女 return(p-rchild);结点的右子女为其后序前驱结点的右子女为其后序前驱 else return(p-lchild);PreorderPre线索树上结点的插入与删除除修改结点指针外，除修改结点指针外，还需要修改线索。还需要修改线索。树的存储结构w考虑存储结构时，主要考虑逻辑结构：n数据元素n数据元素之间的关系w树的存储结构树的存储结构：n链式存储结构树的存储结构ABECDFw双亲表示法双亲表示法 w孩子表示法孩子表示法 w孩子兄弟表示法孩子兄弟表示法 双亲表示法w 使用静态数组（本质是静态链表）静态数组（本质是静态链表）；w 数组的每个数据元素，包括两个域：一个域是数据元素数据元素；另一个域用游标指示该结点的双亲结点在数组中的相对位置位置；根结点的游标为-1。w 特点：n方便找结点的双亲双亲；n顺序存储结构；双亲表示法类型定义#define MAX_NODE 64typedef struct Ptnode ElemTyte data;数据域 int parent;双亲指示域 Ptnode；typedef struct Ptnode nodesMAX_NODE;int n;Ptree;双亲表示示例ACGEDBHF 数组下标 0 1 2 3 4 5 6 7 data A B C D E F G H parent -1 0 0 1 1 2 2 2 双亲表示法表示的树的深度w int Depth(Ptree t)w int maxdepth=0;w for(i=1;i0)/求结点求结点i的深度的深度w temp+;f=t.nodesf.parent;w if(tempmaxdepth)/最大深度更新最大深度更新 maxdepth=temp;w w return(maxdepth);/返回树的深度返回树的深度w /结束结束Depth孩子表示法w 任一数据元素，有任一数据元素，有0个或多个孩子；个或多个孩子；w 因此可以设计一个链式存储结构，其结点除因此可以设计一个链式存储结构，其结点除放置数据元素外，还放置若干指针，分别用放置数据元素外，还放置若干指针，分别用来指示该结点的所有孩子结点在存储空间中来指示该结点的所有孩子结点在存储空间中的位置。的位置。孩子表示法w 方法方法1 1n根据结点的度，设置结点的指针个数，比如若根据结点的度，设置结点的指针个数，比如若结点的度为结点的度为d:d:datachild1child2childd问题问题：n不同的数据元素，结点构造不同；不同的数据元素，结点构造不同；n操作不方便操作不方便孩子表示法w 方法方法2 2n按照树的度定义结点。若树的度为按照树的度定义结点。若树的度为d,定义定义degree，表示该结点的度，表示该结点的度datachild1child2childddegree问题问题：n因因degree为树的度，是所有结点的最大的度，为树的度，是所有结点的最大的度，因此树中有相当部分的指针域为空，浪费空间。因此树中有相当部分的指针域为空，浪费空间。n有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有 n(k-1)+1个。个。孩子表示法w 有有n个结点的树的度为个结点的树的度为k，空指针域有，空指针域有n(k-1)+1个。个。w 证明：证明：nn个结点的树，除根结点外，每个结点有一个指针个结点的树，除根结点外，每个结点有一个指针指向，也就是树中有指向，也就是树中有n-1个有效链域（指针）个有效链域（指针）n而按该结点定义，而按该结点定义，n个结点总的指针域有：个结点总的指针域有：nk个。个。n因此空链域：因此空链域：nk (n-1)=n(k-1)+1w 一个静态数组，存放所有的结点一个静态数组，存放所有的结点w 数组的每个数据元素，包括两部分：数数组的每个数据元素，包括两部分：数据元素，指针；指针指向一个链表，链据元素，指针；指针指向一个链表，链表结点的数据域是一个整数，表示该结表结点的数据域是一个整数，表示该结点的孩子在数组中的相对位置；点的孩子在数组中的相对位置；w 特点：特点：n顺序顺序+链式存储结构；链式存储结构；n找孩子容易，找双亲难；找孩子容易，找双亲难；孩子表示法孩子表示法孩子表示法ACGEDBHF01234567657 ABCDEFG312 4 H双亲孩子链表w 在静态数组的结点中增加一个域，表示该结点的双亲在静态数组的结点中增加一个域，表示该结点的双亲在该树组中的相对位置。在该树组中的相对位置。w 有利于寻找孩子结点和双亲结点。有利于寻找孩子结点和双亲结点。ACGEDBHF01234567657 312 GABCDEF-1001122parent4 H2孩子表示法类型定义#define MAX_NODE 64typedef struct Ctnode 孩子结点孩子结点 int child;struct Ctnode*next;*childlink;typedef struct 头结点头结点 ElemType data;childlink firstchild;CTBox;CTBox nodesMAX_NODE；孩子兄弟表示法w 从向下的纵向和向右的横向描述树；从向下的纵向和向右的横向描述树；w 定义结点，除存放数据元素外，存放两个定义结点，除存放数据元素外，存放两个指针，一个指向该结点的第一个孩子，另指针，一个指向该结点的第一个孩子，另一个指向该结点的下一个兄弟；一个指向该结点的下一个兄弟；孩子兄弟表示法typedef struct CSNode ElemTyte data;struct CSNode *firstchild,*nextsibling;CSNode,*CSTree;该表示方法又称二叉树表示法，本质上与二该表示方法又称二叉树表示法，本质上与二叉链表表示法一致。叉链表表示法一致。datafirstchildnextsibling孩子兄弟表示法A BC DEFGHACGEDBHF孩子-兄弟表示法算法示例w int Leaves(Tree t)w/计算以孩子计算以孩子-兄弟表示法存储的森林的兄弟表示法存储的森林的叶子数叶子数w if(t=null)return 0;w else if(t-firstchild=null)/无孩子的结点必是叶子无孩子的结点必是叶子w return(1+Leaves(t-nextsibling);w /返回叶子结点和其兄弟子树中的叶子结点数返回叶子结点和其兄弟子树中的叶子结点数w else return(Leaves(t-firstchild)+w Leaves(t-nextsibling);w /孩子子树和兄弟子树中叶子数之和孩子子树和兄弟子树中叶子数之和w w/结束结束Leaves孩子-兄弟表示法算法示例w int Height(CSTree bt)/递归求以孩子兄弟链表表示的树的深度递归求以孩子兄弟链表表示的树的深度w int hc,hs;w if(bt=null)return(0);w else if(!bt-firstchild)w return max(1,height(bt-nextsibling）；）；w /子女空，取子女空，取1和兄弟的深度和兄弟的深度 的大者的大者w elsew hc=height(bt-firstchild)；/第一子女树高第一子女树高w hs=height(bt-nextsibling)；/兄弟树高兄弟树高w if(hc+1hs)return(hc+1);else return(hs);w /高度取子女高度高度取子女高度+1和兄弟子树高度的大者和兄弟子树高度的大者w w/结束结束heightw 若若树采用孩子兄弟表示法树采用孩子兄弟表示法，二叉树采用二叉链表，二叉树采用二叉链表表示，则从存储结构上看，结点定义完全相同。表示，则从存储结构上看，结点定义完全相同。因此，在使用该存储结构下，树和二叉树是等价因此，在使用该存储结构下，树和二叉树是等价的，树可以转化为二叉树。的，树可以转化为二叉树。树和二叉树的转化w步骤步骤（1）连线连线：在兄弟结点之间加一条连线。：在兄弟结点之间加一条连线。（2）切线切线：对于每个结点，除了保留与其最左孩：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线。子的连线外，切掉该结点与其它孩子的连线。（3）旋转旋转：将按（：将按（1）、（）、（2）的方法形成的二叉）的方法形成的二叉树，沿顺时针方向旋转树，沿顺时针方向旋转450,就可以得到一棵形式上就可以得到一棵形式上更为清楚的二叉树。更为清楚的二叉树。树和二叉树转化例FGHABCEDFGHABCEDFGHABCEDFHABGCEDv将树转换成二叉树树转换成的二叉树其右子树一定为空树转换成的二叉树其右子树一定为空ABCDEFG H IJKLABCDEFGHIJKL森林到二叉树的转换w 若若树采用孩子兄弟表示法树采用孩子兄弟表示法，二叉树采用，二叉树采用二叉链二叉链表表表示，则：表示，则：n任一棵树，都可以找到唯一的一棵二叉树和它任一棵树，都可以找到唯一的一棵二叉树和它对应，而且该二叉树没有右子树。对应，而且该二叉树没有右子树。(因此因此一棵一棵二二叉树，不一定保证能转换为叉树，不一定保证能转换为一棵一棵(=1)树树)n若把森林中的第二棵树的根结点，看成是第一若把森林中的第二棵树的根结点，看成是第一棵树的根结点的兄弟结点，则这两棵树可以转棵树的根结点的兄弟结点，则这两棵树可以转换为一棵二叉树（该二叉树的根结点的右子女换为一棵二叉树（该二叉树的根结点的右子女没有右子树）。没有右子树）。n依次类推，可以认为森林和二叉树是一一对应依次类推，可以认为森林和二叉树是一一对应的，从而得到二叉树和森林的转换规则的，从而得到二叉树和森林的转换规则森林到二叉树的转换w 步骤：步骤：w（1）连线连线：在兄弟（各树的根结点看作兄弟）：在兄弟（各树的根结点看作兄弟）结点之间加一条连线。结点之间加一条连线。w（2）切线切线：对于每个结点，除了保留与其最左：对于每个结点，除了保留与其最左孩子的连线外，切掉该结点与其它孩子的连线。孩子的连线外，切掉该结点与其它孩子的连线。w（3）旋转旋转：将按（：将按（1）、（）、（2）的方法形成的二）的方法形成的二叉树，沿顺时针方向旋转叉树，沿顺时针方向旋转450,就可以得到一棵形就可以得到一棵形式上更为清楚的二叉树。式上更为清楚的二叉树。AGJBC DHIKEFLM Nv将森林转换成二叉树ABGCEHFJKILMND二叉树到森林的转换w 如果B=root,LBT,RBT是一棵二叉树二叉树，F=T1,T2,Tn表示与其对应的森林森林，转换规则如下：（1）若B为空，则F为空；（2）若B非空，则F中第一棵树第一棵树T1的根的根即为二叉二叉树树B的根的根root，T1中根结点的子树森林根结点的子树森林F1是由B的的左子树左子树LBT转换而成的森林；F中除除T1之外其余之外其余树组成的森林树组成的森林F=T2,T3,Tn是由B的右子树的右子树RBT转化而成的森林。二叉树到森林的转换例1IABDFGHKCEJIABDJHCEFGKDEFGHIJLABCKFILCABEGHJKD二叉树到森林的转换例2树和森林的遍历树和森林的遍历 树的遍历树的遍历：（1）前序遍历）前序遍历 （2）后序遍历）后序遍历森林的遍历森林的遍历：（1）前序遍历）前序遍历 （2）中序遍历）中序遍历树的遍历前序遍历树前序遍历树的规则为：的规则为：若树非空，则：若树非空，则：（1）访问树的根结点；）访问树的根结点；（2）依次前序遍历树的第一棵子树、第二棵子树，）依次前序遍历树的第一棵子树、第二棵子树，后序遍历树后序遍历树的规则为：的规则为：若树非空，则：若树非空，则：（1）依次后序遍历树的第一棵子树、第二棵子树，）依次后序遍历树的第一棵子树、第二棵子树，（2）访问树的根结点；）访问树的根结点；ABCED前序遍历序列：前序遍历序列：ABCDE后序遍历序列：后序遍历序列：BCEDA树的遍历与二叉树遍历对应 树树的的前序前序遍历遍历序列与其对应的序列与其对应的二叉树的前序二叉树的前序遍遍历序列相同；历序列相同；树的后序树的后序遍历序列与其对应的遍历序列与其对应的二叉树