#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 0;
}
BiTree p=T,parent;//用p来查找树
while(p)//p是用来遍历的
{
parent=p;//parent用来存p的父亲 当p等于NULL时,parent存的刚好是NULL
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 0;
}
//二叉排序树函数
void Creat_BST(BiTree& T,KeyType* str,int len)
{
int i;
for(i=0;i<len;i++)
{
BST_Insert(T,str[i]);//把某个结点放入 二叉查找树;
}
}
//中序遍历有序输出(因为中序结果就相当于垂直投影 进而有序输出了排好序的树)
void InOrder(BiTree T)
{
if(T!=NULL)
{
InOrder(T->lchild);
printf("%3d",T->key);
InOrder(T->rchild);
}
}
BiTree BST_Insert(BiTree T,KeyType k,BiTree &parent)//parent是会变的因为相当于偏离的p
{
parent=NULL;
while (T!=NULL&&k!=T->key)
{
parent=T;
if(k>T->key)
{
T=T->rchild;
} else{
T=T->lchild;
}
}
return T;
}
int main() {
BiTree T=NULL;//树根
KeyType str[7]={54,20,66,40,28,79,58};//将要进入二叉排序树的元素值
Creat_BST(T,str,7);
InOrder(T);//中序遍历二叉查找树是由小到大的
printf("\n");
BiTree search,parent;
search = BST_Insert(T,40,parent);
if(search)
{
printf("find key %d\n",search->key);
} else{
printf("not find\n");
}
return 0;
}
二叉树的非递归遍历(详解)
2024-03-11 21:48:06 35 阅读