数据结构与算法―赵玉兰 第4章 树与二叉树

计算机学院软件工程系14.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系24.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系3内蒙古大学理工学院计算机学院生命科学学院外国语学院人文学院数学系物理系电子系计算机系计算中心网络中心汉语系历史系哲学系生物系环境系动物中心生物工程中心资源所英语系日语系行政机构树形结构是一种非线性结构，应用十分广泛。如：行政机构、目录、家谱等。计算机学院软件工程系4磁盘目录计算机学院软件工程系5红楼梦家谱计算机学院软件工程系6树和森林的概念树的定义树是由n(n≥0)个结点组成的有限集合。如果n=0，称为空树；如果n0，则有一个特定的称之为根(root)的结点，它只有直接后继，但没有直接前驱；除根以外的其他结点被划分到m(m≥0)个互不相交的子集T1,T2,…,Tm中，每个子集又都构成一棵树，称之为根的子树(subtree)。计算机学院软件工程系7树的特点每棵子树的根结点有且仅有一个直接前驱，但可以有0个或多个直接后继。树是一种典型的“层次结构”，体现出“一对多”的关系。ACGBDEFKLHMIJ计算机学院软件工程系8例4.1:Tree=(D,R)D={Book,C1,C2,C3,S1.1,S1.2,S2.1,S2.2,S2.3,S2.1.1,S2.1.2}R={Book,C1,Book,C2,Book,C3,C1,S1.1,C1,S1.2,C2,S2.1,C2,S2.2,C2,S2.3,S2.1,S2.1.1,S2.1,S2.1.2}BookC1C2C3S1.1S1.2S2.1S2.2S2.3S2.1.1S2.1.2ChapterSectionSub-Section计算机学院软件工程系9基本术语：主要来源于家谱和自然界中的树。双亲、子女（parent,child）：若a,bR，则称a是b的双亲，b是a的子女(孩子);结点度（degree）：结点所拥有的子女数；叶子（leaf）：度为0的结点；分枝结点（branchnode）：度大于0的结点；树的度：树中最大的结点的度；ABCDEFGHIJMKL计算机学院软件工程系10结点所在的层次(level)：根在第1层，其它任一结点所在的层是其双亲的层数加1。深度或高(depth)：树中结点的最大层数。兄弟(sibling)：同一双亲的结点间互称兄弟。堂兄弟(cousin)：同层的非兄弟结点互称堂兄弟。423ABCDEFGHIJMKL1计算机学院软件工程系11祖先（descendant）、子孙（ancestor）：一个结点是它所有子树中结点的祖先，而子树中的这些结点都是它的子孙。路径（path）：是一个结点序列n1,n2,n3,…,nk，并且前1个结点是后1个结点的双亲；它的长度是k-1。有序树（orderedtree）：将树中每个结点的各子树看出是从左到右是有次序的(不能互换)；否则是无序树。ABCACB无序树有序树计算机学院软件工程系12ABCDEFGHIJKLM结点A、B、C的度分别为：3、2、1叶子：K，L，F，G，M，I，J结点A的孩子：B，C，D结点B的孩子：E，F结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟树的度：3结点A的层次：1结点M的层次：4树的深度：4结点F，G为堂兄弟结点A是结点F，G的祖先计算机学院软件工程系13森林(Forest)：m(m≥0)棵互不相交的树的集合。FGABCDEHIJK由三棵树构成的森林A根BCDEFGHIJK森林由根的各子树构成的森林计算机学院软件工程系144.1树的定义和相关术语4.2二叉树4.3树和森林4.4森林与二叉树的关系4.5Huffman树与编码计算机学院软件工程系15二叉树(BinaryTree)二叉树的五种不同形态：二叉树的定义一棵二叉树是一个结点的有限集合，该集合或者为空，或者是由一个根结点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。LRLR计算机学院软件工程系16自然界很神奇！计算机学院软件工程系174.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树计算机学院软件工程系184.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树计算机学院软件工程系19二叉树的抽象数据类型ADTBinaryTree{Data是有限个结点的集合D。当D非空时，其中有一根结点t，其余结点被分为t的左子树和右子树。OperationsConstructorProcess:建立一棵空二叉树DeleteProcess:删除二叉树计算机学院软件工程系20IsEmptyProcess:判断二叉树是否是空Output:若二叉树为空，则返回true,否则返回falseSizeProcess:计算二叉树的结点数sizeOutput:sizeHeightProcess:计算二叉树的高度heightOutput:heightRootProcess:取二叉树根结点值xOutput:根结点值x计算机学院软件工程系21ParentInput:node是二叉树中的一个结点Process:求node的双亲p，若node是根，则p为空Output:pCreateBinaryTreeInput:二叉树的某种形式的定义definitionProcess:根据此定义definition构造二叉树MakeTreeInput:data是根结点值，left是左子树，right是右子树Process:创建二叉树，data是根结点值，left是其左子树，right是其右子树计算机学院软件工程系22BreakTreeProcess:拆分二叉树，data是根结点数据，left是左子树，right是右子树Output:data,left,rightPreOrderInput:Visit()是结点访问函数Process:前序遍历，对二叉树中每个结点仅调用一次Visit()Output:根据Visit()，得到前序遍历的结果InOrderInput:Visit()是结点访问函数Process:中序遍历，对二叉树中每个结点仅调用一次Visit()Output:根据Visit()，得到中序遍历的结果计算机学院软件工程系23PostOrderInput:Visit()是结点访问函数Process:后序遍历，对二叉树中每个结点仅调用一次Visit()Output:根据Visit()，得到后序遍历的结果LevelOrderInput:Visit()是结点访问函数Process:按层次对二叉树中每个结点仅调用一次Visit()Output:根据Visit()，得到层次遍历的结果}//BinaryTree计算机学院软件工程系244.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树计算机学院软件工程系25二叉树遍历二叉树的遍历是按某种次序访问树中的结点，要求每个结点访问且仅访问一次。设访问根结点记作V，遍历根的左子树记作L，遍历根的右子树记作R，计算机学院软件工程系26可能的遍历次序•前序VLR•中序LVR•后序LRVVLR123计算机学院软件工程系27前序遍历：若BT非空，则：1.访问根；2.前序遍历左子树；3.前序遍历右子树；中序遍历：若BT非空，则：1.中序遍历左子树；2.访问根；3.中序遍历右子树；后序遍历：若BT非空，则：1.后序遍历左子树；2.后序遍历右子树；3.访问根；遍历算法计算机学院软件工程系28--/+*abcdef遍历结果前序：-+a*b-cd/ef中序：a+b*c-d-e/f后序：abcd-*+ef/-计算机学院软件工程系29ABCDFHGE练习:给出该二叉树的前序、中序和后序的遍历结果。前序遍历结果：ABDGCEFH中序遍历结果：DGBAECHF后序遍历结果：GDBEHFCA计算机学院软件工程系30前序遍历的二叉树递归算法voidBinaryTree::preOrder(BinaryTreeNode*&root){if(root){coutroot→data;preOrder(root→leftChild);preOrder(root→rightChild);}}计算机学院软件工程系31二叉树递归的中序遍历算法voidBinaryTree::InOrder(BinaryTreeNode*&root){if(root){InOrder(root→leftChild);coutroot→data;InOrder(root→rightChild);}}计算机学院软件工程系32二叉树递归的后序遍历算法voidBinaryTree::postOrder(BinaryTreeNode*&root){if(root){postOrder(root→leftChild);postOrder(root→rightChild);coutroot→data;}}计算机学院软件工程系33利用二叉树后序遍历计算二叉树结点个数。intSize(BinaryTreeNodeType*&t){if(!t)return0;elsereturn1+Size(t→leftChild)+Size(t→rightChild);}应用二叉树遍历的示例计算机学院软件工程系34intDepth(BinaryTreeNodeType*&t){if(!t)return0;elsereturn1+Max(Depth(t→leftChild),Depth(t→rightChild));}利用二叉树后序遍历计算二叉树的高度。应用二叉树遍历的示例计算机学院软件工程系35以递归方式建立二叉树。递归出口：当遇到@时，是空。建立根结点。建立左子树和右子树。二叉树用根字符序列和左右子树的字符序列表示，空树用空格(或某一字符表示)表示。例如用“@”或用“-1”表示字符序列或正整数序列空结点。利用二叉树前序遍历建立二叉树。应用二叉树遍历的示例计算机学院软件工程系36如图所示的二叉树的前序遍历顺序为ABC@@DE@G@@F@@@序列是扩充二叉树的前序遍历序列。@是扩充的叶结点，它代表空指针。ABCDEGF@@@@@@@@计算机学院软件工程系37建立二叉树(二叉链表）算法:voidCreateBinaryTree(BinaryTreeNode*&root){/*按前序序列输入二叉树中结点的值(一个字符)，空格字符表示空树，构造二叉链表表示的二叉树.*/cinch；if(ch=='@')root=NULL；else{root=newBinTreeNode(ch);//生成根结点CreateBinaryTree(root-leftChild);//构造左子树CreateBinaryTree(root-rightChild);//构造右子树}cout建立成功!endl;}//CreateBinaryTree计算机学院软件工程系384.2二叉树4.2.1二叉树的ADT描述4.2.2二叉树的遍历4.2.3二叉树的性质4.2.4二叉树的实现4.2.5二叉树遍历的非递归实现4.2.6线索二叉树计算机学院软件工程系39性质1若二叉树的层次从1开始,则在二叉树的第i层最多有2i-1个结点。(i≥1)[证明用数学归纳法]性质2深度为k的二叉树最多有2k-1个结点。(h≥1)[证明用求等比数列前k项和的公式]20+21+…+2k-1=2k-1二叉树的性