作业帮编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/12 18:30:18
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列
已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列,编写算法达到要求结果.
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点值递增序列已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得到一个由小到大的结点
首先看下二叉排序树的定义：
二叉排序树（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");
}