数据结构与算法分析lecture6(二叉树).ppt
Binary Trees (二叉树),Tao Liang College of software SiChuan University,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个主要问题,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队,树形结构,图形结构,数据结构的三个主要问题,线性结构,A , B , C , ······· ,X ,Y , Z,学 生 成 绩 表,线性表结点间是以线性关系联结,1数据的逻辑结构,2、数据的存储结构,3、数据的运算:检索、排序、插入、删除、修改等。,A线性结构,B非线性结构,A 顺序存储,B 链式存储,线性表,栈,队列,树形结构,图形结构,数据结构的三个主要问题,树形结构,全校学生档案管理的组织方式,树形结构 结点间具有分层次的连接关系,Binary Tree,Definitions and Properties Binary Tree Traversals Binary Tree Node Implementions Binary Search Trees Heaps and Priority Queues Huffman Coding Trees,Definitions and Properties,二叉树的定义:由结点(node)的有限集合组成,这个集合或者为空(empty),或由一个根结点(root)和两棵分别称为根的左子树(left subtree)和右子树(right subtree)的互不相交的二叉数组成。,介绍几个概念: 结点(Node):树中的元素,包含数据项及若干指向其子树的分支。 结点的度(Degree):结点拥有的子树数。 结点的层次:从根结点开始算起,根为第0层。 叶子(Leaf):度为零的结点,也称端结点。 孩子(Child):结点子树的根称为该结点的孩子结点。 兄弟(Sibling):同一双亲的孩子。 双亲(Parent):孩子结点的上层结点,称为这些结点的双亲。 结点的深度(Depth): 从根结点到该结点的路径的长度。 树的高度(Height):等于最深结点的深度加1。,Two different trees,满二叉树(full binary tree ) 的每一个结点或者是一个分支结点,并恰有两个非空子结点;或者是叶结点. 完全二叉树(complete binary tree)有严格的形状要求:从根结点起每一层从左到右填充.一棵高度为d的完全二叉树除了d-1层以外,每一层都是满的.底层叶结点集中在左边的若干位置上.,The Full Binary Tree Theorem (满二叉树定理),Theorem 5.1 Full Binary Tree Theorem:The number of leaves in a non-empty full binary tree is one more than the number of internal nodes. Theorem 5.2 The number of empty subtrees in a non-empty binary tree is one more than of nodes in the tree.,A Binary Tree Node ADT,Clearly there are activities that relate to nodes(e.g.,reach a child or get a value),and activities that relate to trees(e.g.,tree initialization). So nodes and trees should be separate classes in a C+ implementation.,/binary tree node abstract class template class BinNode public : /return the nodes element virtual Elem,/set the nodes left child virtual void setLeft(BinNode*)=0; /return the nodes right child virtual BinNode* right() const =0; /set the nodes right child virtual void setRight(BinNode*)=0; /return true if the node is a leaf virtual bool isleaf() =0; ;,Binary Tree Traversals (二叉树的遍历),查找某个结点,或对二叉树中全部结点进行某种处理,就需要 遍历。 (1)遍历定义 遍历是指按某条搜索路线寻访树中每个结点,且每个结点只被访问一次。 按先左后右的原则,一般使用三种遍历: preorder traversal 前序遍历 inorder traversal 中序遍历 posterorder traversal 后序遍历,前序遍历(D L R): 访问根结点,按前序遍历左子树,按前序遍历右子树。 A B D C E G F H I 中序遍历(L D R): 按中序遍历左子树,访问根结点,按中序遍历右子树。 B D A G E C H F I 后序遍历(L R D): 按后序遍历左子树,按后序遍历右子树,访问根结点。 二叉树为空时,执行空操作,即空二叉树已遍历完。 D B G E H I F C A,(2)遍历算法,先序遍历:D L R 中序遍历:L D R 后序遍历:L R D,A,D,B,C,T1,T2,T3,D L R,以先序遍历D L R为例演示遍历过程,ABDC,BDAC,DBCA,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,返回,返回,返回,返回,A,C,B,D,返回,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,template void PreOder (BinNode* subroot) if(subroot =NULL) return; visit(subroot); PreOrder (subroot-left(); PreOrder (subroot-right(); /*前序遍历*/,?,中序遍历二叉树的递归算法: template void InOder (BinNode* subroot) if(subroot =NULL) return; InOrder (subroot-left(); visit(subroot); InOrder (subroot-right(); /*中序遍历*/,后序遍历二叉树的递归算法: template void PostOder (BinNode* subroot) if(subroot =NULL) return; PostOrder (subroot-left(); PostOrder (subroot-right(); visit(subroot); /*后序遍历*/,Example5.4 A function that counts the number of nodes in a binary tree. template int count(BinNode* subroot) if(subroot = NULL) return 0; return 1+count(subroot-left() +count(subroot-right(); ,Binary Tree Node Implemention (二叉树的实现),A typical pointer-based binary tree implemention, Each node stores two child pointers and a value.,A binary tree node class implemention(二叉树结点类的实现),/ Binary tree node class template class BinNodePtr : public BinNode private: Elem it; / The node's value BinNodePtr* lc; / Pointer to left child BinNodePtr* rc; / Pointer to right child,public: / Two constructors - with and without initial values BinNodePtr() lc = rc = NULL; BinNodePtr(Elem e, BinNodePtr* l =NULL, BinNodePtr* r =NULL) it = e; lc = l; rc = r; BinNodePtr() / Destructor Elem ,inline BinNode* left() const return lc; void setLeft(BinNode* b) lc = (BinNodePtr*)b; inline BinNode* right() const return rc; void setRight(BinNode* b) rc = (BinNodePtr*)b; bool isLeaf() return (lc = NULL) ,-,*,*,+,*,c,a,x,2,x,4,An expression tree for 4x(2x+a)-c Leaves and internal nodes use different definition,How to differentiate leaf from internal nodes,One way to differentiate leaf from internal nodes is to use the C+ union construct,as shown in Figure 5.9(P 152) C+ provides a better approach to differentiating leaf from internal nodes through the use of class inheritance,as shown in Figure 5.10(P 153) Another way to differentiate leaf from internal nodes is to use a virtual base class and separate node classes for the two types,as shown in Figure 5.11(P 155),Comparison of different implementations,P95-99,Space Requirements,Discuss,Array Implementation for Complete Binary Trees,Properties of complete Binary Trees: Complete binary trees have all levels except the bottom filled out completely,and the bottom level has all of its nodes filled in from left to right.,A complete binary tree and its array implementation,The formulae for calculating the array indices of the various relatives of a node are as follows:,n is the total number of nodes in the tree. r is the index of the node in question,which must fall in the range 0 to n-1.,