2013数据结构作业3-树与二叉树-参考答案

作业3. 树

非编程作业：

1． 请分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。 参考答案：

具有3个结点的树：

具有3个结点的二叉树：

2． 已知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是

ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。

参考答案：

E

A F 层次：E A F B H D G I C K J B H 后序---C D B A G J K I H F E

D C G I K J 3． 将下图所示的森林转换成一棵二叉树。

AGKBCDHIJLEF

参考答案：

转换成的二叉树为： A

B

C

D G H I K L J E F 4． 将下图所示的二叉树还原成树或森林。

ABCDLFEGHMKNJI

参考答案：

转换为森林：

A E

G

B C D F H I J L M N K 5． 假设用于通信的电文由7个字母组成{A,B,C,D,E,F,G}，字母在电文中出

现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度WPL。 参考答案：

哈夫曼树为：

0.18 1

0.39

G 0.61

0.21 0.29

0.32

E 0.17

A 0.09

0.09

B 0.12

WPL=4*(0.03+0.06)+3*(0.12+0.17+0.09)+2*(0.32+0.21)=2.56 A:101 B:001 C:100 D:0001 E:11 F:0000 G:01

编程作业：

二叉树采用二叉链表存储，试设计算法实现：

1．CreateBT(BiTree &T)：从键盘输入二叉树的先序遍历序列字符串（以”#”代表空结点），建立其二叉链表；

如输入：AB#D##CE#F### 则建立如下图所示二叉树的二叉链表 2．ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子交换；

3．CountLeaf(BiTree T, TElemType x, int &count): 统计以值为x的结点为根的子树中叶子结点的数目；

4．DispBiTree(BiTree T, int level) : 按树状打印二叉树。

A 打印得到：#C

###F ##E C B

A ##D

E D #B

F

提示：对于根为T，层次为level的子树：

① 打印其下一层(level+1层)右子树； ② 打印根结点；

③ 打印其下一层(level+1层)左子树； *结点左边的’#’个数为其层次数*

参考答案：

#include #include

typedef struct BiTNode{ char data;

struct BiTNode *lchild,*rchild; }BiTNode, *BiTree;

//输入先序序列，创建二叉树的二叉链表 void CreateBT(BiTree &T) { char ch;

scanf(\

if (ch == '#') T = NULL; else

{ T = (BiTNode *)malloc(sizeof(BiTNode)); T->data = ch; CreateBT(T->lchild); CreateBT(T->rchild);

} }

//交换二叉树中结点的左右孩子 void ExchangeBT(BiTree T) {

BiTree temp; if(T)

{ temp=T->lchild; T->lchild=T->rchild; ExchangeBT(T->lchild); ExchangeBT(T->rchild);

} }

//先序遍历二叉树

void PreOrderTraverse(BiTree T) { if(T)

{ printf(\ PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } }

//查找值为x的结点

BiTree SearchTree(BiTree T,char X) {

BiTree bt;

if(T) { if(T->data==X) return T; bt=SearchTree(T->lchild,X); if(bt==NULL) bt=SearchTree(T->rchild,X); return bt;

}

return NULL; }

T->rchild=temp;

//统计以T为根的子树中叶子结点数 int LeafCount1 (BiTree T) {

static int count;

if ( T )

{ if ((T->lchild==NULL)&& (T->rchild==NULL)) count++; else

{ count=LeafCount1( T->lchild); count=LeafCount1( T->rchild); } }

return count; }

void LeafCount2 (BiTree T, int &count) {

if ( T )

{ if ((T->lchild==NULL)&& (T->rchild==NULL)) LeafCount2( T->lchild, count); LeafCount2( T->rchild, count); } }

//按树状打印输出二叉树的元素,level表示结点的层次void DispBiTree(BiTree T,int level) {

int i; if(T)

{ DispBiTree(T->rchild, level + 1); for(i = 0; i < level;i++) printf(\ printf(\ DispBiTree(T->lchild, level + 1);

} }

void main() { BiTree T,SubT; char Subch;

int countl=0;

printf(\输入先序序列建立二叉树：\\n\ CreateBT(T);

count++; printf(\二叉树的先序序列：\ PreOrderTraverse(T); printf(\二叉树为：\\n\ DispBiTree(T,0);

printf(\交换结点的左右孩子\\n\ ExchangeBT(T);

printf(\此时二叉树为：\\n\ DispBiTree(T,0);

printf(\输入要统计叶子结点个数的子树的根：\ fflush(stdin);

scanf(\

SubT=SearchTree(T,Subch);

//countl=LeafCount1(SubT); LeafCount2(SubT, countl);

printf(\叶子结点数为：%d\\n\}

printf(\二叉树的先序序列：\ PreOrderTraverse(T); printf(\二叉树为：\\n\ DispBiTree(T,0);

printf(\交换结点的左右孩子\\n\ ExchangeBT(T);

printf(\此时二叉树为：\\n\ DispBiTree(T,0);

printf(\输入要统计叶子结点个数的子树的根：\ fflush(stdin);

scanf(\

SubT=SearchTree(T,Subch);

//countl=LeafCount1(SubT); LeafCount2(SubT, countl);

printf(\叶子结点数为：%d\\n\}

本文来源：https://www.bwwdw.com/article/wdja.html