#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cstring>
using namespace std;
struct point
{
string str;
int lson, rson;
}p[1000005];
vector<int> aa[1000005];
int sum;
int ans;
void create(int x,int y)
{
string str;
cin >> str;
if (y % 2 == 0)
{
if (str <= "Z"&&str >= "A")
{
sum++;
aa[x].push_back(y);
p[x].lson = y;
p[y].str = str;
create(y, y*2);
create(y, y*2+1);
}
else
{
p[x].lson = -1;
return;
}
}
else
{
if (str <= "Z"&&str >= "A")
{
sum++;
aa[x].push_back(y);
p[x].rson = y;
p[y].str = str;
create(y, y*2);
create(y, y*2+1);
}
else
{
p[x].rson = -1;
return;
}
}
}
void PreOrder(int x)
{
if (x != 1)
cout <<"->"<< p[x].str;
if (p[x].lson != -1)
PreOrder(p[x].lson);
if (p[x].rson != -1)
PreOrder(p[x].rson);
}
void InOrder(int x)
{
if (p[x].str == "")
{
return;
}
InOrder(p[x].lson);
if (ans == sum-1)
cout << p[x].str << endl;
else
{
ans++;
cout << p[x].str << "->";
}
InOrder(p[x].rson);
}
void PostOrder(int x)
{
if (p[x].str == "")
{
return;
}
PostOrder(p[x].lson);
PostOrder(p[x].rson);
if (ans == sum - 1)
cout << p[x].str << endl;
else
{
ans++;
cout << p[x].str << "->";
}
}
void CheckHeight(int x,int y)
{
int i;
for (i = 0; i < aa[x].size(); i++)
{
int k = aa[x][i];
if (p[k].lson == -1 && p[k].rson==-1)
{
ans = max(y+1, ans);
}
else
{
CheckHeight(k, y + 1);
}
}
}
void CheckSon()
{
int i, summ;
summ = 0;
for (i = 1; i <= 1000005; i++)
{
if (p[i].lson == -1 && p[i].rson == -1 && p[i].str <= "Z"&&p[i].str >= "A")
summ++;
}
cout << "子节点个数是:" << endl;
cout << summ << endl;
}
int main()
{
sum = 0;
string str;
int x;
cout << "A-Z表示元素,'0'表示空元素" << endl;
cout << "输入元素" << endl;
while (true)
{
cout << "请输入根节点" << endl;
cin >> str;
if (str <= "Z"&&str >= "A")
{
p[1].str = str;
create(1,2);
create(1,3);
break;
}
}
sum++;
//cout << sum << endl;
while (true)
{
ans = 0;
cout << "-----------------------------------------------------------------" << endl;
cout << "选择遍历树的顺序:" << endl;
cout << "先序输入1，中序输入2，后序输入3,查询深度输入4,查询子节点个数请输入5" << endl;
cin >> x;
if (x == 1)
{
cout << p[1].str;
PreOrder(1);
cout << endl;
}
else if (x == 2)
{
InOrder(1);
cout << endl;
}
else if (x == 3)
{
PostOrder(1);
cout << endl;
}
else if (x == 4)
{
CheckHeight(1, 1);
cout << "该树的深度为:" << endl;
cout << ans << endl;
}
else if (x == 5)
CheckSon();
else
cout << "输入不符合要求,请重新输入" << endl;
cout << "-----------------------------------------------------------------" << endl;
}
return 0;
}
/*
A B D G 0 0 0 E 0 H 0 0 C F 0 0 0
A
<- ->
B C
<- -> <-
D E F
<- ->
G H
先序:A->B->D->G->E->H->C->F
中序:G->D->B->E->H->A->F->C
后序:G->D->H->E->B->F->C->A
深度:4
查询子节点个数:3
A
C<-
D<- ->B
H<- ->E
K<- ->L
N<-
A C D H K 0 0 L N 0 0 0 0 B 0 E 0 0 0
先序:A->C->D->H->K->L->N->B->E
中序:K->H->N->L->D->C->B->E->A
后序:K->N->L->H->D->E->B->C->A
深度:6
查询子节点个数:3
*/
