《ds07_树2概要》由会员分享，可在线阅读，更多相关《ds07_树2概要（43页珍藏版）》请在金锄头文库上搜索。
1、第7章 树与二叉树,2,树和二叉树的基本概念 二叉树和树的存储结构 二叉树的抽象类 二叉树的遍历和树的遍历 二叉排序树 赫夫曼树及其应用,主要内容,3,二叉树的抽象类,二叉树结点类 二叉树的抽象类,4,结点类的定义： /类的提前引用声明：二叉树类 template class BinaryTree; template class BinaryTreeNode /将BinaryTree类声明为BinaryTreeNode类的友元类 friend class BinaryTree;,5,public: BinaryTreeNode ( ); /构造函数 BinaryTreeNode （T /取左右
2、结点指针,6,void SetData(T /右孩子指针 ；,7,释放子树空间：释放以某结点为根的子树中所有结点的存储空间，但不释放根结点所占的存储空间。 template void BinaryTreeNode:release( ) if(Lchild!=NULL) Lchild-release( ); /递归调用释放左子树 delete Lchild; Lchild=NULL: if(Rchild!=NULL) Rchild-release( ); /递归调用释放右子树 delete Rchild; Rchild=NULL: ,8,设置新的左子树：在给一个左子树或右子树重新赋值之前，必须先
3、释放掉该指针原来所指向的子树的所有结点。 template void BinaryTreeNode : SetLeft (BinaryTreeNode *L) Lchild-release( ); /释放原来的左子树 delete Lchild; /释放左子树的根结点 Lchild=L; /修改左指针,9,设置新的右子树 template void BinaryTreeNode :SetRight (BinaryTreeNode *R) Rchild-release( ); /释放原来的右子树 delete Rchild; /释放右子树的根结点 Rchild=R; /修改右指针,10,二叉树的
4、抽象类,template class BinaryTree public: BinaryTree( ); /构造一棵空的二叉树 BinaryTree(const BinaryTree,11,/在以t为根的二叉树中查找，找到值等于value的结点 时，返回该结点地址，否则返回空指针 virtual BinaryTreeNode*Find (BinaryTreeNode *t, T /在当前二叉树中查找数据域值等于value的结点 virtual BinaryTreeNode*Find(T &value)=0；,12,/在当前二叉树中删除一个节点 virtual int Delete(const
5、T /取根,13,/输入运算符重载 frind istream ,14,构造空树的函数 template BinaryTree:BinaryTree( ) root=NULL; 拷贝构造函数 template BinaryTree:BinaryTree(const BinTree ,15,多参数构造函数：新构造一个根结点，将已知两棵树分别作为左、右子树。调用结点类的带参构造函数。 template BinaryTree:BinaryTree( T value, BinaryTreeNode *left, BinaryTreeNode *right) root=new BinaryTreeNod
6、e (value, left, right); ,16,析构函数：使用结点类中的release函数， release函数只删除两个子树中的结点，因此最后需要删除根结点。 template BinaryTree : BinaryTree( ) root-release( ); delete root; root=NULL;,17,删除整棵树中的所有结点：删除树中所有的结点，最后将根指针置空。 template void BinaryTree:DeletAllValues( ) root-release( ); / if (root !=NULL) delete root; root=NULL;
7、/函数如何重用？ 判定二叉树是否为空：检查根指针是否为空。 template int BinaryTree:IsEmpty( ) /bool return root=NULL; /root=NULL逻辑表达式,18,返回左孩子地址 template BinaryTreeNode*BinaryTree:LeftChild(T /优化：GetChild( T &value, int nType ),19,小结,二叉树的结点类 二叉树的抽象类,20,二叉树的遍历,1、遍历的概念 2、二叉树的遍历 3、二叉树遍历的应用,21,1、遍历的基本概念,遍历：按某种搜索路径访问二叉树中的每个结点，而且每个结点
8、仅被访问一次。 访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据等。 遍历是各种数据结构最基本的操作，许多其它的操作可以在遍历基础上实现。 遍历对线性结构来说很容易解决，但是二叉树每个结点都可能有两棵子树，因而需要寻找一种规律，使得二叉树上的结点能排列成线性。,22,2、二叉树的遍历,二叉树由三部分组成：根结点、左子树、右子树； 若能依次遍历这三部分，就遍历完了整个二叉树。, L：遍历左子树 D：访问根结点 R：遍历右子树, 先左后右： DLR、LDR、LRD 先右后左： DRL、RDL、RLD,23,先(根)序遍历 中(根)序遍历 后(根)序遍历,先左后右的遍历算法,24
9、,先(根)序遍历,先序遍历DLR递归描述 基本项：若二叉树为空，结束 递归项： （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。,A,B,C,F,D,G,E,先序遍历序列（DLR）：A B D E G C F,25,/先序遍历以current为根的子树，递归函数 template void BinaryTree:PreOrder(BinTreeNode *current) /current=NULL，即到达叶子结点是递归终止条件 if(current!=NULL) coutdata; /访问根结点,用输出语句暂代 PreOrder(current-leftChild); /先
10、序遍历左子树 PreOrder(current-rightChild); /先序遍历右子树 ,26,中(根)序遍历,中序遍历递归描述 基本项：若二叉树为空，结束 递归项： （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。,中序遍历序列（LDR）：D B G E A F C,A,B,C,F,D,G,E,27,/中序遍历以current为根的子树，递归函数 template void BinaryTree:InOrder(BinTreeNode *current) if(current!=NULL) /current=NULL为递归终止条件 InOrder(current-LCh
11、ild); /中序遍历左子树 coutdata; /访问根结点，用输出语句暂代 InOrder(current-RChild); /中序遍历右子树 ,28,后(根)序遍历,后序遍历递归描述 基本项：若二叉树为空，结束 递归项： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。,后序遍历序列（LRD）：D G E B F C A,A,B,C,F,D,G,E,29,/后序遍历以current为根的子树，递归函数 template void BinaryTree:PostOrder(BinTreeNode *current) if(current!=NULL)/current=NU
12、LL是递归终止条件 PostOrder(current-leftChild); /后序遍历左子树 PostOrder(current-rightChild);/后序遍历右子树 coutdata; /访问根结点, 用输出语句代 ,30,3、二叉树遍历的应用,计算二叉树结点个数 计算二叉树的高度 判断两棵二叉树是否相等或等价,31,1）计算二叉树结点个数,利用二叉树的后序遍历规则，先遍历左子树和右子树，分别计算出左子树和右子树中的结点个数，然后把访问根结点加进去，就可以得到整个二叉树的结点个数。 template int BinaryTree:Size(const BinTreeNode *t)c
13、onst /计算以t为根的二叉树的结点个数 if(t=NULL) return 0; /递归结束条件为空树，结点个数为0 else return 1+Size(t-LChild)+Size(t-RChild); ,32,2）计算二叉树的高度,如果二叉树为空树，高度为-1；否则按后序遍历规则，先递归计算根结点的左子树和右子树的高度，再求出两者中较大者，并加1（要包括根结点，高度加1），就可以得到整个二叉树的高度。 template int BinaryTree:Depth(const BinTreeNode *t)const /计算以t为根的二叉树的高度 if (t=NULL) return -
14、1; /递归结束条件为空树，空树高度为-1 else return 1+Max(Depth(t-LChild)，Depth(t-RChild); 其中Max函数是求两者中的较大者： int Max(int x,int y) return(xy ? x:y);,33,仅知二叉树的先序序列“abcdefg” 不能唯一确定一棵二叉树，,由二叉树的先序和中序序列建树,如果同时已知二叉树的中序序列“cbdaegf”，则会如何？,二叉树的先序序列,二叉树的中序序列,左子树,左子树,右子树,右子树,根,根,34,a b c d e f g,c b d a e g f,例如:,a,a,b,b,c,c,d,d,
15、e,e,f,f,g,g,a,b,c,d,e,f,g,先序序列中序序列,35,例:试分别找出满足以下条件的所有二 叉树。,（1）二叉树的前序序列与中序序列相同,空树或缺左子树的单支树,（2）二叉树的中序序列与后序序列相同,空树或缺右子树的单支树,（3）二叉树的前序序列与后序序列相同,空树或只有根结点的二叉树,36,小结,二叉树的遍历 二叉树的遍历 二叉树遍历的应用,37,深度优先遍历 先根次序遍历 后根次序遍历 广度优先遍历,树的遍历,38,深度优先遍历,第一步：访问树的根结点； 第二步：“先根次序”遍历根的第一棵子树； 第三步：“先根次序”遍历根的第二棵子树、第三棵子树， , 直至遍历完整棵树。,先根次序遍历,39,后根次序遍历,第一步： “后根次序”遍历根的第一棵子树； 第二步：“后根次序”遍历根的第二棵子树、第三棵子树，, 直至遍历根的所有子树； 第三步：访问根结点。,40,广度优先遍历,按层次进行访问遍历： 第一步，访问层次为0 的根结点； 第二步，自左向右顺序访问层次为1的各个结点； 第三步，自左向右顺序访问层次为2的各个结点； 直至所有的结点都访问完。,41,树的遍历实例,先序遍历：,后序遍历：,层次遍历：,A,B,
