// 鏈式二叉查找樹的各種操作.cpp : Defines the entry point for the console application.
//
#include "stdafx.h"
#include<iostream>
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->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<n;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<<"刪除之後，二叉排序樹為空！"<<endl;
else
cout<<"刪除成功！"<<endl;
return r;
}
//前序輸出
void preOrder(BSTree *r)
{
if(r==NULL)
return;
else
{
cout<<r->data<<" ";
preOrder(r->left);
preOrder(r->right);
}
}
//中序輸出
void inOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
inOrder(r->left);
cout<<r->data<<" ";
inOrder(r->right);
}
}
//後續輸出
void postOrder(BSTree *r)
{
if(r==NULL)
return ;
else
{
postOrder(r->left);
postOrder(r->right);
cout<<r->data<<" ";
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int cases;
cout<<"請輸入案例個數："<<endl;
cin>>cases;
while(cases--)
{
int n;
flag = false;
BSTree *root=NULL;
cout<<"請輸入元素個數："<<endl;
cin>>n;
int i;
cout<<"請輸入這些元素："<<endl;
for(i=0;i<n;i++)
cin>>a[i];
cout<<"建立二叉排序樹!"<<endl;
root = createBSTree(root,a,n);
if(root!=NULL)
cout<<"二叉排序樹建立成功！"<<endl;
else
{
cout<<"二叉排序樹建立失敗！"<<endl;
return 0;
}
cout<<"此二叉樹根的值為："<<endl;
cout<<root->data<<endl;
cout<<"請選擇您要進行的操作："<<endl;
cout<<"1.插入(I/i)"<<endl;
cout<<"2.查找(S/s)"<<endl;
cout<<"3.刪除(D/d)"<<endl;
cout<<"4.先序輸出(P/p)"<<endl;
cout<<"5.中序輸出(M/m)"<<endl;
cout<<"6.後序輸出(L/l)"<<endl;
cout<<"7.退出(E/e)"<<endl;
char s;
cin>>s;
while(1)
{
if(s=='E'||s=='e')
break;
else if(s=='I'||s=='i')
{
cout<<"請輸入您要插入的值："<<endl;
int x;
cin>>x;
BSTree *p =(BSTree*)malloc(sizeof(BSTree));
p->data = x;
p->left = NULL;
p->right = NULL;
root = insert(root,p);
if(flag==false)
cout<<"插入成功！"<<endl;
else
{
cout<<"此二叉樹中已存在此值！"<<endl;
flag=false;//恢復原值
}
}
else if(s=='S'||s=='s')
{
cout<<"請輸入您要查找的值："<<endl;
int x;
cin>>x;
BSTree *p=search(root,x);
BSTree *pfather=getFather(root,p);
cout<<"查找的值為："<<p->data<<endl;
if(pfather!=NULL)
cout<<"其父節點的值為："<<pfather->data<<endl;
else
cout<<"它是根節點，沒有父節點！"<<endl;
if(p->left==NULL&&p->right==NULL)
cout<<"它是葉子節點，沒有子節點"<<endl;
else
{
if(p->left != NULL)
cout<<"其左兒子節點的值為："<<p->left->data<<endl;
else
cout<<"其左兒子節點為空！"<<endl;
if(p->right != NULL)
cout<<"其右兒子的值為："<<p->right->data<<endl;
else
cout<<"其右兒子節點為空！"<<endl;
}
}
else if(s=='D'||s=='d')
{
cout<<"請輸入您要刪除的節點的值："<<endl;
int value;
cin>>value;
cout<<"你確定要刪除嗎？(Yy/Nn)"<<endl;
char order;
cin>>order;
while(1)
{
if(order=='Y'||order=='y')
{
BSTree * node;
node = search(root,value);
if(node==NULL)
cout<<"該節點不存在！"<<endl;
else
BSTree *nodeDel = deleteNode(root,node);
break;
}
else if(order=='N'||order=='n')
{
break;
}
else
{
cout<<"命令不正確，請重新輸入！"<<endl;
cin>>order;
}
}
}
else if(s=='P'||s=='p')
{
cout<<"其前序輸出為："<<endl;
preOrder(root);
cout<<endl;
}
else if(s=='M'||s=='m')
{
cout<<"其中序輸出為："<<endl;
inOrder(root);
cout<<endl;
}
else if(s=='L'||s=='l')
{
cout<<"其後序輸出為："<<endl;
postOrder(root);
cout<<endl;
}
else
{
cout<<"命令有誤，請重新輸入！"<<endl;
}
cout<<"請選擇您要進行的操作："<<endl;
cin>>s;
}
}
system("pause");
return 0;
}
摘自：我和我追逐的夢
