树和二叉树习题答案.doc

《树和二叉树习题答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章练习1、试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。态。解：（1）3个结点的树：（2）3个结点的二叉树：2、已知一棵度为m的树中有个度为1的结点，个度为2结点，…，个度为m的结点，问该树中有多少个叶子结点？解：由树的特征可知，除顶点外每个结点对应于一条边，总边数等于各顶点度数之和，所以有：所以：3、对第1题所得的各种形态的二叉树，分别写出前序、中序和后序遍历的序列。解：(1)前：ABC中：BAC后：BCA(2)前：ABC中：CBA后：CBA(3)前：ABC中：BCA后：CBA

2、(4)前：ABC中：ABC后：CBA(5)前：ABC中：ACB后：CBA4、试以二叉链表作为存储结构，编写算法将二叉树中所有结点的左、右子树相互交换。voidBitree_Revolute(BitreeT)//交换所有结点的左右子树{T->lchild<->T->rchild;//交换左右子树if(T->lchild)Bitree_Revolute(T->lchild);if(T->rchild)Bitree_Revolute(T->rchild);//左右子树再分别交换各自的左右子树}//Bit

3、ree_Revolute5、画出和下面树对应的二叉树：6、画出和下面二叉树对应的森林：7、写出判断给定的二叉树是否是完全二叉树的算法。intIsFull_Bitree(BitreeT)//判断二叉树是否完全二叉树,是则返回1,否则返回0{InitQueue(Q);flag=0;EnQueue(Q,T);//建立工作队列while(!QueueEmpty(Q)){DeQueue(Q,p);if(!p)flag=1;elseif(flag)return0;else{EnQueue(Q,p->lchil

4、d);EnQueue(Q,p->rchild);//不管孩子是否为空,都入队列}}//whilereturn1;}//IsFull_Bitree分析:该问题可以通过层序遍历的方法来解决.不管当前结点是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空指针的序列.反之,则序列中会含有空指针.8、根据栈的存储结构写出二叉树的非递归形式的先序遍历算法。解：voidPreOrder_Nonrecursive(BitreeT)//先序遍历二叉树的非递归算法{InitStack(S

5、);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个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.0

6、6，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。所以这8个字符的哈夫曼编码分别为：1010，00，10000，1001，11，10001，01，1011。