#include <malloc.h>
typedef int KeyType;
typedef char InfoType[10];
typedef struct node //記錄類型
{
KeyType key; //關鍵字項
InfoType data; //其他數據域
struct node *lchild,*rchild; //左右孩子指針
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k)
{
if (p==NULL) //原樹為空, 新插入的記錄為根結點
{
p=(BSTNode *)malloc(sizeof(BSTNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}
else if (k==p->key) //樹中存在相同關鍵字的結點,返回0
return 0;
else if (k<p->key)
return InsertBST(p->lchild,k); //插入到*p的左子樹中
else
return InsertBST(p->rchild,k); //插入到*p的右子樹中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST樹根結點指針
{
BSTNode *bt=NULL; //初始時bt為空樹
int i=0;
while (i<n)
{
InsertBST(bt,A[i]); //將關鍵字A[i]插入二叉排序樹T中
i++;
}
return bt; //返回建立的二叉排序樹的根指針
}
void DispInDescrease(BSTNode *bt){ //按從小到大輸出查找樹中的內容,對該樹中序遍歷即可
if(bt){
DispInDescrease(bt->lchild);
printf("%d\t",bt->key);
DispInDescrease(bt->rchild);
}
}
void main()
{
BSTNode *bt,*p,*f;
int n=9;
KeyType a[]={1,12,5,8,3,10,7,13,9};
bt=CreateBST(a,n);
DispInDescrease(bt);
}
//已上機驗證成功