离散数学 树 知识点总结.docx

该【离散数学 树 知识点总结 】是由【国霞穿越】上传分享，文档一共【6】页，该文档可以免费在线阅读，需要了解更多关于【离散数学 树 知识点总结 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。1第六章树一、掌握基本概念树的子树是互不相交的,树可以为空(空树)非空的树中,只有一个结点是没有前趋的,那就是根。非空树只有一个树根,是一对多的关系。叶子结点、结点的度、树的度、结点的层次、树的深度、树的四种表示方法二、二叉树的定义、特点、五种基本形态二叉树是有序树,左右子树不能互相颠倒二叉树中结点的最人度为2,但不一定都是2。三、二叉树的性质要掌握性质1:二叉树的第1层上至多有21-1(il)个结点。性质2:深度为k的二叉树中至多2k-1个结点。性质3:对任何一棵二叉树T,如果其终端结点数为nO,度为2的结点数为n2,则n0=n2+1。证明:1)结点总数n=n0+nl+ii2(ill是度为1的结点数)2)进入分支总数m(每个结点唯一分支进入)n=m+l3)m个分支是由非叶子结点射出m=nl+2n2性质4:具有n个结点的完全二叉树的深度k为[log2n]+l四、满二叉树和完全二叉树的区别是什么?满二叉树一定是完全二叉树,但是完全二叉树不一定是满二叉树。深度为k的二叉树,最少有k个结点,最多有2k-1深度为k的完全二叉树,最少有2k-l-l+l个结点,最多有2k-l五、二叉树的存储结构(可以通过下标找结点的左右孩子)1?顺序存储结构适用于满二叉树和完全二叉树。(其缺点是必须把其他二叉树补成完全二叉树,从上到卞,从左到右依次存储在顺序存储空间里,会造成空间浪费)二叉链表存储结构(其优点是找左孩子和右孩子方便,但缺点是找父节点麻烦)lcliildDatarcliild(重点)2三叉链表存储结构不仅找其左、右孩子很方便,而且找其双亲也方便六、遍历的概念是什么?七、二叉树的遍历有三种:前序(先序、先根)遍历、中序(中序、中根)遍历、后序(后序、后根)遍历给出一棵二叉树,要会二叉树的三种遍历给出两种遍历(必须有中序遍历),要求会画该二叉树。八、了解引入线索(中序、先序、后序)二叉树的原因是什么?九、会在二叉树上画先序线索化、中序线索化、后序线索化。在线索二叉树的格式中,可以找到任意结点的直接后继。(错)在线索二叉树中,如呆某结点的右孩子为空,那么可以找到该结点的直接后继。(对)在线索二叉树中,如呆某结点的左孩子为空,那么可以找到该结点的直接前趋。(对)十、,转换后的二叉树根的右子树为空。十一、森林的遍历(只有先序遍历和后序遍历)先序遍历一棵树,相当于先序遍历该树所对应的二叉树。后序遍历一棵树,相当于中序遍历该树所对应的二叉树。十二、赫夫曼树(又称最优二叉树或哈夫曼树)、赫夫曼树编码赫夫曼树中,权越人的叶子离根越近,其形态不唯一,但是WPL带权路径长度一定是最小。—定要会构造哈夫曼树,在构造好的哈夫曼树上会构造哈夫曼编码。(认真看题目要求)第6章算法设计题已知二叉树中的结点类型用BiTNode表示,被定义描述为:TypedefstmctBiTNode{TElemTvpedata;stnictBiTNode*LChild,*RChild;3}BiTNode,*BiTree;其中data为结点值域,LCluld和RChild分别为指向左、右孩子结点的指针域,编写出求一棵二叉树高度的算法。IntBTreeHeight(BiTreeBT){if(BT=NULL)return0;else{h1=BTieeHeight(BT->LCluld);li2=BTreeHeight(BT->RChild);if(hl>112)retum(hl+l);elsereturn(h2+l);}}已知二叉树中的结点类型用BiTNode表示,被定义描述为:TypedefstmctBiTNode{TElemTvpedata;stnictBiTNode*LChild,*Rchild;}BiTNode,*BiTree:BiTreeT:其中data为结点值域,LChild和RChild分别为指向左、右孩子结点的指针域,编写算法,求出二叉树中2度结点个数。iiitdegree2nodenum(BiTreeT){】f(T){if(T->lcluld!=NULL&&T->cluld!=NULL)count++;leafiiodenum(l->lcluld);leafiiodenum(l->icluld);}returncount;4}已知二叉树中的结点类型用BiTNode表示,被定义描述为:TypedefstnictBiTNode{TElemTvpedata;stnictBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT;其中data为结点值域,LCluld和RChild分别为指向左、右孩子结点的指针域,写一算法,求出二叉树中的叶子结点个数。voidBTreeLeaf(BiTreeBT){if(ET){if(BT->LChild==NULL&&BT->RChild==NULL)count++;BTreeLeaf(BT->LCluld);//访问左子树BTreeLeaf(BT->RCluld);//访问右子树}}或下面算法均可编写递归算法,计算二叉树中叶子结点的数目。mtLeafCount_BiTree(BitreeT)//求二叉树中叶子结点的数目{if(!T)leturn0;//空树没有叶子elseif(!T->lchild&&!T->rchild)return1;〃叶子结点elseretiiniLeaf_Count(T->lchild)+Leaf_Count(T->rchild);//左子树的叶子数加上右子树的叶子数}//LeafCount_BiTree6PPT±的三种遍历递归算法和课本上P131先序递归创建二叉链表。给定一棵二叉树,其根指针为root。试写出求二叉树结点数目的算法(递归算法或非递归算法)。【提示】采用递归算法实现。mtcount(BiTreet){if(t==NULL)return0;elsereturncount(t->lchild)+count(t->rcluld)+1;}以二叉链表为存储结构,写一算法交换各结点的左右子树。【分析】依题意,设t为一棵用二叉链表存储的二叉树,则交换各结点的左右子树的运算基于后序遍历实现:交换左子树上各结点的左右子树;交换右子树上各结点的左右子树:再交换根结点的左右子树。【算法】voidExchg(BiTiee*t){BinNode*p;P=(*t)->lchild;(*t)->lchild=(*t)->rcluld;(*t)->icliild=p;Exchg(&((*t)->lchild));Exchg(&((*t)->rchild));}}已知一棵二叉树采用二叉链表结构存储,每个结点的值为整数类型。要求:给出相应的语言描述,在此基础上设计计算二叉树中所有结点值之和的算法。6tvpedefstmctlink{intdata;stnictlink*Ichild;stmctluik*rchild;}bitnode、*bitree;voidsum(bitree&s)