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

《离散数学 树 知识点总结.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第六章树一、掌握基本概念树的子树是互不相交的，树可以为空（空树）非空的树中，只有一个结点是没有前趋的，那就是根。非空树只有一个树根，是一对多的关系。叶子结点、结点的度、树的度、结点的层次、树的深度、树的四种表示方法二、二叉树的定义、特点、五种基本形态二叉树是有序树，左右子树不能互相颠倒二叉树中结点的最大度为2，但不一定都是2。三、二叉树的性质要掌握性质1：二叉树的第i层上至多有2i-1（i1）个结点。性质2：深度为k的二叉树中至多2k-1个结点。性质3：对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0＝n2＋1。证明：1)

2、结点总数n=n0+n1+n2(n1是度为1的结点数)2)进入分支总数m(每个结点唯一分支进入)n=m+13)m个分支是由非叶子结点射出m=n1+2n2性质4：具有n个结点的完全二叉树的深度k为[log2n]+1四、满二叉树和完全二叉树的区别是什么？满二叉树一定是完全二叉树，但是完全二叉树不一定是满二叉树。深度为k的二叉树，最少有k个结点，最多有2k-1深度为k的完全二叉树，最少有2k-1-1+1个结点,最多有2k-1五、二叉树的存储结构（可以通过下标找结点的左右孩子）1.顺序存储结构适用于满二叉树和完全二叉树。（其缺点是必须把其他二叉树补成完全二

3、叉树，从上到下，从左到右依次存储在顺序存储空间里，会造成空间浪费）2.二叉链表存储结构（其优点是找左孩子和右孩子方便，但缺点是找父节点麻烦）lchildDatarchild（重点）3.三叉链表存储结构不仅找其左、右孩子很方便，而且找其双亲也方便六、遍历的概念是什么？七、二叉树的遍历有三种：前序（先序、先根）遍历、中序（中序、中根）遍历、后序（后序、后根）遍历1.给出一棵二叉树，要会二叉树的三种遍历2.给出两种遍历（必须有中序遍历），要求会画该二叉树。八、了解引入线索（中序、先序、后序）二叉树的原因是什么？九、会在二叉树上画先序线索化、中序线索化、

4、后序线索化。在线索二叉树的格式中，可以找到任意结点的直接后继。（错）在线索二叉树中，如果某结点的右孩子为空，那么可以找到该结点的直接后继。（对）在线索二叉树中，如果某结点的左孩子为空，那么可以找到该结点的直接前趋。（对）十、树.森林和二叉树的相互转换树转换成二叉树后，转换后的二叉树根的右子树为空。十一、森林的遍历（只有先序遍历和后序遍历）先序遍历一棵树，相当于先序遍历该树所对应的二叉树。后序遍历一棵树，相当于中序遍历该树所对应的二叉树。十二、赫夫曼树（又称最优二叉树或哈夫曼树）、赫夫曼树编码1.赫夫曼树中，权越大的叶子离根越近，其形态不唯一，但是

5、WPL带权路径长度一定是最小。2.一定要会构造哈夫曼树，在构造好的哈夫曼树上会构造哈夫曼编码。（认真看题目要求）第6章算法设计题1．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写出求一棵二叉树高度的算法。IntBTreeHeight(BiTreeBT){if(BT==NULL)return

6、0;else{h1=BTreeHeight(BT->LChild);h2=BTreeHeight(BT->RChild);if(h1>h2)return(h1+1);elsereturn(h2+1);}}2．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*Rchild；}BiTNode,*BiTree；BiTreeT；其中data为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，编写算法，求出二叉树中2

7、度结点个数。intdegree2nodenum(BiTreeT){if(T){if(T->lchild！=NULL&&T->child！=NULL)count++;　　　　　　　leafnodenum(l->lchild);leafnodenum(l->rchild);　　　}returncount;}3．已知二叉树中的结点类型用BiTNode表示，被定义描述为：TypedefstructBiTNode{TElemTypedata;structBiTNode*LChild,*RChild;}BiTNode,*BiTree;BiTreeT；其中da

8、ta为结点值域，LChild和RChild分别为指向左、右孩子结点的指针域，写一算法，求出二叉树中的叶子结点个数。voidBTreeLe