二叉排序树，用顺序表（一维数组）作存储结构

来源：百度知道 编辑：UC知道 时间：2024/05/05 18:19:51
二叉排序树，用顺序表（一维数组）作存储结构
1 以回车为输入结束标志，输入数列L，生成一棵二叉排序树T
2 对二叉树T作中序遍历，输出结果
3 计算二叉排序树T查找成功的平均查找长度，输出结果
4 输入元素X，查找二叉排序树T，若存在含X的结点，则删除该结点，并做中序遍历，执行操作2，否则输出信息”无X“
需要用最简单的C++语言编写...谢谢

#include <iostream>
#include <malloc.h>
using namespace std;

typedef struct _Node
{
int key;
struct _Node *lchild,*rchild;
} *nodePtr;

nodePtr search(nodePtr t,int key)//查找关键字key
{
if (t == NULL)
{
return NULL;
}
else if(t->key == key)
{
return t;
}
else if (t->key < key)
{
return (search(t->rchild,key));
}
else
{
return (search(t->lchild,key));
}
}

nodePtr insert(nodePtr t,nodePtr s)//插入节点
{
if (t == NULL)
{
t = s;
}
else if (t->key > s->key)
{
t->lchild=insert(t->lchild,s);
}
else
{
t->rchild=insert(t->rchild,s);
}
return (t);
}

void order(nodePtr t)//中序遍历
{//对二叉树T作中序遍历，输出结果
if (t != NULL)
{
or