作业3树参考答案

数据结构作业3树 参考答案

作业3. 树

非编程作业参考答案：

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

具有3个结点的二叉树：

A B C B C A A A B C A B C B C 2．已E 知二叉树的先序遍历序列是EABDCFHGIKJ，中序遍历序列是ABCDEFGHIJK，请构造二叉树，并写出其层次遍历序列和后序遍历序列。

A 构造的二叉树为：

F

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

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

D G I

B H

K C

J 3．将图1所示的森林转换成一棵二叉树。

AGKBCDHIJLEF

图1

数据结构作业3树 参考答案 转换成的二叉树为： A G B C H K D I L E J F 4．将如图2所示的二叉树还原成树或森林。 ABCDLFEGHLKLJI

图2

转换为森林：

A E

G B C D F H I J

L L L

K

5．假设用于通信的电文由7个字母组成，字母在电文中出现的频率分别为0.17、0.09、0.12、0.06、0.32、0.03、0.21。试为这7个字母设计哈夫曼编码，并计算其带权路径长度。

数据结构作业3树 参考答案

哈夫曼树为：

0.39

G 1

0.61

0.18 0.21 0.29

0.32

E 0.17

A 0.09

0.09

B 0.06

D

0.12

0.03

F

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．DepthBT(BiTree T, int &depth)：设计算法求二叉树的高。 3．ExchangeBT(BiTree T): 设计递归算法实现二叉树中所有结点的左右孩子交换；

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

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

A 打印得到：#C

###F ##E C B

A ##D

E D #B

F

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

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

数据结构作业3树 参考答案

参考答案：

#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; T->rchild=temp; ExchangeBT(T->lchild); ExchangeBT(T->rchild); } }

//先序遍历二叉树

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

数据结构作业3树 参考答案

}

//查找值为x的结点

BiTree SearchBT(BiTree T,char X) { BiTree bt; if(T) { if(T->data==X) return T; bt=SearchBT(T->lchild,X); if(bt==NULL) bt=SearchBT(T->rchild,X); return bt; } return NULL; }

//求二叉树高度

void DepthBT(BiTree T, int &depth) { int depthLeft,depthRight; if(!T) depth=0; else

{ DepthBT (T->lchild,depthLeft); DepthBT (T->rchild,depthRight);

depth=1+(depthLeft>depthRight?depthLeft : depthRight); } }

//统计以T为根的子树中叶子结点数

void LeafCount(BiTree T, int &count) { if ( T )

{ if ((T->lchild==NULL)&& (T->rchild==NULL)) count++; LeafCount( T->lchild, count); LeafCount( 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++)

数据结构作业3树 参考答案

printf(\ printf(\ DispBiTree(T->lchild, level + 1); } }

void main()

{ BiTree T,SubT; char Subch; int count=0,depth;

printf(\输入先序序列建立二叉树：\\n\ CreateBT(T); printf(\二叉树的先序序列：\ PreOrderTraverse(T); printf(\二叉树为：\\n\ DispBiTree(T,0); printf(\二叉树深度为：\ DepthBT(T,depth); printf(\ printf(\交换结点的左右孩子\ ExchangeBT(T); printf(\此时二叉树为：\\n\ DispBiTree(T,0); printf(\输入要统计叶子结点个数的子树的根：\ fflush(stdin); scanf(\ SubT=SearchBT(T,Subch); LeafCount(SubT, count); printf(\叶子结点数为：%d\\n\}

数据结构作业3树 参考答案

printf(\ printf(\ DispBiTree(T->lchild, level + 1); } }

void main()

{ BiTree T,SubT; char Subch; int count=0,depth;

printf(\输入先序序列建立二叉树：\\n\ CreateBT(T); printf(\二叉树的先序序列：\ PreOrderTraverse(T); printf(\二叉树为：\\n\ DispBiTree(T,0); printf(\二叉树深度为：\ DepthBT(T,depth); printf(\ printf(\交换结点的左右孩子\ ExchangeBT(T); printf(\此时二叉树为：\\n\ DispBiTree(T,0); printf(\输入要统计叶子结点个数的子树的根：\ fflush(stdin); scanf(\ SubT=SearchBT(T,Subch); LeafCount(SubT, count); printf(\叶子结点数为：%d\\n\}

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