软件技术基础实验指导书(20101009)

实验二 二叉树的建立和遍历

一、 实验目的

1．掌握二叉树的建立算法

2．掌握二叉树的前序、中序和后序遍历算法。

二、 实验环境

操作系统和C语言系统

三、 预习要求

复习二叉树的生成及遍历算法，编写完整的程序。

四、 实验内容

要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体实现要求：分别利用前序遍历、中序遍历、后序遍历所建二叉树。

五、 参考算法

二叉树的建立算法思路：主要利用二叉树的性质：在编号的完全二叉树中，编号为i的结点如果存在左孩子，则其编号为2i；若其存在右孩子，则其编号为2i+1；若存在父结点，则其编号为i/2取整。对任意二叉树，先按满二叉树对其进行编号，算法中使用一个辅助向量s来存放指向树结点的指针。如s[i]中存放编号为i的结点的指针，即为该结点的地址。当结点编号i=1时，所产生的结点为根结点，同时将指向该结点的指针存入s[1]。当结点编号i>1时，产生一个新的结点后，也要将指向该结点的指针存入s[i]，由上述性质可知：j=i/2为它的双亲结点编号。如果i为偶数，则它是双亲结点的左孩子，即让s[j]->lch=s[i]；若i为奇数，则它是双亲结点的右孩子，即让s[j]->rch=s[i]。这样就将新输入的结点逐一与其双亲结点相连，生成二叉树。

二叉树的遍历算法可以使用递归算法实现，也可采用非递归算法实现，可参考教材上算法实现。

六、 思考题

请思考其它的二叉树建立算法。

七、 实验报告要求

具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。

5

实验三 二叉排序树的建立和查找

一、 实验目的

1．掌握二叉排序树的建立算法 2．掌握二叉排序树查找算法。

二、 实验环境

操作系统和C语言系统

三、 预习要求

复习二叉排序树的生成及查找算法，编写完整的程序。

四、 实验内容

实现二叉排序树上的查找算法。具体实现要求：用二叉链表做存储结构，输入键值序列，建立一棵二叉排序树并在二叉排序树上实现查找算法。

五、 参考算法

#include #include typedef int InfoType;

typedef int KeyType; typedef struct node {

KeyType key;

/*关键字项*/

InfoType otherinfo; /*其它数据域，InfoType视应用情况而定 下面不处理它*/ struct node *lchild,*rchild;/*左右孩子指针*/

/*BSTree是二叉排序树的类型*/

/*假定关键字类型为整数*/ /*结点类型*/

}BSTNode;

typedef BSTNode *BSTree;

void main() {

BSTNode *SearchBST(BSTree T,KeyType key); void InsertBST(BSTree *Tptr,KeyType key); BSTree CreateBST(void); void ListBinTree(BSTree T); BSTree T; BSTNode *p; int key;

printf(\请输入关键字（输入0为结束标志）：\\n\T=CreateBST();

/*用广义表表示二叉树*/

6

}

ListBinTree(T); printf(\

printf(\请输入欲查找关键字：\scanf(\p=SearchBST(T,key); if(p==NULL) else

printf(\找到%d！\\n\ListBinTree(p); printf(\

printf(\没有找到%d！\\n\

BSTNode *SearchBST(BSTree T,KeyType key) { */

}

void InsertBST(BSTree *Tptr,KeyType key) { }

7

/*在二叉排序树T上查找关键字为key的结点，成功时返回该结点位置，否则返if(T==NULL||key==T->key) /*递归的终结条件*/

return T;

/*若T为空，查找失败；否则成功，返回找到的结点位置

回NULL*/

if(keykey) else

return SearchBST(T->rchild,key); /*继续在右子树中查找*/ return SearchBST(T->lchild,key);

/*若二叉排序树*Tptr中没有关键字为key，则插入，否则直接返回*/ BSTNode *f,*p=*Tptr; while(p){ }

p=(BSTNode *)malloc(sizeof(BSTNode)); p->key=key;p->lchild=p->rchild=NULL; if(*Tptr==NULL)

*Tptr=p;

/*生成新结点*/ /*原树为空*/

f=p;

/*p的初值指向根结点*/ /*查找插入位置*/

/*树中已有key，无须插入*/ /*f保存当前查找的结点*/

if(p->key==key) return;

p=(keykey)? p->lchild:p->rchild;

/*若keykey，则在左子树中查找，否则在右子树中查找*/

/*新插入的结点为新的根*/

else/*原树非空时将新结点*p作为*f的左孩子或右孩子插入*/

if(keykey)

f->lchild=p; else f->rchild=p;

BSTree CreateBST(void) { }

/*输入一个结点序列，建立一棵二叉排序树，将根结点指针返回*/ BSTree T=NULL; KeyType key; scanf(\while(key){ } return T;

/*返回建立的二叉排序树的根指针*/

/*读入一个关键字*/

/*假设key=0是输入结束标志*/ /*将key插入二叉排序树T*/

/*初始时T为空树*/

InsertBST(&T,key); scanf(\

/*读入下一关键字*/

六、 思考题

请思考采用其他存储结构实现的二叉排序树建立算法。

七、 实验报告要求

具体内容包含以下几项：实验题目、实验目的、实验环境、实验内容与完成情况（要求附上自主设计的源程序）、实验中出现的问题、对问题的解决方案、完成思考题、实验总结等。

8