数据结构习题

14．分别描述满足下面条件的二叉树的特征： （1）先序序列和中序序列相同。 （2）先序序列和后序序列相反。

15．证明：由二叉树的先序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①先序：ABCDEFGHI ②先序：ABCDEFGHIJ 中序：ADECFBGIH 中序：BDECAGIJHF

16．证明：由二叉树的后序序列和中序序列能唯一确定一棵二叉树，并分别由下面的两个序列构造出相应的二叉树：

①后序：DCFEBIHGA ②后序：DECBGIHFA 中序：DCBFEAGHI 中序：DCEBAFHGI

17．已知一棵二叉树的先序、中序和后序序列如下，其中各有一部分未给出其值，请构造出该二叉树。

先序：A CDEF_H_J 中序：C_EDA_GFI_ 后序：C_ _BHGJI_ _

18．证明：任意一棵非空的二叉树的先序序列的最后一个结点一定是叶子结点。 19．用反例证明：由二叉树的先序序列和后序序列不能唯一确定一棵二叉树。 20．设计算法以输出二叉树中先序序列的前k（k>0）个结点的值。

21．设计算法按中序次序依次输出各结点的值及其对应的序号。例如，下图中的二叉树的输出结果是(C,1) (B,2) (E,3) (D,4) (F,5) (A,6) (H,7) (J,8) (I,9) (G,10)。

33

22．设计算法以输出每个结点到根结点之间的路径上的所有结点的值。

23．设计算法将一棵以二叉链表形式存储的二叉树转换为顺序存储形式存储到数组A[n]中，并将其中没有存放结点值的数组元素设置为NULL。

24．设计算法将一棵以顺序存储方式存储在数组A中的二叉树转换为二叉链表形式。

25．写出如下图树的先根遍历序列和后根遍历序列并将此树转化为二叉树：

26.已知某系统在通讯联络中只可能出现6种字符{a,b,c,d,e,f}，其概率分别为0.10，0.22，0.13，0.14，0.15，0.26，试画出赫夫曼树并设计赫夫曼编码。

27.假定用于通信的电文仅由8个字母a，b，c，d，e，d，f，g，h组成，各个字母在电文中出现的频率分别为5，23，3，6，10，11，36，4。试为这8个字母设计不等长Huffman编码，并输出该电文的总码数。 （1）Huffman树为：（2）Huffman编码为（3）电文总长度：

28．对给定的权值｛ 2 ， 3 ， 4 ， 7 ， 8 ， 9 ｝，构造出相应的赫夫曼树和赫夫曼编码，并求出带权路径的长度 WPL 。

29．将下图中的二叉树转换为对应的森林。

34

30．已知二叉树的存储结构为二叉链表，阅读下面算法。 typedef struct node { DateType data； Struct node * next； }ListNode；

typedef ListNode * LinkList ； LinkList Leafhead=NULL； void Inorder (BinTree T) { LinkList s；

if(T)

{

Inorder(T－>lchild)；

if ((!T－>lchild)&&(!T－>rchild))

{

s=(ListNode*)malloc(sizeof(ListNode))； s－>data=T－>data； s－>next=Leafhead； Leafhead=s； }

Inorder(T－>rchild)；

} } 对于如下所示的二叉树

（1）画出执行上述算法后所建立的结构；

35

（2）说明该算法的功能。

31．分别画出下图所示的森林的双亲表示形式、孩子链表表示形式和二叉链表表示形式。

32． 将下图中的森林转换为对应的二叉树。

五、算法设计题

1.先序遍历二叉树的非递归算法

void PreOrder_Nonrecursive(Bitree T) { InitStack(S);

Push(S, ); //根指针进栈 while(!StackEmpty(S))

{ while(Gettop(S, )&&p)

{ visit(p->data); push(S, ); } //向左走到尽头 pop(S,p);

if(!StackEmpty(S))

{ pop(S, ); push(S, ); //向右一步 } }//while

}//PreOrder_Nonrecursive

2.补充下列中序遍历二叉树的非递归算法 inorder(BiTree T)

{ SqStack S; BiTree P=T; InitStack(S);

while( )

{

36