Question

把已经建立的二叉树转换成二叉排序树的算法实现（C++）

Answer 1

typed RcdType TElemType;
void Insert_BST( BiTree &T, KeyType e )
{ // 在以T为根指针的二叉排序树中插入记录e
s=new BiTNode; // 生成新的结点
s->data=e; s->lchild=NULL; s->rchild=NULL; //新插入结点必为叶
if(!T) T=s; // 插入的结点为根结点
else {
p=T;
while( p) // 查找插入位置
if(e .key< p->data .key)
{ f=p; p=p->lchild; } // 应插入在左子树中
else
{ f=p; p=p->rchild; } // 应插入在右子树中
if(e.key<f->data.key) f->lchild=s;//插入为f所指结点的左子树根
else f->rchild = s; // 插入为f所指结点的右子树根
} //else
} // Insert_BST
void BSTSort( SqList &L )
{ // 利用二叉排序树对顺序表L进行排序
BiTree T=NULL; // 初始化二叉排序树为空树
for(i=1;i<L.length;++i)
Insert_BST( T,L.r[i]); // 按顺序表L构造二叉排序树
i=0;
InOrder(T，Output(T,L,i)); // 中序遍历二叉排序树
//通过函数指针引用Output，将排序记录由小到大输出至L.r[i]
} // BSTSort
其中函数Output的具体实现如下：
void Output(BiTree T, SqList &L, int &i )
{ L.r[++i]=T->data; }

完成。