#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
typedef struct node {
datatype key;
struct node* lchild, * rchild;
} BSTnode;
typedef BSTnode * BSTree;
//插入结点,并对结点进行判断,确定插入左子树还是右子树
//基于二叉排序树的结点的插入算法
void InsertBSTree(BSTree* t, datatype x)
{
BSTree f = NULL, p;
p = *t;
while (p)
{
if (x == p->key)return;
f = p;
p = (x < p->key) ? p->lchild : p->rchild;
}
p = (BSTree)malloc(sizeof(BSTnode));
if (p != NULL)
{
p->key = x;
p->lchild = p->rchild = NULL;
}
if (*t == NULL) *t = p;
else
if (x < f->key)
f->lchild = p;
else f->rchild = p;
}
//从键盘输入元素的值,创建相应的二叉排序树
BSTree creatBSTree(void)
{
BSTree t = NULL;
datatype key;
printf("\n请输入一个以-1为结束标志的结点序列;\n");
scanf_s("%d", &key);
while (key != -1)
{InsertBSTree(&t,key);
scanf_s("%d", &key);
}
return t;
}
//逆中序遍历从大到小输出二叉树结点,即先遍历右子树,然后根,最后左子树
void Inorder(BSTree rood)
{
if (rood)
{
// 先序遍历右子树
Inorder(rood->rchild);
// 访问根节点
printf("%d\n",rood ->key);
// 先序遍历左子树
Inorder(rood->lchild);
}
}
int main()
{
BSTree rood{};
creatBSTree(&rood);
printf("结果序列为:\n");
Inorder(rood);
return 0;
}