두 갈래 찾기 트리 (아날로그 메모리)
#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
*/
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
언제가 아닌가프로그래밍 언어에서 null 참조가 수십억 달러의 실수라는 말을 이미 들었을 것입니다. Java의 유명하고 두려운 NullPointerException은 여러분이 알고 있거나 C의 분할 오류일 수 있습니다. 모든 상...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.