二叉樹5（複制二叉樹）

# include <stdio.h>

# include <stdlib.h>

typedef char ElemType;

typedef struct BiTNode{

ElemType data;

struct BiTNode* Lchild;

struct BiTNode* Rchild;

}BiTNode,*BiTree;

//構造二叉樹

void createbt(BiTree &T){

char ch;

scanf("%c",&ch);

if(ch=='#')T=NULL;

else{

T=(BiTree)malloc(sizeof(BiTNode));

T->data=ch;

createbt(T->Lchild);

createbt(T->Rchild);

}

}

//複制一棵二叉樹

BiTNode *GetTreeNode(ElemType item,BiTNode*lptr,BiTNode*rptr){

//生成一個其元素值為item,左指針為lptr，右指針為rptr的節點

BiTNode *T;

T=(BiTree)malloc(sizeof(BiTNode));

T->data=item;

T->Lchild=lptr;

T->Rchild=rptr;

return T;

}

BiTNode *CopyTree(BiTNode*T){

//已知二叉樹的根指針為T，本算法傳回他的複制品的根指針。

struct BiTNode *newlptr,*newrptr;

BiTNode *newnode;

if(!T)return NULL;

if(T->Lchild)

newlptr=CopyTree(T->Lchild);

else

newlptr=NULL;

if(T->Rchild)

newrptr=CopyTree(T->Rchild);

else

newrptr=NULL;

newnode=GetTreeNode(T->data,newlptr,newrptr);

return newnode;

}

//中序周遊

void Inorder(BiTree T){

if(T){

Inorder(T->Lchild);

printf("%c ",T->data);

Inorder(T->Rchild);

}

}

void main(){

int depth=0;

BiTree T;

BiTree T0;

printf("create a tree such as ABC##de#G##f###\n");

createbt(T);

printf("print T\n");

Inorder(T);

    T0=CopyTree(T);

printf("\nprint T0\n");

Inorder(T0);

}