第六章树状结构.

1第六章树和二叉树26.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码36.1树的类型定义4数据对象D：D是具有相同特性的数据元素的集合。若D为空集，则称为空树。否则:(1)在D中存在唯一的称为根的数据元素root；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。数据关系R：5基本操作：查找类插入类删除类6Root(T)//求树的根结点查找类：Value(T,cur_e)//求cur_e结点的元素值Parent(T,cur_e)//求cur_e结点的双亲结点LeftChild(T,cur_e)//求cur_e结点的最左孩子RightSibling(T,cur_e)//求cur_e结点的右兄弟TreeEmpty(T)//判定树是否为空树TreeDepth(T)//求树的深度TraverseTree(T,Visit())//遍历7InitTree(&T)//初始化置空树插入类：CreateTree(&T,definition)//按定义构造树Assign(T,&cur_e,value)//给cur_e结点赋值InsertChild(&T,&p,i,c)//插入c为T中P所指结点的第i棵子树8ClearTree(&T)//将树清空删除类：DestroyTree(&T)//销毁树的结构DeleteChild(&T,&p,i)//删除结点p的第i棵子树9ABCDEFGHIJMKLA(B(E,F(K,L)),C(G),D(H,I,J(M)))T1T3T2树根例如:树的图示表示法树的广义表表示法10ABDCJIHMEFGKL树的嵌套集合表示法11(１)有确定的根；(２)树根和子树根之间为有向关系。有向树：有序树：子树之间存在确定的次序关系。无序树：子树之间不存在确定的次序关系。12基本术语13结点:结点的度:树的度:叶子结点:分支结点:数据元素+若干指向子树的分支分支的个数（子树的个数）树中所有结点的度的最大值度为零的结点度大于零的结点包含根结点和中间结点DHIJM14(从根到结点的)路径：孩子结点、双亲结点兄弟结点、堂兄弟祖先结点、子孙结点结点的层次:树的深度：由从根到该结点所经分支和结点构成ABCDEFGHIJMKL假设根结点的层次为1，根的孩子为第2层，如果某结点在第L层,则其子树的根在L+1层。树中叶子结点所在的最大层次15任何一棵非空树是一个二元组Tree=（root，F）其中：root被称为根结点F被称为子树森林森林：是m（m≥0）棵互不相交的树的集合ArootBCDEFGHIJMKLF16对比树型结构和线性结构的结构特点17线性结构树型结构（非线性结构）第一个数据元素(无前驱)根结点(无前驱)最后一个数据元素(无后继)多个叶子结点(无后继)其它数据元素(一个前驱、一个后继)其它数据元素(一个前驱、多个后继)18赵老根赵跃进赵小康赵改革赵开放赵抗美赵援朝赵卫兵赵永红196.2二叉树的类型定义20二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(二叉树的度最大为2)ABCDEFGHK根结点左子树右子树21二叉树的五种基本形态：N空树只含根结点NNNLRR右子树为空树L左子树为空树左右子树均不为空树22二叉树的主要基本操作：查找类插入类删除类23Root(T);Value(T,e);Parent(T,e);LeftChild(T,e);RightChild(T,e);LeftSibling(T,e);RightSibling(T,e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T,Visit());InOrderTraverse(T,Visit());PostOrderTraverse(T,Visit());LevelOrderTraverse(T,Visit());24InitBiTree(&T);Assign(T,&e,value);CreateBiTree(&T,definition);InsertChild(T,p,LR,c);25ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T,p,LR);26二叉树的重要特性27性质1：二叉树第i层上至多有2i-1个结点。(i≥1)用归纳法证明：归纳基：归纳假设：归纳证明：i=1层时，只有一个根结点：2i-1=20=1；假设当j=i-1时,命题成立；即j层最多有2j-1（2i-2）个节点二叉树上每个结点至多有两棵子树，则第i层的结点数=2i-22=2i-1。28•性质2：深度为k的二叉树上至多含2k-1个结点（k≥1）。证明：基于上一条性质，深度为k的二叉树上的结点数至多为20+21++2k-1=2k-1。（等比数列求和）29•性质3：对任何一棵二叉树，若它含有n0个叶子结点（0度节点）、n2个度为2的结点，则必存在关系式：n0=n2+1。证明：二叉树上结点总数n=n0+n1+n2又二叉树上分支总数b=n1+2n2而b=n-1=n0+n1+n2-1由此，n0=n2+1。30两类特殊的二叉树：满二叉树：指的是深度为k且含有2k-1个结点的二叉树。完全二叉树：树中所含的n个结点和满二叉树中编号为1至n的结点一一对应。（编号的规则为，由上到下，从左到右。）123456789101112131415abcdefghij特点1.叶子结点出现在最后2层2.对于任意结点，若其右分支下的子孙的最大层次为L,则左分支下的子孙的最大层次为L或L+131•性质4：具有n个结点的完全二叉树的深度为log2n+1(k≥1）证明：设完全二叉树的深度为k则根据第二条性质得2k-1-1n≤2k-1即k-1≤log2nkk是整数，因此，k=log2n+132•性质5：若对含n个结点的完全二叉树从上到下且从左至右进行1至n的编号，则对完全二叉树中任意一个编号为i的结点：(1)若i=1，则该结点是二叉树的根，无双亲，否则，编号为i/2的结点为其双亲结点；(2)若2i＞n，则序号为i的结点无左孩子；否则，编号为2i的结点为其左孩子结点；(3)若2i+1＞n，则该序号为i的结点无右孩子；否则，编号为2i+1的结点为其右孩子结点。1.深度为k的完全二叉树至少有个结点，至多有个结点，k和n之间关系为。2.设高度为h的二叉树只有度为偶数的结点，则至少有个结点，至多有个结点。3.一棵有124个叶子结点的完全二叉树，最多有个结点。4.完全二叉树的某结点若无左孩子，则必为叶子结点？5.具有n个结点的满二叉树叶子结点有。2k-12k-1log2n+12h-12h-1248(n+1)/2346.3二叉树的存储结构二、二叉树的链式存储表示一、二叉树的顺序存储表示35#defineMAX_TREE_SIZE100//二叉树的最大结点数typedefunsignedcharTElemType;typedefTElemTypeSqBiTree[MAX_TREE_SIZE+1];SqBiTreebt;一、二叉树的顺序存储表示36例如:ABCDEFABD0C0E000000F12345678910111213142511437一般树按完全二叉的方式存储非常浪费空间！深度为K的单支树，需要2k个空间37二、二叉树的链式存储表示1.二叉链表2．三叉链表38ADEBCFrootlchilddatarchild结点结构:1.二叉链表39typedefcharTElemType;typedefstructNode{//结点结构TElemTypedata;structNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;lchilddatarchild结点结构:C语言的类型描述如下:40ADEBCFroot2．三叉链表parentlchilddatarchild结点结构:41typedefstructNode{//结点结构structNode*parent;//双亲指针TElemTypedata;structNode*lchild,*rchild;//左右孩子指针}TriTreeNode,*TriTree;parentlchilddatarchild结点结构:C语言的类型描述如下:426.4二叉树的遍历43一、问题的提出二、先左后右的遍历算法三、算法的递归描述四、遍历算法的非递归描述44顺着某一条搜索路径寻访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。（将树线性化）一、问题的提出（寻找某个结点）“访问”的含义可以很广，如：输出结点的信息或判定结点满足某些条件等。45“遍历”是任何数据结构均有的操作，对线性结构而言，只有一条搜索路径(因为每个结点均只有一个后继)故不需要另加讨论。而二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径遍历的问题。46对“二叉树”而言，可以有三条搜索方法：•1．先上后下的按层次遍历；•2．先左（子树）后右（子树）的遍历；•3．先右（子树）后左（子树）的遍历。47二、先左后右的遍历算法先（根）序的遍历算法中（根）序的遍历算法后（根）序的遍历算法48例：将如下表达式a+b*(c-d)-e/f存入一个树结构。叶子结点为操作数中间结点为运算符f/e-dc-ab*+49若二叉树为空树，则空操作；否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。先（根）序的遍历算法：顺序：-+a*b-cd/ef正好是前缀表达式50若二叉树为空树，则空操作；否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。中（根）序的遍历算法：顺序：a+b*c-d-e/f正好是中缀表达式51若二叉树为空树，则空操作；否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。后（根）序的遍历算法：顺序：abcd-*+ef/-正好是后缀表达式52三、算法的递归描述voidPreOrder(BiTreeT,void(*Visit)(TElemType)){if(T){visit(T-data);//访问根结点PreOrder(T-lchild,visit);//遍历左子树PreOrder(T-rchild,visit);//遍历右子树}}ADBT53voidInOrder(BiTreeT,void(*Visit)(TElemType)){//中序遍历二叉树if(T){InOrder(T-lchild,visit);//遍历左子树visit(T-data);//访问根结点InOrder(T-rchild,visit);//遍历右子树}}54voidPostOrder(BiTreeT,void(*Visit)(TElemType)){//后序遍历二叉树if(T){PostOrder(T-lchild,visit);//遍历左子树PostOrder(T-rchild,visit);//遍历右子树visit(T-data);//访问根结点}}55可以这样理解：无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根结点出发，逆时针沿二叉树外缘移动对每个结点均途经三次。先序遍历：第一次经过结点时访问。中序遍历：第二次经过结点时访问。后序遍历：第三次经过结点时访问。ABΦΦΦ12356四、先序遍历算法的非递归描述1.初始化设置一个栈；2.根结点指针入栈；3.堆栈非空时：（1）出栈取得结点指针，visit该结点（2）若该结点右子树不空，右子树指针进栈；（3）若该结点左子树不空，左子树指针进栈；57voidpre_s(BiTreet){SqStacks;BiTreep;Init_Sq(s);if(t){push(s,t);while(