📄 bst.c
字号:
/* 二插排序树 */
#include<stdio.h>
#include<malloc.h>
#define Length sizeof(struct BSTreeNode)
typedef struct BSTreeNode{
int data;
struct BSTreeNode *left;//左孩子指针
struct BSTreeNode *right;//右孩子指针
}BSTreeNode,* BSTree;//BSTree为结构体BSTreeNode的指针类型
typedef struct Snode{
BSTree addr;
struct Snode *link;
}Snode;//定义结构体Snode，用于构造链式结构的堆栈
void CreateBSTree(BSTree *BST,int a[],int n)
//利用数组中的n个元素建立二叉搜索树
{
void Insert();
int i;
*BST=NULL;
for(i=0;i<n;i++)
Insert(BST,a[i]);
}
/************************************************/
void Insert(BSTree *BST,int item)
{ //向二叉搜索树中插入一个 元素item，变参BST初始指向
//一棵树的根节点，并且BST必须为变参
BSTree p,T;
T=*BST;//T指向BST所指向的节点
if(T==NULL){
//把按照item元素生成的新节点链接到已经找到的插入位置
p=(BSTree)malloc(Length);
p->data=item;
p->left=p->right=NULL;
*BST=p;
}
else if(item==T->data){//当item元素的值与树中节点的值相等时，
//终止插入操作
printf("\nThe data has exist in the tree.Can not insert!!\n");
return;
}
else if(item<T->data) //向左子树中插入元素
Insert(&(T->left),item);
else //向右子树中插入元素
Insert(&(T->right),item);
}
/************************************************/
void Preorder(BSTree BST)
{ //前序遍历由BST指针所指向的二叉树
if(BST!=NULL){
printf("%d ",BST->data); //访问根节点
Preorder(BST->left); //前序遍历左子树
Preorder(BST->right); //前序遍历右子树
}
}
/************************************************/
void Inorder(BSTree BST)
{ //中序遍历由BST指针所指向的二叉树
if(BST!=NULL){
Inorder(BST->left); //中序遍历左子树
printf("%d ",BST->data); //访问根节点
Inorder(BST->right); //中序遍历右子树
}
}
/************************************************/
void Postorder(BSTree BST)
{ //后序遍历由BST指针所指向的二叉树
if(BST!=NULL){
Postorder(BST->left); //后序遍历左子树
Postorder(BST->right); //后序遍历右子树
printf("%d ",BST->data); //访问根节点
}
}
/************************************************/
void Levelorder(BSTree BST)
{ //按层遍历由BST指针所指向的二叉树，
//该层遍历算法使用一个队列
int Maxlength=30;//定义用于存储队列的数组的长度
BSTree q[30];//定义队列所使用的数组空间，元素类型
BSTree p; //为指向节点的指针类型
int front,rear;
front=rear=0;//定义队首指针和队尾指针，初始均置0表示空队
if(BST!=NULL){ //将树根指针进队
rear=(rear+1)%Maxlength;
q[rear]=BST;
}
while(front!=rear){ //当队列非空时执行循环
front=(front+1)%Maxlength; //使队首指针指向队首元素
p=q[front];
printf("%d ",p->data); //输出队首元素所指向的节点的值
if(p->left!=NULL){ //若节点存在左孩子，则左孩子节点指针进队
rear=(rear+1)%Maxlength;
q[rear]=p->left;
}
if(p->right!=NULL){ //若节点存在左孩子，则左孩子节点指针进队
rear=(rear+1)%Maxlength;
q[rear]=p->right;
}
} //while end
}
/************************************************/
void InorderUnrec(BSTree BST)
{ //中序遍历由BST指针所指向的二叉树
//这是一个非递归的算法
Snode *top,*p; //定义链式结构堆栈的栈顶指针
BSTree t;
t=BST;
top=NULL; //初始栈顶指针top
while(t!=NULL || top!=NULL){ //t指针指向的节点不为空和栈顶指针top
//不为空时，执行循环
while(t!=NULL){ //t指针指向的节点不为空时，执行循环
p=(Snode *)malloc(sizeof(Snode)); //进栈操作
p->addr=t;
p->link=top;
top=p;
t=t->left; //t指针指向左孩子
} // end while
if(top!=NULL){ //栈顶指针不为空时，执行循环
t=top->addr; //输出栈顶元素所指向的节点的值
printf("%d ",t->data);
p=top;
top=top->link; //栈顶指针top指向下一个元素
free(p); //释放指针p的空间
t=t->right; //指针t指向右孩子
}
}//end while
}
/************************************************/
int Find(BSTreeNode *BST,int *item)
{ //从BST指针所指向的二叉搜索树中查找等于给定
//值item的元素，此算法为非递归算法
while(BST!=NULL){ //查找整棵树，找到返回1
if(*item==BST->data){
*item=BST->data;
return 1;
}
else if(*item<BST->data)//查找左子树
BST=BST->left;
else //查找右子树
BST=BST->right;
}
return 0; //找不到给定的值，返回0
}
/************************************************/
void Change(BSTree *BST)
{ //交换由变参BST所指向的二叉搜索树上每个节点
//的左右子树
BSTree temp,T; //定义temp为交换操作的中间变量
T=*BST; //T指向BST所指向的节点
temp=(BSTree)malloc(Length);
if(T==NULL) //对于空树，直接返回
return;
else if(T->left!=NULL || T->right!=NULL){
//当左子树或右子树不为空时，进行交换操作
temp=T->left;
T->left=T->right;
T->right=temp;
}
Change(&(T->left));
//交换左子树的每个节点的左右子树
Change(&(T->right));
//交换右子树的每个节点的左右子树
}
/************************************************/
int BSTreeDepth(BSTree BST)
{ //求由BST指针指向的一棵二叉树的深度
if(BST==NULL) //对于空树，返回0并结束递归
return 0;
else{
int dep1=BSTreeDepth(BST->left);
//计算左子树的深度
int dep2=BSTreeDepth(BST->right);
//计算右子树的深度
if(dep1>dep2)//返回树的深度
return dep1+1;
else
return dep2+1;
}
}
/************************************************/
int NodeNum(BSTree BST)
{ //求由BST指针指向的一棵二叉树的叶子节点数
int n=0; //定义元素n用来统计叶子节点数
if(BST==NULL)//对于空树，返回0并结束递归
return 0;
else{
n+=NodeNum(BST->left);
//计算左子树的叶子节点数
n+=NodeNum(BST->right);
//计算右子树的叶子节点数
n++; //加上树根节点
}
return n;//返回叶子节点数
}
/************************************************/
main()
{
int j,k,b[10]={38,26,35,28,62,50,94,55,77,88};
BSTree BST=NULL;
char a[50];
while(1)
{
printf("\nplease choose a function:\n1.Create a new binary sort tree or Insert a new node.");
printf("\n2.Preorder Traverse tree.");
printf("\n3.Inorder Traverse tree.\n4.Postorder Traverse tree.\n5.Level order Traverse tree.");
printf("\n6.Unrecursive Inorder Traverse tree.");
printf("\n7.Find a given key data.\n8.Exchange left and right child tree.\n9.Tree`s highter and node`s number.");
printf("\n0.Exit.\n");
for(j=0;j<100;j++){
scanf("%c",&a[j]);
if(a[j]=='\n') break;
} /*功能选择*/
if(a[1]!='\n') {printf("\nError!!!\n");continue;}
else{
if(a[0]=='0') break;
switch(a[0])
{
case '1' :while(1)
{
printf("\n1.Create a new binary tree by system.\n2.Input a new data.\n0.Exit.\n");
for(j=0;j<100;j++){
scanf("%c",&a[j]);
if(a[j]=='\n') break;
} /*功能选择*/
if(a[1]!='\n') {printf("\nError!!!\n");continue;}
else if(a[0]=='0')break;
else if(a[0]=='1'){
CreateBSTree(&BST,b,10);
printf("\nThe binary sort has been created.\n");
}
else if(a[0]=='2'){
printf("\nInput a data:");scanf("%d%*c",&k);Insert(&BST,k);
}
else printf("\nerror!!\n");
};break;
case '2' :printf("\n______________________________________________________________\n");
printf("\nPreorder traverse the tree:\n");Preorder(BST);
printf("\n______________________________________________________________\n");
break;
case '3' :printf("\n______________________________________________________________\n");
printf("\nInorder traverse the tree:\n");Inorder(BST);
printf("\n______________________________________________________________\n");
break;
case '4' :printf("\n______________________________________________________________\n");
printf("\nPostorder traverse the tree:\n");Postorder(BST);
printf("\n______________________________________________________________\n");
break;
case '6' :printf("\n______________________________________________________________\n");
printf("\nUnrecursive Inorder traverse the tree:\n");InorderUnrec(BST);
printf("\n______________________________________________________________\n");
break;
case '7' :printf("\nInput a data you want to find:");scanf("%d%*c",&k);
if(Find(BST,&k)){
printf("\n______________________________________________________________\n");
printf("\n\nThe data %d has existed in the tree.\n",k);
printf("\n______________________________________________________________\n");
}
else{
printf("\n______________________________________________________________\n");
printf("\n\nThe data did not find in the tree.\n");
printf("\n______________________________________________________________\n");
}
break;
case '8' :printf("\n______________________________________________________________\n");
printf("\nExchange left and right child tree.\nThe result show by Inorder:\n");
Change(&BST);
Inorder(BST);
printf("\n______________________________________________________________\n");
break;
case '9' :printf("\n______________________________________________________________\n");
printf("\nThe tree`s Depth is : %d\n",BSTreeDepth(BST));
printf("\nThe tree`s node numbers are : %d\n",NodeNum(BST));
printf("\n______________________________________________________________\n");
break;
case '5' :printf("\n______________________________________________________________\n");
printf("\nLevel order traverse the tree:\n");Levelorder(BST);
printf("\n______________________________________________________________\n");
break;
default:printf("\nerror!!\n");
}//end switch
}//end else
}// end while
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -