二叉树模拟网站:Binary Search Tree Visualization (usfca.edu)
图
代码:
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct BSTNode{
KeyType key;
struct BSTNode *lchild, *rchild;
}BSTNode, *BiTree;
int BST_Insert(BiTree &T,KeyType k)
{
BiTree TreeNew=(BiTree)calloc(1,sizeof(BSTNode));//新结点申请空间
TreeNew->key=k;//把值放入
if(NULL==T){
T=TreeNew;
return 1;//代表插入成功
}
BiTree p=T,parent;//p用来查找树
while(p){
parent=p;//parent用来存p的父亲
if(k>p->key){
p=p->rchild;
}else if(k<p->key){
p=p->lchild;
}else{
return -1;//相等元素不可放入查找树,考研不会考相等元素放入问题
}
}
//接下来要判断放到父亲的左边还是右边
if(k>parent->key){
parent->rchild=TreeNew;
}else{
parent->lchild=TreeNew;
}
return 1;
}
void Creat_BST(BiTree &T,KeyType str[],int n)
{
for(int i=0;i<n;i++){
BST_Insert(T,str[i]);//把某一个结点放入二叉查找树
}
}
BiTree BST_Search(BiTree T,KeyType key,BiTree &p)
{
p = NULL;//存储父亲结点的地址值
while(T!=NULL&&key!=T->key){
p=T;
if(key<T->key)
T=T->lchild;
else
T=T->rchild;
}
return T;
}
void InOrder(BiTree T)
{
if(T!=NULL){
InOrder(T->lchild);
printf("%3d",T->key);
InOrder(T->rchild);
}
}
int main()
{
BiTree T = NULL;//树根
BiTree parent;//存储父亲结点的值
BiTree search;
KeyType str[7] = {54,20,66,40,28,79,58};
Creat_BST(T,str,7);
InOrder(T);
printf("\n");
search=BST_Search(T,40,parent);
if(search){
printf("找到对应结点值,值=%d\n",search->key);
}else{
printf("未找到对应结点\n");//没找到search返回的是NULL
}
return 0;
}
运行
20 28 40 54 58 66 79
找到对应结点值,值=40
中序遍历正好从小到大