두 갈래 찾기 트리 (아날로그 메모리)

#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
",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
", 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!
");return ;} printf("T in preorder: "); T.dfs(T.Root); printf("
"); printf("T in inorder: "); T.dfs(T.Root,1); printf("
"); printf("T in postorder: "); T.dfs(T.Root,2); printf("
"); } int main () { int m, w, n, op, data, delp; printf("***************************************************
"); printf("* Please input the number of a Binary Tree with : *
"); printf("***************************************************
"); 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:
"); scanf("%d", &n); for (int i=1; i<n; ++i) { printf("**Choose the operator: *0.insert and search *1.del *2.print
"); 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!
"); else printf("The key had already exist!
"); } else if(op==1) { printf("Please input the key:"); scanf("%d",&delp); if(delp==-1) { printf("The data is not exist!
"); } 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
",delp); delp=T.Father(0,delp); if(delp==-2)printf("It's root node!
"); else if(delp==-1)printf("Error data!
"); else printf("Father of %d is %d
",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 */

좋은 웹페이지 즐겨찾기