学步园

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cstring>

using namespace std;

class Node{
public:
    int l, r, data;
};

class BTree{
    int curcnt;
public:
    Node* p;
    int Root;
    BTree(int SZ=100){p=new Node[SZ]; curcnt=Root=0; memset(p, -1, sizeof(Node)*SZ);}
    BTree(int SZ, int d)
    {p=new Node[SZ]; curcnt=Root=0;
                               memset(p, -1, sizeof(Node)*SZ); p[curcnt++].data=d;}
    ~BTree(){delete []p;}
    void insert(int , int);
    void dfs(int, int);//1 preorder 2 inorder 3 postorder
    int search(int, int);
    int Father(int, int);
    void del(int);
    void Del(int);
};

int BTree::Father(int t,int f)
{
	int q;
	//printf("%d %d\n",t,f);
	if(f==Root)return -2;
	if(f==-1 || t==-1)return -1;
	if(p[t].l==f || p[t].r==f)return t;
	if(~(q=Father(p[t].l, f)))return q;
	return Father(p[t].r, f);
}

int  BTree::search (int key, int father)
{
	int tt;
	if(father==-1)return -1;
	if(p[father].data==key)return father;
	if(~(tt=search(key,p[father].l)))return tt;
	return search(key,p[father].r);
	//if(key)
}

void BTree::insert (int n,int root)
{
    if(p[root].data<n)//ÓÒ×ÓÊ÷
    {
        if(~p[root].r)
            insert(n,p[root].r);
        else
            p[root].r=curcnt, p[curcnt++].data=n;
    }
    else
    {
        if(~p[root].l)
            insert(n,p[root].l);
        else
            p[root].l=curcnt, p[curcnt++].data=n;
    }
}

void BTree::dfs(int root,int flag=0)
{
    if(flag)
    {
        if(~p[root].l)dfs(p[root].l,flag);
        if(flag==1)
        {
            if(~p[root].data)printf("%d ",p[root].data);
            if(~p[root].r)dfs(p[root].r,flag);
        }
        else if(flag==2)
        {
            if(~p[root].r)dfs(p[root].r,flag);
            if(~p[root].data)printf("%d ",p[root].data);
        }
    }
    else
    {
        if(~p[root].data)printf("%d ",p[root].data);
        if(~p[root].l)dfs(p[root].l);
        if(~p[root].r)dfs(p[root].r);
    }
}

void BTree::del(int rt)
{
    if(~rt)
    {
		//printf("%d %d %d\n", p[rt].l, p[rt].r, p[rt].data);
		del(p[rt].l);
		del(p[rt].r);
		p[rt].l=-1;
		p[rt].r=-1;
		p[rt].data=-1;
	}
}

void BTree::Del(int q)
{
    if(q==-1)return ;
    int t=q;
    if(p[t].r==-1)t=p[t].l;// right is null ,set left in right
    else // right is not null
    {
        int rr=p[t].r;
        if(p[rr].l==-1)// left of right is null
        {
            p[rr].l=p[q].l;
            t=rr;
        }
        else
        {
            int s=p[rr].l;
            while (~p[s].l)
            {
                rr=s;
                s=p[rr].l;
            }
            p[s].l=p[t].l;
            p[rr].l=p[s].l;
            p[s].l=p[t].l;
            t=s;
        }
    }
    if(q==Root)Root=t;
    else
    {
        int f=Father(Root,q);
        if(p[f].l==q)p[f].l=t;
        else p[f].r=t;
        p[q].data=-1;
        p[q].l=-1;
        p[q].r=-1;
    }
}

void out (BTree &T)
{
	if(T.p[0].data==-1){printf("T is empty!\n");return ;}
    printf("T in preorder:  "); T.dfs(T.Root); printf("\n");
    printf("T in inorder:   "); T.dfs(T.Root,1); printf("\n");
    printf("T in postorder: "); T.dfs(T.Root,2); printf("\n");
}

int main ()
{
    int m, w, n, op, data, delp;
    printf("***************************************************\n");
    printf("* Please input the number of a Binary Tree with : *\n");
    printf("***************************************************\n");
    while (~scanf("%d",&m))
    {
        int w;
        scanf("%d", &w);
        BTree T(m*2,w);
        for (int i=1; i<m; ++i)
        {
            scanf("%d",&w);
            T.insert(w, T.Root);
        }
        out(T);
        printf("Please input the number of operators you will take:\n");
        scanf("%d", &n);
        for (int i=1; i<n; ++i)
        {
            printf("**Choose the operator: *0.insert and search  *1.del  *2.print\n");
            scanf("%d",&op);
            if(op==0)
            {
				printf("Please input the key:");
				scanf("%d",&data);
				delp=T.search(data,T.Root);
				if(delp==-1)T.insert(data,T.Root),printf("Insert new key!\n");
				else printf("The key had already exist!\n");
			}
			else if(op==1)
			{
				printf("Please input the key:");
				scanf("%d",&delp);
				if(delp==-1)
				{
				    printf("The data is not exist!\n");
				}
				delp=T.search(delp,T.Root);
				T.Del(delp);
			}
			else if(op==2)
			{
				out(T);
			}
			/*
			else if(op==3)
			{
				printf("Please input the key:");
				scanf("%d",&data);
				delp=T.search(data,0);
				//printf("%d\n",delp);
				delp=T.Father(0,delp);
				if(delp==-2)printf("It's root node!\n");
				else if(delp==-1)printf("Error data!\n");
				else printf("Father of %d is %d\n",data,T.p[delp].data);
			}*/
			else printf("Error input!");
        }
    }
    system("puase");
    return 0;
}
/*
15
16 12 13 18 20 11 9 8 6 1 2 5 3 4 7
100

5
2 5 4 3 1

*/