#include <iostream>
using namespace std;
typedef struct BSTnode // typedef定义类型的别名
{
int data;
struct BSTnode *LeftChild,*RightChild,*Parent;
BSTnode(int e,BSTnode *L,BSTnode *R,BSTnode *P):data(e),LeftChild(L),RightChild(R),Parent(P){}
}BSTnode;
int index=0;//定义全局索引变量
/*
class BSTree
{
private:
public:
BSTnode* GetRoot(BSTnode *root){return root;}
BSTnode* Search(BSTnode *root,int key);
BSTnode* Minimun(BSTnode *root);
BSTnode* Maxmun(BSTnode *root);
BSTnode* Delete(BSTnode *root,int key);
BSTnode* Insert(BSTnode *root,int e);
void InorderTreeWalk(BSTnode *node);
BSTnode* Transplant(BSTnode *root,BSTnode *u,BSTnode *v);
};
*/
BSTnode* Search(BSTnode* root,int key)
{
BSTnode *p=root;
while(p&&p->data!=key)
{
if(key<p->data) p=p->LeftChild;
else p=p->RightChild;
}
return p;
}
BSTnode* Minimun(BSTnode *root)
{
BSTnode *p=root;
while(p->LeftChild)
p=p->LeftChild;
return p;
}
BSTnode* Maxmun(BSTnode *root)
{
BSTnode *p=root;
while(p->RightChild)
p=p->RightChild;
return p;
}
BSTnode* Insert(BSTnode *root,int e)
{
BSTnode *p=root,*pp=NULL;//p搜索指针,pp是p的父节点
if(NULL==p)
{
root= new BSTnode(e, NULL, NULL, NULL);//注意这个指针参数是引用
return root;
}
else{
while(p)
{
pp=p;
if(e<=p->data)p=p->LeftChild;
else if(e>p->data)p=p->RightChild;
}
BSTnode *r=new BSTnode(e,NULL,NULL,NULL);
r->Parent=pp;
if(e<=pp->data) pp->LeftChild=r;
else pp->RightChild=r;
//return this;
return root;
}
}
BSTnode* Transplant(BSTnode *root,BSTnode *u,BSTnode *v)
{
if(!u->Parent){ root=v; return root; }
else if(u==(u->Parent)->LeftChild) { (u->Parent)->LeftChild=v; if(v) v->Parent=u->Parent; return root; }
else { (u->Parent)->RightChild=v; if(v) v->Parent=u->Parent; return root;}
}
BSTnode* Delete(BSTnode *root,int key)
{
BSTnode *z=Search(root,key);
if(!z->LeftChild){ root=Transplant(root,z,z->RightChild); delete z; return root; }
else if(!z->RightChild) { root = Transplant(root,z,z->LeftChild); delete z; return root;}
else{
BSTnode *y;
y=z->RightChild;
while(y->LeftChild) {y=y->LeftChild;}
if(y->Parent!=z)
{
root = Transplant(root,y,y->RightChild);
y->RightChild=z->RightChild;
(y->RightChild)->Parent=y;
}
root = Transplant(root,z,y);
y->LeftChild=z->LeftChild;
(y->LeftChild)->Parent=y;
delete z;
return root;
}
}
void InorderTreeWalk(BSTnode *node)
{
if(node)
{
InorderTreeWalk(node->LeftChild);
cout<<node->data<<" ";
InorderTreeWalk(node->RightChild);
}
}
int main()
{
//BSTree *TestTree;
BSTnode *root;
root=NULL;
int num,e;
cin>>num;
while(num--)
{
cin>>e;
root=Insert(root,e);
}
cout<<"root->data="<<(root->data)<<endl;
cout<<"创建二叉搜索(排序)树完毕,中序遍历输出为:"<<endl;
InorderTreeWalk(root);
cout<<endl<<"请输入要插入的数"<<endl;
cin>>e;
root = Insert(root,e);
cout<<endl<<"插入新元素后的二叉搜索树"<<endl;
InorderTreeWalk(root);
cout<<endl<<"输入你选择删除的数"<<endl;
cin>>e;
root = Delete(root,e);
cout<<endl<<"删除该元素后的二叉搜索树"<<endl;
InorderTreeWalk(root);
cout<<endl<<"输入要查找的数,系统找到则输出:"<<endl;
cin>>e;
BSTnode *p=Search(root,e);
if (p) cout<<p->data<<endl;// 后面这些可能不存在<<(p->Parent)->data<<(p->LeftChild)->data<<" "<<(p->RightChild)->data<<endl;
else cout<<"没有找到该数"<<endl;
system("pause");
return 0;
}
/*
#include <stdio.h>
//#include <iostream>
#include <string.h>
//using namespace std;
typedef struct student
{
int age;
char name[20];
} stud;
int main()
{
stud st;
stud *p;
p=&st;
p->age=15;//不能不声明对象就直接对指针进行操作,比如没有stud st,就直接进行stud *p;p->age=15;因为次数p不指向任何内存位置,会发生错误
strcpy(p->name,"zhangsan");
printf("%d\n%s\n",p->age,p->name);
//cout<<p->name<<endl<<p->age<<endl;
getchar();
//system("pause");
return 0;
}
*/