问题：
输入一系列整数，建立二叉排序数，并进行前序，中序，后序遍历。
输入：
输入第一行包括一个整数n(1<=n<=100)。接下来的一行包括n个整数。
输出：
可能有多组测试数据，对于每组数据，将题目所给数据建立一个二叉排序树，并对二叉排序树进行前序、中序和后序遍历。每种遍历结果输出一行。每行最后一个数据之后有一个空格。
例如：
4
21 10 5 39
输出：
21 10 5 39
5 10 21 39
5 10 39 21
分析：
二叉排序树，就是左子树全部小于根，右子树全部大于根
Node *t;
t=NULL;
while(n--){
cin>>k;
create_tree(t,k);
}
Node* create_tree(Node *&t,int k){
if(t==NULL){
t=new Node;
t->data=k;
t->lchild=NULL;
t->rchild=NULL;
}else if(k>t->data){
create_tree(t->rchild,k);
}else if(k<t->data){
create_tree(t->lchild,k);
}
return t;
}
代码：
#include <iostream>
using namespace std;
typedef struct Node{
int data;
struct Node *lchild;
struct Node *rchild;
};
Node* create_tree(Node *&t,int k){
if(t==NULL){
t=new Node;
t->data=k;
t->lchild=NULL;
t->rchild=NULL;
}else if(k>t->data){
create_tree(t->rchild,k);
}else if(k<t->data){
create_tree(t->lchild,k);
}
return t;
}
void pre(Node *&t){
if(t){
cout<<t->data<<" ";
pre(t->lchild);
pre(t->rchild);
}
}
void zhongxu(Node *&t){
if(t){
zhongxu(t->lchild);
cout<<t->data<<" ";
zhongxu(t->rchild);
}
}
void hou(Node *&t){
if(t){
hou(t->lchild);
hou(t->rchild);
cout<<t->data<<" ";
}
}
int main()
{
int n,k;
while(cin>>n){
Node *t;
t=NULL;
while(n--){
cin>>k;
create_tree(t,k);
}
pre(t);
cout<<endl;
zhongxu(t);
cout<<endl;
hou(t);
cout<<endl;
}
return 0;
}
结果：
查找二叉树中的值：
Tree* find_k1(Tree *&t,int k){
Tree *t2=t;
while(t2){
if(k==t2->data){
return t2;
}else if(k>t2->data){
t2=find_k1(t2->rchild,k);
}else if(k<t->data){
t2=find_k1(t2->lchild,k);
}
}
return NULL;
}
删除二叉排序树的点
bool delete_tree(Tree *&t){
if(t->rchild==NULL&&t->lchild==NULL){
delete t;
}else if(t->rchild==NULL){//如果这个点只有左子树,就把左子树直接弄上去就可以了
Tree *t2=t;
t=t->lchild;
delete t2;
}else if(t->lchild==NULL){//如果这个点只有右子树,就把右子树直接弄上去就可以了
Tree *t2=t;
t=t->rchild;
delete t2;
}else{//左右子树都不为空
//当左右子树都不为空的时候，有两种方法来删除
/**<
1.找到这个节点的左节点的最右边的元素代替，相当于用前继节点代替
2.找到这个节点的右节点的最左边的元素代替，相当于用后继节点代替
*/
//这里我采用第一种
Tree *t3=t;//t3标识t2的前继
Tree *t2=t->lchild;
while(t2->rchild){//找到左节点的最右边的点，以及他的前继
t3=t2;
t2=t2->rchild;
}
//把前继节点t2代替t1
t->data=t2->data;
//如果t3==t1说明t1的左节点没有右节点了，把t2的左子树弄到t3的左子树上
if(t3==t){
t3->lchild=t2->lchild;
}else{//如果不相等，说明有右节点，把t2的左子树弄到t3的右子树上
t3->rchild=t2->lchild;
}
delete t2;
}
return true;
}
bool del_tree(Tree *&t,int k){
if(!t) /* 不存在关键字等于k的数据元素 */
return false;
else{
if (k==t->data) /* 找到关键字等于key的数据元素 */
return delete_tree(t);
else if (k<t->data)
return del_tree(t->lchild,k);
else
return del_tree(t->rchild,k);
}
}
