《树和二叉树习题答案.docx》由会员分享，可在线阅读，更多相关《树和二叉树习题答案.docx（7页珍藏版）》请在三一文库上搜索。
1、第六章练习1试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 态。解：(1)3个结点的树：(2)3个结点的二叉树:ABCABCABCABC个度为m的结点,点，个度为2结点，问该树中有多少个叶子结点？有：所以：3、对第 1 题所得的各种形态的二叉树，分别写出前序、中序和后序遍历的序列。解：(1) 前： ABC 中： BAC 后： BCA(2) 前： ABC 中： CBA 后： CBA(3) 前： ABC 中： BCA 后： CBA(4) 前： ABC 中： ABC 后： CBA(5) 前： ABC 中： ACB 后： CBA4、试以二叉链表作为存储结构，编写算法将二叉树中所有结点的左
2、、右子树相互交换。void Bitree_Revolute(BitreeIABCEDFGJHK管当前结点是否有左右孩子，都入队列这样当树为完全二叉树时，遍历时得到是 一个连续的不包含空指针的序列反之，那么序列中会含有空指针8、根据栈的存储结构写出二叉树的非递归形式的先序遍历算法。解：void PreOrder_Nonrecursive(Bitree T)先序遍历二叉树的非递归算法 _Ini tStack(S);Push(S,T); /根指针进栈while(!StackEmpty(S)while(Gettop(S,p)&&p)visit(p->data);push(S,p->lchild); / 向左走到尽头pop(S,p);if(!StackEmpty(S)pop(S,p);push(S,p->rchild); / 向右一步/while/PreOrder_Nonrecursive9、假设用于通信的电文仅由 8 个字母组成， 字母在电文中出现的频率分别为， 试为这 8 个字母设计哈夫曼编码。所以这 8 个字符的哈夫曼编码分别为：1010，00，10000，1001， 11，10001，01，1011。