#include <iostream>
#include <stdio.h>
using namespace std;
typedef struct tree{
char data;
struct tree *lchild, *rchild;
}BitNode, *BiTree;
void creatTree(BiTree &T){
char ch;
cin >> ch;
if (ch == '#'){
T = NULL;
} else {
T = new BitNode;
T->data = ch;
creatTree(T->lchild);
creatTree(T->rchild);
}
}
void InOrderTraverse(BiTree T){
if (T){
InOrderTraverse(T->lchild);
cout << T->data;
InOrderTraverse(T->rchild);
}
}
void front(BiTree T) {
if (T){
cout << T->data;
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);
}
}
void end(BiTree T) {
if (T){
InOrderTraverse(T->lchild);
InOrderTraverse(T->rchild);
cout << T->data;
}
}
int NodeCount(BiTree T){
if (T){
return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
}
int Depth(BiTree T){
int m = 0, n = 0;
if (T){
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n){
return (m + 1);
} else {
return (n + 1);
}
}
}
int main(){
BiTree T = NULL;
creatTree(T);
cout << "================中序============"<<endl;
InOrderTraverse(T);
cout << endl;
cout << "================先序============"<<endl;
front(T);
cout << endl;
cout << "================后序============"<<endl;
end(T);
cout << endl;
cout << "================节点个数============"<<endl;
cout << NodeCount(T);
cout << endl;
cout << "================数的深度============"<<endl;
cout << Depth(T);
}