数据结构实验五查找算法应用

天津理工大学实验报告

学院（系）名称：计算机与通信工程学院

实验思路：首先定义二叉链表的存储结构，定义左右孩子， 用递归算法定义插入二叉排序树，按照左小于中小于右，即程序中的insert（）函数。然后是生成二叉树的算法，即CreateTree（）函数，最后是中序遍历的递归算法的算法，即InOrder（）函数。下面是主函数main（）函数。程序结果如图所示。

实验代码如下：

#include<stdio.h>

#include<stdlib.h>

typedef int ElemType;//每个元素的数据类型为Elemtype，假设为int

typedef int KeyType;

typedef struct BiTNode{//定义二叉链表结构

ElemType data;

struct BiTNode * lchild,* rchild;//左右孩子指针

}BiTNode;

typedef BiTNode *BiTree;//将BiTree定义为指向二叉链表节点结构的指针类型

BiTree insert(BiTree T,KeyType k){//二叉排序树的插入，递归算法

if(T==NULL){

T=(BiTree)malloc(sizeof(BiTNode));

T->data=k;

T->lchild=T->rchild=NULL;

}

else if(k<T->data) T->lchild = insert(T->lchild,k);

else if(k>T->data) T->rchild = insert(T->rchild,k);

return T;

}

BiTree CreateTree(int n)

{//生成二叉树的递归算法

int i ;

BiTree T;

T=(BiTree)malloc(sizeof(BiTNode));

T= NULL;

for( i=0; i<n; i++)

{

int k;

scanf("%d",&k);

T=insert(T,k);

}

return T;

}

void InOrder(BiTree root){//中序遍历

if(root==NULL) return;

InOrder(root->lchild);

printf("% d",root->data);

InOrder(root->rchild);

}

void main()

{

BiTree p;

int n;

printf("请输入关键字个数n:\n"); scanf("%d",&n);

printf("请输入节点值创建二叉排序数:\n"); p=CreateTree(n);

printf("递归中序遍历为：\n");

InOrder(p);

printf("\n");

printf("以上为遍历的结果！\n"); }

实验结果如图所示：