Question

编写算法:已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列

已知二叉排序树按二叉链表形式存储，树中结点各不相同，欲得到一个由小到大的结点值递增序列，编写算法达到要求结果。

Answer 1

首先看下二叉排序树的定义：

二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、右子树也分别为二叉排序树；

由定义可知，采用中序遍历的输出序列，就是“一个由小到大的结点值递增序列”

代码参考如下：

#include <stdio.h>
#include <malloc.h>
typedef int KeyType;
typedef struct node             //记录类型
{
 KeyType key;                //关键字项
 struct node *lchild,*rchild; //左右孩子指针
} BSTNode;
int InsertBST(BSTNode *&p,KeyType k) 
{
    if (p==NULL)      //原树为空, 新插入的记录为根结点
 {
  p=(BSTNode *)malloc(sizeof(BSTNode));
  p->key=k;
  p->lchild=p->rchild=NULL;
  return 1;
 }
 else if (k==p->key)     //树中存在相同关键字的结点,返回0
  return 0;
 else if (k<p->key) 
  return InsertBST(p->lchild,k); //插入到*p的左子树中
 else  
  return InsertBST(p->rchild,k);  //插入到*p的右子树中
}
BSTNode *CreateBST(KeyType A[],int n) //返回BST树根结点指针
{
 BSTNode *bt=NULL;            //初始时bt为空树
 int i=0;
 while (i<n) 
 {
  InsertBST(bt,A[i]);     //将关键字A[i]插入二叉排序树T中
  i++;
    }
    return bt;                  //返回建立的二叉排序树的根指针
}
void mid_order(BSTNode *T)//中序遍历二叉树
{
    if(T)
    {
    mid_order(T->lchild);
    printf(" %d ",T->key);
    mid_order(T->rchild);
    }
}
void main()
{
 BSTNode *bt,*p,*f;
 int n=9;
 KeyType a[]={1,12,5,8,3,10,7,13,9};
 bt=CreateBST(a,n);
 printf("BST:");mid_order(bt);printf("\n");
         
}

追问

首先，谢谢你的帮助。我还有一个疑问，因为这是一道数据结构题，我是不只用写出算法即可，还是需要完整的程序啊

追答

以上已经包含完整的程序可编译可运行

追问

恩恩，好的，谢谢啊。

追答

如有帮助，请采纳

追问

必须采纳你的。。稍后给你分哈。

Answer 2

中序遍历一遍

追问

算法呢？