数据结构之二叉树1.

数据结构与算法For软件学院08级本科生2009-2010秋4二叉树1二叉树•二叉树及相关定义、主要性质•二叉树的存储结构•二叉树的遍历（周游）递归和非递归•穿线（线索）二叉树二叉树•二叉树的定义二叉树：是n(n≥0)个结点的有限集合。n=0的树称为空二叉树；n0的二叉树由一个根结点以及两棵互不相交的、分别称为左子树和右子树的二叉树组成。ABCDEIJGH根结点左子树右子树二叉树•基本特征:•①每个结点最多只有两棵子树（不存在度大于2的结点）•②左子树和右子树次序不能颠倒。下面是两棵不同的树:BACEDFGBACEDFG二叉树•基本形态AABABABC空二叉树只有根结点的二叉树右子树为空左子树为空左、右子树均非空问：具有3个结点的二叉树可能有几种不同形态？有5种二叉树一般的树有几种？结点：包含一个数据元素及若干指向其子树的分支。结点的度：结点拥有的子树个数。二叉树的基本术语EFBAKLMHID叶子(leaf)：度为0的结点，也称为终端结点。分支结点：度不为0的结点，也称为非终端结点或内部结点。二叉树的基本术语EFBAKLMHID路径与路径长度：路径的长度等于路径所通过的结点数目减1(即路径上分支数目)。子女结点、父母结点、祖先、后继二叉树的基本术语EFBAKLMHID结点的层次：根结点的层数为0，根的孩子层数为1，依此类推。二叉树深度：树中结点的最大层次。二叉树的高度：层数最大的叶结点的层数加1。0123二叉树的基本术语EFBAKLMHID满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的二叉树称为满二叉树。BACEDFGHIJKLMNO满二叉树特点•高度为k且有2k-1个结点的二叉树。–每一层上的结点数都是最大结点数；–所有的分支结点的度数都为2；–叶子结点都在同一层次上。123114589121367101415完全二叉树如果一棵深度为k，有n个结点的二叉树中各结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应的二叉树称为完全二叉树。（只有最下两层结点可以度小于2）BACEDFGHIJ完全二叉树特点•叶子结点只可能在层次最大的两层上出现；•前k-1层中的结点都是“满”的，且第k层的结点都集中在左边。123114589126710判断是否为完全二叉树1234567123456思考：满二叉树与完全二叉树的关系？扩充二叉树•当二叉树里出现空的子树时，就增加新的、特殊的结点——空树叶–对于原来二叉树里度数为1的分支结点，在它下面增加一个空树叶–对于原来二叉树的树叶，在它下面增加两个空树叶•扩充的二叉树是满二叉树，新增加的空树叶(外部结点)的个数等于原来二叉树的结点(内部结点)个数加1扩充二叉树扩充二叉树•外部路径长度E从扩充的二叉树的根到每个外部结点的路径长度之和•内部路径长度I扩充的二叉树里从根到每个内部结点的路径长度之和•E和I两个量之间的关系为E=I+2n（证明见课本）二叉树的主要性质书上列举的6个性质–大都可以计算出来•满二叉树定理：非空满二叉树树叶数等于其分支结点数加1。•满二叉树定理推论：一个非空二叉树的空子树(指针)数目等于其结点数加1。•对任意一棵二叉树，若终端结点数为n0，度为2的结点数为n2，则n0=n2+1。二叉树的主要性质•在二叉树的第i层上至多有2i个结点(根为第0层，i≥0)。•高度为k(深度为k-1)的二叉树至多有2k-1个结点•有n个结点（n0）的完全二叉树的高度为log2(n+1)(深度为log2(n+1)-1)二叉树性质•对完全二叉树中编号为i的结点(0≤i≤n-1,n≥1,n为结点数)有：ABCDEHIJKFG012345678910完全二叉树（1）若i=0,则结点i是二叉树的根，无双亲。（2）若i0,则它的双亲结点的编号为(i-1)/2。当i为偶数时,其双亲结点的编号为i/2-1,它是右孩子结点,当i为奇数时,其双亲结点的编号为(i-1)/2,它是左孩子结点。二叉树性质ABCDEHIJKFG012345678910完全二叉树(3)若编号为i的结点有左孩子结点,则左孩子结点的编号为2i+1；若编号为i的结点有右孩子结点,则右孩子结点的编号为(2i+2)。二叉树性质ABCDEHIJKFG012345678910完全二叉树(4)若n为偶数,则每个分支结点都既有左孩子结点,也有右孩子结点；若n为奇数,则编号最大的分支结点(编号为(n-1)/2)只有左孩子结点,没有右孩子结点,其余分支结点都有左、右孩子结点。二叉树性质ABCDEHIJKFG012345678910完全二叉树二叉树的存储结构二叉树的存储结构主要有三种：•顺序存储结构•链式存储结构•仿真指针存储结构BACEDFGHIJKLMNOBACEDFGHIJABCDONMLKJIHGFE12043576118109121314ABCDJIHGFE1204357689完全二叉树的结点可按从上至下和从左至右的次序存储在一维数组中，其结点之间的关系可由公式计算得到。顺序存储结构对于一般的非完全二叉树显然不能直接使用二叉树的顺序存储结构。可以首先在非完全二叉树中增添一些并不存在的空结点使之变成完全二叉树的形态，然后再用顺序存储结构存储。BACDEGFBACDEGF(a)一般二叉树(b)完全二叉树形态(c)在数组中的存储形式ABC∧G∧∧F∧∧∧ED1204357611810912数组下标–顺序存储表示#defineMAX_TREE_SIZE100//最大结点数TypedefTElemTypeSqBiTree[MAX_TREE_SIZE];//0号根结点SqBiTreebt;高度为4，有7个结点的一般二叉树的顺序存储abcdefggf0000edcba1234567891011浪费4个高度为4，只有4个右孩子的二叉树的顺序存储0000400030002011234123456789101112131415浪费11个•顺序存储结构适用于满二叉树和完全二叉树的存储。二叉树的链式存储结构二叉树的链式存储结构是用指针建立二叉树中结点之间的关系。二叉树最常用的的链式存储结构是二叉链。二叉链存储结构的每个结点包含三个域，分别是数据域data、左孩子指针域leftChild和右孩子指针域rightChild。二叉链存储结构中每个结点的图示结构为：rightChilddataleftChild二叉链表的存储表示typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*Bitree;图二叉链存储结构的二叉树root∧A∧BC∧D∧E∧F∧G∧∧∧rootA∧BC∧D∧E∧F∧G∧∧∧(a)不带头结点的二叉树(b)带头结点的二叉树ABCDEFGABCDEFG^^^^^^^^在n个结点的二叉链表中，有n+1个空指针域。二叉树的仿真指针•二叉树的仿真指针存储结构是用数组存储二叉树中的结点，数组中每个结点除数据元素域外，再增加仿真指针域用于仿真常规指针建立二叉树中结点之间的关系。三叉链表–结点包括数据域，左子树指针域、双亲域和右子树指针域。lchilddataparentrchild三叉链表的存储表示typedefstructTriTNode{TElemTypedata;structTriTNode*lchild,*rchild,*parent;}TriTNode,*Tritree;ABCDEFG^^^^^^^^^ABCDEFG遍历（周游）二叉树遍历是树结构的一种常用的、重要的运算，是树的其它运算的基础。•遍历–按一定的规律，走遍二叉树的每个结点，使每个结点被访问一次，且只被访问一次。遍历的过程就是把非线性结构的二叉树中的结点排成一个线性序列的过程。•遍历方式–广度优先遍历（逐层遍历）•从根节点开始，向下逐层访问每个节点，在每一层次上，从左到右访问每个节点。–深度优先遍历按根、左子树、右子树三个部分进行访问132910212252031广度优先（逐层）遍历HCFEDAH入队出队HCDCFEDAFEA队列实现广度优先遍历演示队列实现广度优先遍历templateclassTvoidLevelOrder(BinaryTreeNodeT*t){//对*t逐层遍历BinaryTreeNodeT*p=t;LinkedQueueBinaryTreeNodeT*Q;while(p){coutp-data;//访问pif(p-LeftChild)Q.Add(p-LeftChild);//将p的孩子放入队列if(p-RightChild)Q.Add(p-RightChild);//访问下一个结点if(Q.IsEmpty())return;elseQ.Delete(p);//相当于p=s.top();s.pop();}}按根、左子树、右子树三个部分进行访问（深度优先）•设D表示根结点，L表示左子树，R表示右子树，则对这三个部分进行访问的组合共有6种，–DLR–DRL–LDR–LRD–RDL–RLD•若限定先左后右，则只有DLR，LDR，LRD三种，分别称为先序遍历，中序遍历，后序遍历。•先序遍历•中序遍历•后序遍历深度优先遍历若二叉树为空，则返回；否则(1)访问根结点；(2)先序遍历左子树；(3)先序遍历右子树；AABCABC先序遍历AABCDEFGH000000000beginend先序遍历顺序:ABDFGCEHABDFGCEH先序遍历演示先序遍历递归算法templateclassTvoidPreOrder(BinaryTreeNodeT*t){//对*t进行前序遍历if(t){coutt-data;//访问根结点PreOrder(t-LeftChild);//前序遍历左子树PreOrder(t-RightChild);//前序遍历右子树}}递归算法转化为非递归算法•递归算法优点–形式简洁，可读性好，正确性容易得到证明，可以给程序的编制和调试带来很大的方便。•递归算法缺点–递归调用比非递归调用消耗的时间与存储空间多，运行的效率较低。所有的递归算法都可转化成相应的非递归算法。将递归算法改成相应的非递归算法需要一个栈来记录调用返回的路径。通过分析递归调用的执行过程，并观察栈的变化就可得到相应的非递归算法。先序遍历的非递归实现•先序的非递归程序实现：1、根结点进栈2、结点出栈，被访问3、结点的右、左儿子（非空）进栈4、反复执行2、3，至栈空为止。先序遍历的非递归实现BCDELA先序：A、L、B、E、C、De.g:ACLCEBCECDCA出栈访问L出栈访问B出栈访问E出栈访问C出栈访问D出栈访问后，栈空结束A进栈C、L进栈E、B进栈D进栈给出先序遍历的非递归实现的代码templateclassTvoidPreOrderTranverse(BinaryTreeNodeT*t){StackBinaryTreeNodeT*s(20);BinaryTreeNodeT*p;p=t;s.add(p);while(!s.IsEmpty()){s.delete(p);//相当于p=s.top();s.pop();coutp-data;if(p-rightchild)s.add(p-rightchild);if(p-leftchild)s.add(p-leftchild);}}先序遍历的非递归实现若二叉树为空，则返回；否则(2)访问根结点；(1)中(根)序遍历左子树；(3)中(根)序遍历右子树；AAABCBAC中序遍历ABCDEFGH000000000beginend中序遍历顺序:ABDFGCEHBFDGACEH中序遍历演示DGBAECH中序遍历：ABCDGEFHF将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根结点的右侧的形式绘制，则对每一个结点做一条垂线，映射到水