// 链式二叉查找树的各种操作.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include
using namespace std;
struct BSTree
{
int data;
BSTree *left;
BSTree *right;
};
//标记在插入时，如果已存在，则为true ，表示不需要插入，否则为false
bool flag = false;
int a[100];
//查找操作
BSTree *search(BSTree *r,int x)
{
if(r==NULL)
return NULL;
else
{
if(r->data==x)
return r;
else if(r->data>x)
return search(r->left,x);
else
return search(r->right,x);
}
}
//插入操作
BSTree* insert(BSTree *r,BSTree *s)
{
//首先查找树中是否已存在此节点
BSTree *p = search(r,s->data);
if(p==NULL)
{
if(r==NULL)
{
r=s;
}
else if(s->data
r->left = insert(r->left,s);
else if(s->data>r->data)
r->right = insert(r->right,s);
}
else
flag = true;
return r;
}
//建树
BSTree * createBSTree(BSTree *r,int *a,int n)
{
int i;
BSTree * t;
t = r;
for(i=0;i { BSTree *s = (BSTree*)malloc(sizeof(BSTree)); s->data=a[i]; s->left=NULL; s->right=NULL; t = insert(t,s); } return t; } //获得其父节点 BSTree *getFather(BSTree *r, BSTree *s) { BSTree *sf; if(r==NULL||r==s) sf=NULL; else { if(s==r->left||s==r->right) sf= r; else if(s->data > r->data) sf=getFather(r->right,s); else sf=getFather(r->left,s); } return sf; } //删除操作 BSTree * deleteNode(BSTree *r,BSTree *s) { //BSTNODE * temp, * tfather, * pf; BSTree *temp,*father,*sf; //pf = getfather(p, r); sf=getFather(r,s); //被删除结点是叶子结点, 不是根结点 if(s->left==NULL&&s->right==NULL&&sf!=NULL) // if(sf->left==s) sf->left=NULL; // else sf->right=NULL; //被删除结点是叶子结点,又是根结点 else if(s->left==NULL&&s->right==NULL&&sf!=NULL) r=NULL; // else if(s->left==NULL&&s->right!=NULL&&sf!=NULL) if(sf->left==s) sf->left=s->right; else sf->right=s->right; //被删除结点有右孩子,无左孩子.被删结点是根结点 else if(s->left==NULL&&s->right!=NULL&&sf==NULL) r=s->right; //被删结点有左孩子,无右孩子.被删结点不是根结点 else if(s->left!=NULL&&s->right==NULL&&sf!=NULL) if(sf->left==s) sf->left=s->left; else sf->right=s->left; //被删结点有左孩子,无右孩子.被删结点是根结点 else if(s->left!=NULL&&s->right==NULL&&sf==NULL) r=s->left; else if(s->left!=NULL&&s->right!=NULL) { temp = s->left; father = s; //找出左子树最大的节点 while(temp->right!=NULL) { father=temp; temp=temp->right; } s->data = temp->data; if(father!=s) father->right = temp->left; else father->left=temp->left; } if(r==NULL) cout<<"删除之后，二叉排序树为空！"< else cout<<"删除成功！"< return r; } //前序输出 void preOrder(BSTree *r) { if(r==NULL) return; else { cout< preOrder(r->left); preOrder(r->right); } } //中序输出 void inOrder(BSTree *r) { if(r==NULL) return ; else { inOrder(r->left); cout< inOrder(r->right); } } //后续输出 void postOrder(BSTree *r) { if(r==NULL) return ; else { postOrder(r->left); postOrder(r->right); cout< } } int _tmain(int argc, _TCHAR* argv[]) { int cases; cout<<"请输入案例个数："< cin>>cases; while(cases--) { int n; flag = false; BSTree *root=NULL; cout<<"请输入元素个数："< cin>>n; int i; cout<<"请输入这些元素："< for(i=0;i cin>>a[i]; cout<<"建立二叉排序树!"< root = createBSTree(root,a,n); if(root!=NULL) cout<<"二叉排序树建立成功！"< else { cout<<"二叉排序树建立失败！"< return 0; } cout<<"此二叉树根的值为："< cout< c