/*
构建二叉树、输出二叉树、求树深、复制二叉树 7
*/
#include<stdio.h>
#include<stdlib.h>
typedef int DataType;
typedef struct BinTreeNode *PBinTreeNode;
typedef struct BinTreeNode{
DataType info;
PBinTreeNode lchild;
PBinTreeNode rchild;
}*BinTree;
int h,depth;
BinTree Create();
void print(BinTree t);
int Depth(BinTree t,int h,int depth);
BinTree GetBinTreeNode(DataType info,struct BinTreeNode lptr,struct BinTreeNode rptr);
BinTree CopyTree(BinTree t);
int main()
{
h = 1;
depth = 1;
BinTree t,copyt;
t = Create();
print(t);
printf("\n");
depth = Depth(t,h,depth);
copyt = CopyTree(t);
print(copyt);
printf("\n%d\n",depth);
system("PAUSE");
return 0;
}
BinTree Create()
{
BinTree t;
DataType data;
if(scanf("%c",&data) && data == '#')
t = NULL;
else{
t = (BinTree)malloc(sizeof(struct BinTreeNode));
t->info = data;
t->lchild = Create();
t->rchild = Create();
}
return t;
}
void print(BinTree t)
{
if(t){
printf("%c",t->info);
print(t->lchild);
print(t->rchild);
}
}
int Depth(BinTree t,int h,int depth)
{
int a,b;
if(t){
if(h > depth)depth = h;
a = Depth(t->lchild,h + 1,depth);
b = Depth(t->rchild,h + 1,depth);
depth = (a > b)? a:b;
}
return depth;
}
BinTree GetBinTreeNode(DataType info,PBinTreeNode lptr,PBinTreeNode rptr)
{
BinTree newtnode;
newtnode = (BinTree)malloc(sizeof(struct BinTreeNode));
newtnode->info = info;
newtnode->lchild = lptr;
newtnode->rchild = rptr;
return newtnode;
}
BinTree CopyTree(BinTree t)
{
BinTree newtnode;
BinTree newlptr,newrptr;
newlptr = (BinTree)malloc(sizeof(struct BinTreeNode));
newrptr = (BinTree)malloc(sizeof(struct BinTreeNode));
if(!t)return NULL;
else{
if(t->lchild)newlptr = CopyTree(t->lchild);
else newlptr = NULL;
if(t->rchild)newrptr = CopyTree(t->rchild);
else newrptr = NULL;
newtnode = GetBinTreeNode(t->info,newlptr,newrptr);
return newtnode;
}
}
/*
Inout
abdh###e##cf##g##
*/