C中二叉排序树的非递归和递归插入操作以及中序遍历代码实现【可运行】
#include <stdio.h>
#include <stdlib.h>
typedef int KeyType;
typedef struct node
{
KeyType key;
struct node* lchild, * rchild;
}BSTNode, * BSTree;
//二叉排序树递归插入操作
int InsertBST1(BSTree& T, int k) {
if (T == NULL) {//原树为空，新插入的结点为根结点
T = (BSTree)malloc(sizeof(BSTNode));
if (T == NULL) {
return 0;//内存分配失败的情况
}
T->key = k;
T->lchild = T->rchild = NULL;
return 1;//返回1, 插入成功
}
else if (k == T->key) {//树中存在相同关键字的结点，插入失败
return 0;
}
else if (k < T->key) {
return InsertBST1(T->lchild, k); //如果插入的值小于结点的值，则递归插入函数进行查找
}
else {
return InsertBST1(T->rchild, k); //如果插入的值大于结点的值，则递归插入函数进行查找
}
}
//二叉排序树非递归插入操作
int InsertBST2(BSTree& T, KeyType k)
{
BSTree q, s;//新增两个结点q，s
s = (BSTree)malloc(sizeof(BSTNode));//分配一个新节点
if (s == NULL) {
return 0;//内存分配失败的情况
}
s->key = k;//新结点存储的数据为插入的值
s->lchild = NULL;
s->rchild = NULL;
if (T == NULL)//如果当前结点为空则将新分配的结点s赋给当前结点
{
T = s;
return 1;
}
q = T;//
while (q) {//
BSTree p = q;
if (k == q->key){//如果插入的值等于结点的值，则释放新分配出的内存
free(s);
return 0;
}
if (k < q->key){//如果插入的值小于结点的值，则令该结点等于其左孩子结点
q = q->lchild;
if (q == NULL)
p->lchild = s;//如果该结点的还在结点等于空，则令其孩子结点等于结点s，否则继续找孩子为空的结点
}
else {//如果插入的值大于结点的值，则令该结点等于其右孩子结点
q = q->rchild;
if (q == NULL)
p->rchild = s;//如果该结点的还在结点等于空，则令其孩子结点等于结点s，否则继续找孩子为空的结点
}
}
q = s;
return 1;
}
void CreateBST(BSTree &T)
{
KeyType key;
T = NULL;
scanf_s("%d", &key);
while (key!=0)
{
InsertBST2(T, key);
//InsertBST1(T, key);
scanf_s("%d", &key);
}
}
void InOrder(BSTree T)
{
if (T != NULL)
{
InOrder(T->lchild);
printf("%d ", T->key);//这个前置为先序遍历，后置为后序遍历
InOrder(T->rchild);
}
}
int main()
{
BSTree T;
printf("建立二叉排序树，请输入序列:
");
CreateBST(T);
printf("中序遍历输出序列为:");
InOrder(T);
}
//34
//25
//56
//79
//12
//38
//先序遍历输出序列为:34 25 12 56 38 79
//中序遍历输出序列为:12 25 34 38 56 79
//后序遍历输出序列为:12 25 38 79 56 34
结果为
