第6章-树和森林-----数据结构(北师大)C++版.ppt

《第6章-树和森林-----数据结构(北师大)C++版.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、树和二叉树二叉树遍历线索二叉树二叉搜索树二叉树的计数堆树与森林霍夫曼树及其应用第六章树和森林一、树和二叉树树tree的定义(1)无结点的树空树(2)非空树仅有一个根结点其余结点分为若干互不相交的子树ABCDEFGHIJKLM········································根3度·············叶0度2个3度点A,D2个2度点B,E2个1度点C,H7个叶F,G,I,J,K,L,MABCDEFGHIJKLM····························

2、·················第一层······························第二层···············第三层····································第四层树的深度为4ABCDEFGHIJ2.二叉树每个结点至多有两棵子树,1度或2度深度为k，结点至多2k-1个第i层结点至多2i-1个设有n2个2度点则有n2+1个叶片ABCDEFGHIJABCDEFGHIJ满二叉树KLMNO深度为k,结点数2k-1,每层结点数都最大满二叉树满二叉树去掉最

3、下层最右边若干结点满二叉树也是完全二叉树完全二叉树ABCDEFGHIJKLMNOABCDEFGHIJ完全二叉树KLMn个结点,深度k=[log2n]+1n个结点,深度为k:2k-1-1＜n≤2k-12k-1≤n＜2kk-1≤log2n＜kk-1=[log2n]k=[log2n]+11个结点深度为12-3个结点深度为24-7个结点深度为38-15个结点深度为412345678910完全二叉树111213结点i的左子结点是2i右子结点是2i+1结点i的父结点是[i/2]二叉树的存储完全二叉树的顺序存储#

4、defineMaxTreeSize100typedefTElemTypeSqBiTree[MaxTreeSize];SqBiTreebt;1234567891011120123456789完全二叉树101112结点i的左子结点是2i+1右子结点是2i+2结点i的父结点是[(i-1)/2]123456789101112二叉树的链式存储树结点左指针数据右指针lchilddatarchildAB^C^D^E^F^^G^^H^ABCDEFGH二叉树结点类的定义#ifndefTREENODE_CLASS#de

5、fineTREENODE_CLASS#ifndefNULLconstintNULL=0;#endif//NULLtemplateclassBinSTree;templateclassTreeNode{protected:TreeNode*left，*right;public:Tdata;TreeNode(constT&item,TreeNode*lptr=NULL,TreeNode*rptr=NULL);virtual~TreeNode(void);

6、TreeNode*Left(void)const;TreeNode*Right(void)const;voidGetLeft(TreeNode*lptr);voidGetRight(TreeNode*rptr);friendclassBinSTree;};//thepointerNULLassignsanemptytreetemplateTreeNode::TreeNode(constT&item,TreeNode*lptr,TreeNode

7、*rptr):data(item),left(lptr),right(rptr){}//methodLeftallowstheuser//toreferencetheleftchildtemplateTreeNode*TreeNode::Left(void)const{//returntheprivatemembervalueleftreturnleft;}//methodLeftallowstheuser//toreferencetherightchildte

8、mplateTreeNode*TreeNode::Right(void)const{//returntheprivatemembervaluerightreturnright;}//doesnothing.//existssonodesderivedfromitwillbe//destroyedproperlybydelete.//usedinChapter13forAVLtreestemplateTreeNode: