#include<iostream>
#define ElemType int
#define NULLDATA -1
using namespace std;
typedef struct TREE_NODE *link;
typedef struct TREE_NODE
{
ElemType data;
link right ;
link left ;
}TREE_NODE;
link T; //全局根节点变量
void Insert(ElemType v) //插入操作
{
link current;
link *head = &T;
while((*head) != NULL)
{
if(v < (*head)->data)
head = &(*head)->left;
else
head = &(*head)->right;
}
current = (link)malloc(sizeof(TREE_NODE));
current->data = v;
current->left = NULL;
current->right = NULL;
(*head) = current;
}
ElemType Delete(link head,ElemType v)
{
link h = head; // 记录要删除的结点
link aux = head; //aux 记录要删除结点的前驱
link p ; // p 记录要替换删除结点的前驱
link ptr; // ptr记录要替换的结点
while(h->data != v)
{
aux = h;
if(v < h->data)
h = h->left;
else
h = h->right;
}
if(h->left == NULL && h->right == NULL) //第一种情况：要删除结点（叫做Ｚ，导论里的叫法）没有子女
{ cout<<"111 "<<aux->data<<endl;
if(aux->left == h)
{ aux ->left = NULL; cout<<"hhh"<<endl;}
else
{
aux->right = NULL;
cout<<"SSS"<<endl;
}
return h->data;
}
else if(h->left == NULL || h->right == NULL) // 第二种情况： Z 只有一个子女
{ cout<<"222"<<aux->data<<endl;
if(aux->left = h)
{ if(h->left != NULL)
aux->left = h->left;
if(h->right != NULL)
aux->left = h->right;
}
else
{ if(h->right != NULL)
aux->right = h->right;
if(h->left != NULL)
aux->left = h->left;
}
return h->data;
}
else //第三种情况： Z有两个子女
{ cout<<"333 h->right is"<<h->right->data<<endl;
p = h->right;
if(p->left == NULL)
{
p->left = h->left;
if(aux->left == NULL)
{ aux->right = p;
}
else
{
aux->left = p;
}
}
else
{
while(p->left->left != NULL ) //找到要替换结点的前驱
{
p = p->left;
}
ptr = p->left; // 要替换的结点
if(ptr->right != NULL)
p->right = ptr->right;
p->left = NULL;
ptr->left = h->left;
ptr->right= h->right;
aux->left = ptr;
}
return h->data;
}
}
ElemType find_1(link head,ElemType v) //查找版本1
{ link h = head;
if( h == NULL || h->data == v)
{return h->data;}
else
return NULLDATA;
if(v < h->data)
find_1(h->left,v);
else
find_1(h->right,v);
}
ElemType find_2(link head,ElemType v) //非递归版本，导论上说一般来说，非递归版本一般要比递归运行的快。
{ link h = head;
while(v != h->data && h != NULL)
{
if(v < h->data)
h = h->left;
else
h = h->right;
}
if( h != NULL)
return h->data;
else
return NULLDATA;
}
int count(link head) //统计结点个数
{
if(head == NULL) return 0;
return count(head->left) + count(head->right) +1;
}
int height(link head) //计算二叉树的高度
{
int r_h,l_h,max;
link h = head;
if(h != NULL)
{
r_h = height(h->left);
l_h = height(h->right);
max = (r_h > l_h) ? r_h:l_h;
return (max+1);
}
else
return 0;
}
ElemType out_max(link head) //输出二叉树的最大值
{ link h = head;
while(h->right != NULL)
{
h = h->right;
}
return h->data;
}
ElemType out_min(link head) //输出二叉树的最小值
{
link h = head;
while(h->left != NULL)
{
h = h->left;
}
return h->data;
}
void pre_traverse(link head) //前序遍历
{
link h = head;
if(h == NULL) return ;
cout<<h->data<<endl;
pre_traverse(h->left);
pre_traverse(h->right);
}
void post_traverse(link head) //后序遍历
{
link h = head;
if(h == NULL) return ;
post_traverse(h->left);
post_traverse(h->right);
cout<<h->data<<endl;
}
void in_traverse(link head) //中序遍历
{
link h = head;
if(h == NULL) return ;
in_traverse(h->left);
cout<<h->data<<endl;
in_traverse(h->right);
}
int main()
{
Insert(13); //一系列的插入
Insert(12);
Insert(28);
Insert(11);
Insert(33);
Insert(2);
Insert(29);
Insert(56);
Insert(10);
Insert(23);
Insert(6);
Insert(7);
Insert(53);
Insert(80);
Insert(90);
Insert(91);
cout<<"pre_traverse:"<<endl;
pre_traverse(T);
cout<<"in_traverse:"<<endl;
in_traverse(T);
cout<<"post_traverse:"<<endl;
post_traverse(T);
cout<<"The element is "<<find_1(T,18)<<endl;
cout<<"The element is "<<find_2(T,12)<<endl;
cout<<"The number of all element is "<<count(T)<<endl;
cout<<"The height of binary tree is "<<height(T)<<endl;
cout<<"----------------------------"<<endl;
cout<<"The max element is "<<out_max(T)<<endl;
cout<<"---------------------------------"<<endl;
cout<<"The min element is "<<out_min(T)<<endl;
cout<<"Delete the element is "<<Delete(T,53)<<endl;
cout<<"int_traverse after delete :"<<endl;
in_traverse(T);
return 0;
}
参考：导论 P151 ~ P157 重点是删除操作的三种情况 以及 插入操作实现和《算法：C实现》的区别。