第六章树和二叉树1.

第6章树和二叉树TreeandBinaryTree第六章树和二叉树目录§6.1树的定义和基本术语§6.2二叉树§6.3遍历二叉树§6.4线索二叉树§6.5树和森林§6.6哈夫曼树及其应用§6.1树的定义和基本术语6.1.1树的定义6.1.2树的术语树的定义和基本术语6.1.1树的定义树是n（n≥0）个结点的有限集。在任意一棵非空树中，有且仅有一个称为根的结点；其余结点分为m（m≥0）个互不相交的子集，每个子集又是一棵树，称为根的子树。这是一个递归的定义——在树的定义中又用到了树的概念。递归是树的固有特性。树的定义和基本术语•树的定义AFEDCBIHGKJ树根：A三个互不相交的子集：{B，E，F，J}{C}{D，G，H，I，K}每个子集都是满足树的定义的树，称为A的子树－－B子树、C子树、D子树。树根A没有直接前驱；其余结点有且仅有一个直接前驱，有0个或多个直接后继。树的特征：层次性和分支性树的定义和基本术语•树的定义§6.1树的定义和基本术语6.1.1树的定义6.1.2树的术语树的定义和基本术语•树的定义6.1.2树的术语结点的度：结点的非空子树个数树的度：树中各结点度的最大值分支结点(非终端结点)：度0的结点叶子结点(终端结点)：度=0的结点孩子：结点的子树的根称为该结点的孩子双亲：结点的直接前驱结点称为该结点的双亲兄弟：同一个双亲的结点互称为兄弟子孙：以某结点为根的各个子树上的所有结点称为该结点的子孙祖先：从树根到该结点所经过的所有分支结点称为该结点的祖先AFEDCBIHGKJ结点的层次：从树根开始自上而下编号，树根的层次为1，其余结点的层次为其双亲的层次＋1树的深度（高度）：结点层次的最大值有序树和无序树：若树中所有结点的孩子都长幼有序，位置不能互换，称为有序树，否则称为无序树。森林：m（m≥0）个树的集合AFEDCBIHGKJ树的定义和基本术语•树的定义树的基本运算：初始化空树InitTree(&T)销毁树DestroyTree(&T)创建树CreateTree(&T,definition)清空树ClearTree(&T)判断空树TreeEmpty(T)求树的深度TreeDepth(T)求双亲parent(T,cur_e)求长子LeftChild(T,cur_e)求右邻兄弟RightSibling(T,cur_e)树的定义和基本术语•树的定义插入子树InsertChild(&T,&p,i,c)删除子树DeleteChild(&T,&p,i)按层次遍历TraverseTree(T,visite())树的定义和基本术语•树的定义第六章树和二叉树目录§6.1树的定义和基本术语§6.2二叉树§6.3遍历二叉树§6.4线索二叉树§6.5树和森林§6.6哈夫曼树及其应用§6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构二叉树6.2.1二叉树的定义二叉树(BinaryTree)一种受限的树型结构,它的特点是每个结点至多只有2棵子树,而且,二叉树的子树有左右之分,其次序不能颠倒。根左子树右子树二叉树•二叉树的定义从二叉树的定义得知：1.二叉树可以为空，称为空二叉树；2.非空二叉树每个节点至多有两棵子树：左子树和右子树；3.左、右子树有次序关系，不能互换;4.二叉树可以有5种基本形态：ACIBGFHEDØ二叉树•二叉树的定义三个结点的无序树有两种不同的形态：三个结点的二叉树有五种不同的形态：二叉树•二叉树的定义二叉树的基本运算：初始化空二叉树InitBiTree(&T)销毁二叉树DestroyBiTree(&T)创建二叉树CreateBiTree(&T,definition)清空二叉树ClearBiTree(&T)判断空二叉树BiTreeEmpty(T)求二叉树深度BiTreeDepth(T)求双亲parent(T,e)求左孩子LeftChild(T,e)求右孩子RightChild(T,e)二叉树•二叉树的定义求左兄弟LeftSibling(T,e)求右兄弟RightSibling(T,e)插入子树InsertChild(T,p,LR,c)删除子树DeleteChild(T,p,LR)先序遍历二叉树PreOrderTraverse(T,visite())中序遍历二叉树InOrderTraverse(T,visite())后序遍历二叉树PostOrderTraverse(T,visite())按层次遍历levelTraverse(T,visite())二叉树•二叉树的定义§6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构二叉树6.2.2二叉树的性质性质1.在二叉树的第i层上至多有2i-1个结点；性质2.深度为k的二叉树上至多有2k-1个结点12211kkii二叉树•二叉树的性质性质3.设二叉树中有n2个度为2的结点，n1个度为1的结点，n0个度为0的结点，则有：n0=n2+1n=n0+n1+n2(1)树枝数=n0×0＋n1×1＋n2×2=n1+2n2n=树枝数+1=n1+2n2+1(2)由(1)、(2)可得n0=n2+1二叉树•二叉树的性质满二叉树：结点总数n＝2k－1所有非终端结点的度都等于2且所有树叶都分布在同一个层次上132675489101112131415二叉树•二叉树的性质完全二叉树：将深度为k，有n个结点的二叉树自上而下，自左向右进行编号，编号与深度为k的满二叉树中前n个结点一致。前k－1层是满的，第k层可以不满，但第k层结点集中在左侧132675489101112132675489101112二叉树•二叉树的性质性质4.具有n个结点的完全二叉树的深度为k＝log2n+1或k=log2(n+1)证明：设完全二叉树的深度为k，根据完全二叉树的定义有2k－1-1n≤2k－1或2k－1≤n2k取对数有k－1≤log2nk∵k是整数，∴k＝log2n+1二叉树•二叉树的性质性质5.将完全二叉树自上而下，自左向右地编号，树根的编号为1。对于编号为i的结点X有：1.若i＝1，则X是根；若i1,则X的双亲的编号为i/2;2.若X有左孩子，则X左孩子的编号为2i；3.若X有右孩子，则X右孩子的编号为2i＋1；4.若i为奇数且i1，则X的左兄弟为i－1；5.若i为偶数且in，则X的右兄弟为i＋1；二叉树•二叉树的性质2i+12iii/2i+12i2i+1ii/2i-1132675489101112131415i是偶数i是奇数二叉树•二叉树的性质§6.2二叉树6.2.1二叉树的定义6.2.2二叉树的性质6.2.3二叉树的存储结构二叉树一、二叉树的顺序存储结构二叉树的性质5为用数组存储完全二叉树提供了依据：ACBFGEDHIJKLABCDEFGHIJKL0123456789101112123456789101112二叉树•二叉树的存储结构对于普通二叉树，可以将其补足成完全二叉树后再进行编号:ACBEFDGH1938765421112131410ABCØDEFØØGØØØH01234567891011121314BT二叉树•二叉树的存储结构这样表示的二叉树可能会造成空间的极大浪费，因而实用时不常采用。比如有5个结点的右单枝树,需为其分配个结点空间。ABCDE二叉树•二叉树的存储结构?31二、二叉树的链式存储结构－－二叉链表lchilddatarchild左孩子指针结点值右孩子指针typedefstructBiTNode{ElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;二叉树•二叉树的存储结构ACBGEDIFHB∧D∧E∧F∧∧H∧G∧∧CA∧I∧bt每个非空指针表示一个树枝n个结点的二叉树共有n＋1个空指针二叉链表根指针二叉树•二叉树的存储结构二叉树•二叉树的存储结构lchildparentdatarchild左孩子指针双亲指针结点值右孩子指针ACBFDE∧A∧B∧CD∧∧F∧∧E∧bt三叉链表“双向链”第六章树和二叉树目录§6.1树的定义和基本术语§6.2二叉树§6.3遍历二叉树§6.4线索二叉树§6.5树和森林§6.6哈夫曼树及其应用§6.3遍历二叉树6.3.1先序、中序和后序遍历6.3.2算术表达式的二叉树表示6.3.3二叉树的运算举例6.3.4按层次遍历二叉树6.3.5构造二叉链表二叉树•遍历二叉树6.3.1先序、中序和后序遍历二叉树遍历：按某种次序访问二叉树的所有结点，且每个结点仅访问一次。二叉树•遍历二叉树根据二叉树的结构：左子树_根_右子树，我们可以把对二叉树的遍历分解为三项子任务：访问根－－D遍历左子树－－L遍历右子树－－R根据这三项任务的执行次序的不同，有六种可能的遍历方案：DLR、LDR、LRD先左后右DRL、RDL、RLD先右后左如果约定先左后右，则取前三种方案。二叉树•遍历二叉树根据访问根的时机不同，将这三种遍历方案分别称为:先根遍历（先序遍历）DLR中根遍历（中序遍历）LDR后根遍历（后序遍历）LRD二叉树•遍历二叉树若二叉树为空，则空操作；否则(1)访问根；(2)先序遍历左子树(3)先序遍历右子树先序遍历的递归定义：二叉树•遍历二叉树voidpreorder(BiTreebt){if(!bt)return;visite(bt-data);//访根preorder(bt-lchild);preorder(bt-rchild);}若二叉树为空，则空操作；否则,(1)中序遍历左子树(2)访问根；(3)中序遍历右子树中序遍历的递归定义：二叉树•遍历二叉树voidinorder(BiTreebt){if(!bt)return;inorder(bt-lchild);visite(bt-data);//访根inorder(bt-rchild);}若二叉树为空，则空操作;否则,(1)后序遍历左子树(2)后序遍历右子树(3)访问根；后序遍历的递归定义：二叉树•遍历二叉树voidpostorder(BiTreebt){if(!bt)return;postorder(bt-lchild);postorder(bt-rchild);visite(bt-data);//访根}ACBGEDIFH先序遍历序列：中序遍历序列：后序遍历序列：ABDGECFHIDGBEACHIFGDEBIHFCA二叉树的遍历二叉树•遍历二叉树ACBHIDEFG先序遍历序列：中序遍历序列：后序遍历序列：练习:二叉树的遍历二叉树•遍历二叉树???ABDGHIECFGDHIBEACFGIHDEBFCAvoidpreorder(BiTreebt){if(!bt)return;visite(bt-data);preorder(bt-lchild);preorder(bt-rchild);}voidinorder(BiTreebt){if(!bt)return;inorder(bt-lchild);visite(bt-data);inorder(bt-rchild);}voidpostorder(BiTreebt){if(!bt)return;postorder(bt-lchild);postorder(bt-rchild);visite(bt-data);}现将三个遍历算法中的visite语句去掉，我们发现这三个算法完全一样。这说明三种遍历的路径是一样的，只是访问根的时机不同而已。二叉树•遍历二叉树StatusInOrder(BiTreeT,Status(*Visit)(TElemTypee)){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);