BST二叉排序树的建立以及应用
浏览数：312 /
时间：2015年06月08日
二叉排序树又叫二叉查找树，英文名称是：Binary Sort Tree. BST的定义就不详细说了，我用一句话概括：左 < 中 < 右。 根据这个原理，我们可以推断：BST的中序遍历必定是严格递增的。
在建立一个BST之前，大家可以做一下这个题目（很简单的）：
已知，某树的先序遍历为：4, 2, 1 ,0, 3, 5, 9, 7, 6, 8. 中序遍历为: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. 请画出该树。
我们知道，树的基本遍历有4种方式，分别是：
先序遍历；中序遍历；后续遍历；层次遍历。事实上，知道任意两种方式，并不能唯一地确定树的结构，但是，只要知道中序遍历和另外任意一种遍历方式，就一定可以唯一地确定一棵树，于是，上面那个题目的答案如下：
#include <iostream>
using namespace std;// BST的结点
typedef struct node
{
int key;
struct node *lChild, *rChild;
}Node, *BST;
// 在给定的BST中插入结点，其数据域为element, 使之称为新的BST
bool BSTInsert(Node * &p, int element)
{
if (p == NULL)
{
p = new Node;
p->key = element;
p->lChild = p->rChild = NULL;
}
if (element == p->key)
{
return false;
}
if (element < p->key)
{
BSTInsert(p->lChild, element);
}
else
BSTInsert(p->rChild, element);
return true;
}
void createBST(BST &p)
{
int k;
p = NULL;
printf("请输入一组数字，#结束\n");
while(scanf("%d", &k)==1)
BSTInsert(p,k);
}
//先序遍历
void preorderBST(BST p)
{
if (p)
{
cout << p->key << " ";
preorderBST(p->lChild);
preorderBST(p->rChild);
}
}
//中序遍历（这个可以做为排序算法）//后面的堆排序需要用到这种方法
void inorderBST(BST p)
{
if (p)
{
inorderBST(p->lChild);
cout << p->key << " ";
inorderBST(p->rChild);
}
}
int main(void)
{
BST T;
createBST(T);
inorderBST(T);
cout << endl;
return 0;
}
实验结果：
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
