第7章树和二叉树剖析.ppt

第七章 树和二叉树,本章主要内容,一、树的基本概念 二、二叉树 三、二叉树的遍历 四、线索二叉树 五、树和森林 六、哈夫曼树,6.1 树的基本概念,1.定义：是一种常非线性结构树是n（n≥0）个结点的有限集合若n=0，则称为空树；否则，有且仅有一个特定的结点被称为根，当n1时，其余结点被分成m（m0）个互不相交的子集T1，T2，.，Tm，每个子集又是一棵树递归定义的,树的几种形态,2.树的特点,（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点 （2）树中所有结点可以有零个或多个后继结点,3.树的相关概念,1) 结点 数据元素的内容及其指向其子树根的分支统称为结点 2) 结点的度 结点的分支数 3) 终端结点（叶子） 度为0的结点 4) 非终端结点 度不为0的结点 5) 结点的层次 树中根结点的层次为1，根结点子树的根为第2层，以此类推 6) 树的度 树中所有结点度的最大值 7) 树的深度 树中所有结点层次的最大值 8) 有序树、无序树 如果树中每棵子树从左向右的排列拥有一定的顺序，不得互换，则称为有序树，否则称为无序树9) 森林 是m（m≥0）棵互不相交的树的集合。

在树结构中，结点之间的关系又可以用家族关系描述，定义如下： 10)孩子、双亲 结点子树的根称为这个结点的孩子，而这个结点又被称为孩子的双亲 11)子孙 以某结点为根的子树中的所有结点都被称为是该结点的子孙 12)祖先 从根结点到该结点路径上的所有结点 13)兄弟 同一个双亲的孩子之间互为兄弟 14)堂兄弟 双亲在同一层的结点互为堂兄弟4.树的表示法,直观表示法 嵌套集合表示法 凹入表示法 //不清晰 广义表表示法,(1),(2),(3),(4),返回,6.2 二叉树,1.定义：叉树是n（n≥0）个结点的有限集合当n=0时，称为空二叉树；当n0时，有且仅有一个结点为二叉树的根，其余结点被分成两个互不相交的子集，一个称为左子集，另一个称为右子集，每个子集又是一个二叉树,递归定义的,2.二叉树的五种形态,例,3.二叉树的性质,在二叉树的第i层上最多有2i-1个结点（i≥1） 深度为K的二叉树最多有2K-1个结点（K≥1） 对于任意一棵二叉树BT，如果度为0的结点个数为n0，度为2的结点个数为n2，则n0=n2+1,二叉树的总度数＝n1+2n2 二叉树的节点数＝n0＋n1＋n2 二叉树的总度数＝二叉树的节点数－1 n1+2n2=n0＋n1＋n2-1 即： n0=n2+1,,具有n个结点的完全二叉树的深度为 log2n+1,证明：假设具有n个结点的完全二叉树的深度为K，则根据性质2可以得出： 2K-1-1n≤2K-1 将不等式两端加1得到： 2K-1≤n2K 取以2为底的对数，化简： K-1≤log2nK 得到：log2n =K-1。

整理：K= log2n+1,完全二叉树：n个结点的二叉树，若将它与一棵同深度的满二叉树中的所有结点按从上到下，从左到右的顺序分别进行编号，且该二叉树中的每个结点分别与满二叉树中编号为1~n的结点位置一一对应，则称这棵二叉树为完全二叉树,对于有n个结点的完全二叉树中的所有结点按从上到下，从左到右的顺序进行编号，则对任意一个结点i （1≤i≤n），有:,如果i=1，则结点i是这棵完全二叉树的根，没有双亲；否则其双亲结点的编号为 i/2 如果2in，则结点i没有左孩子；否则其左孩子结点的编号为2i 如果2i+1n，则结点i没有右孩子；否则其右孩子结点的编号为2i+1证明：采用数学归纳法，请大家自行阅读教材,4.二叉树的存储,顺序存储结构 链式存储结构,通常二叉树可以用下面两种方式存储：,下页介绍,(1) 顺序存储结构,适用完全二叉树，用一组连续的存储单元按照完全二叉树的每个结点编号的顺序存放结点内容 如下图所示：,下页给出C++实现,,#define maxsize 100 class QbTree { public: DataType elem[maxsize]; //根存储在下标为1的数组单元中 int n; //当前完全二叉树的结点个数 void CreateBTree(int m)； //构造一棵完全二叉树 int LeftCHild(int i)； //获取给定结点的左孩子 int RightChild(int i)； //获取给定结点的右孩子 int Parent(int i)； //获取给定结点的双亲 },,顺序存储特点：,二叉树是完全二叉树时，空间利用率高、寻找孩子和双亲比较容易。

若二叉树不是完全二叉树，需要将空缺的位置用特定的符号填补，造成空间利用率的下降,引出链式存储,(2)链式存储结构,注：Lchild和Rchild是分别指向该结点左孩子和右孩子的指针,下页C++实现,typedef int DataType Class BinTreeNode { public: DataType data; BinTreeNode * leftChild; BinTreeNode * rightChild; BinTreeNode( ){leftChild=NULL;rightChild=NULL; } //构造函数，构造一个空结点 };,二叉树链接存储的节点定义,,class BinaryTree { public: BinTreeNode *root; BinaryTree(){root=NULL;} ～BinaryTree(){DeleteTree();} bool InsertLeft(BinTreeNode * current,DataType x); //将元素x插入作为current所指结点的左孩子 bool InsertRight(BinTreeNode * current,DataType x);//将元素x插入作为current所指结点的右孩子 void Preorder(BinTreeNode *current); //先序遍历 void InOrder(BinTreeNode *current); //中序遍历 void Postorder(BinTreeNode *current); //后序遍历 BinTreeNode * Find(BinTreeNode *current,DataType x);//搜值为x结点 void Destroy(BinTreeNode * current); //删除指定子树 void DeleteTree(){Destroy(root);root=NULL;} //删除整棵树 bool IsEmpty( ){ return root == NULL } //判树空否 BinTreeNode *CreatBinTree() ; //创建一棵二叉树 };,返回,6.3 二叉树的遍历,定义：按照一定规则访问二叉树的所有节点一次,先序遍历TLR、 中序遍历LTR和 后序遍历 LRT 层次遍历,下页分述,T,L,R,,,(1)先序遍历TLR,若二叉树为空，则结束遍历操作；否则 访问根结点； 先序遍历根的左子树； 先序遍历根的右子树,递归算法，思考它所对应的非递归算法,先看遍历的结果,,下页C++实现,void BinaryTree :: PreOrder(BinTreeNode * current) { if(current != NULL){ cout data; //输出此结点内容 Preorder(current-leftChild); //遍历左子树 Preorder(current-rightChild); //遍历右子树 } } 思考：1. visite 函数能做什么？ 2.visite (t-data)这条语句执行次数？ 3.如何计算结点个数、叶子个数？ 4.改变visite (t-data)这条语句的位置会产生 什么效果?,思考如何得到中序和后序遍历的算法？,（2）中序遍历和后序遍历算法,中序遍历 void BinaryTree :: InOrder(BinTreeNode *current) { if(current != NULL){ InOrder(current-leftChild); cout data; InOrder(current-rightChild); } },（2）中序遍历和后序遍历算法,后序遍历 void BinaryTree :: PostOrder(BinTreeNode * current) { if(current != NULL){ PostOrder(current-leftChild); PostOrder(current-rightChild); cout data; } },三种访问序列的结果,（3）三种遍历的非递归算法,树的定义是递归的，容易实现遍历的递归算法,思考遍历算法的执行过程,,,找出它们所对应的非递归算法,？,1) 先序遍历的非递归算法,void BinaryTree :: PreOrder(BinTreeNode *p= root) //带默认参数值root，注意：此函数没有在类中声明 { SeqStack S;//见第5章顺序栈，不同的是栈内存储的元素是指针 while(p ||!S.Empty_Stack( )) if(p){ cout data leftChild; } else { S.Pop_Stack(p); p = p-rightChild; } //左子树为空，进右子树 },2) 中序遍历的非递归算法,将上述算法稍微改动就能写出中序遍历的非递归算法,请读者思考两个算法的差异.,void BinaryTree:: InOrder(BinTreeNode * p= root) //带默认参数值root，注意：此函数没有在类中声明 { SeqStack S; while(p||!S.Empty_Stack( )) if(p){ S.Push _Stack(p); //预留p指针在栈中 p = p-leftChild; } else { S.Pop_Stack(p); cout data rightChild; } //左子树为空，进右子树 },3) 后序遍历的非递归算法,先思考如下问题: *在先序中序遍历中,每个结点(结点地址)进栈几次?出栈几次? *在后序遍历中,每个结点(结点地址)进栈几次?出栈几次? *为什么后序遍历特殊呢? *如何区别结点的第1次和第2次进(出)栈?,3) 后序遍历的非递归算法,void BinaryTree :: PostOrder(BinTreeNode * p= root) { SeqStack s1;//s1栈存放结点指针 SeqStack s2;//s2栈存放标志flag int flag; while(p ||!s1.Empty_Stack( )) { if(p){ flag=0; s1.Push_Stack(p);//当前p指针第一次进栈 s2.Push_Stack(flag);//标志flag进栈 p = p-leftChild; } else {,3) 后序遍历的非递归算法,s1.Pop_Stack(p); //p指针出栈 s2.Pop_Stack(flag); //标志flag出栈 if(flag==0) { flag=1; s1.Push_Stack(p); //当前p指针第二次进栈 s2.Push_Stack(flag);//标志flag进栈 p = p-rightChild; } //左子树为空，进右子树 else { //flag为1说明是第二次出栈，访问结点 cout data endl; p=NULL; //请读者思考：为什么要把p赋空？ } } } },（4）层次遍历二叉树,定义：按照树深度的次序从左到右依次访问二叉树的所有节点,请同学们动手写出它C++算法,(5) 二叉树遍历算法的应用,二叉树是递归定义，。