教你利用栈非递归复制二叉树

利用栈非递归复制二叉树非递归复制二叉树#includestdio.h#includemalloc.h#defineSTACK_INIT_SIZE100#defineSTACK_INCR10typedefstructBiTNode{//二叉树节点chardata;structBiTNode*lChild,*rChild;}BiTNode,*BiTree;typedefstruct{//栈的定义BiTree*base;BiTree*top;intstackSize;}Stack;voidinitStack(Stack&stack){//初始化栈stack.base=stack.top=(BiTree*)malloc(sizeof(BiTree)*STACK_INIT_SIZE);stack.stackSize=STACK_INIT_SIZE;}voidpop(Stack&S,BiTree&T){//出栈if(S.top==S.base){T=NULL;return;}T=*--S.top;}voidpush(Stack&S,BiTree&T){//入栈if(S.top-S.base=S.stackSize){S.base=(BiTree*)realloc(S.base,(S.stackSize+STACK_INCR)*sizeof(BiTree));S.top=S.base+S.stackSize;S.stackSize+=STACK_INCR;}*S.top++=T;}boolstackEmpty(StackS){//栈是否为空returnS.top==S.base?true:false;}voidcreateBinaryTree(BiTree&T){//创建二叉树charc=getchar();if(c=='*')T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));T-data=c;createBinaryTree(T-lChild);createBinaryTree(T-rChild);}}voidinOrderTaverse(BiTreeT){//中序便利二叉树if(T){inOrderTaverse(T-lChild);printf(%c,T-data);inOrderTaverse(T-rChild);}}voidBiTreeCopy_Stack(BiTreeT,BiTree&U){//非递归复制二叉树，T复制到UStackS1,S2;initStack(S1);initStack(S2);BiTreep=T,q,pre;U=pre=(BiTree)malloc(sizeof(BiTNode));while(p||!stackEmpty(S1)){while(p){//只要左子树存在，一路往左走q=(BiTree)malloc(sizeof(BiTNode));q-data=p-data;q-lChild=q-rChild=NULL;pre-lChild=q;pre=q;push(S1,p);push(S2,q);p=p-lChild;}pop(S1,p);pop(S2,q);while(!p-rChild&&!stackEmpty(S1)){pop(S1,p);pop(S2,q);}p=p-rChild;if(p){pre=q;q=(BiTree)malloc(sizeof(BiTNode));q-data=p-data;q-lChild=q-rChild=NULL;pre-rChild=q;pre=q;push(S1,p);push(S2,q);p=p-lChild;}}pre=U;U=U-lChild;free(pre);//删除临时头结点}intmain(){BiTreeT,U;printf(先序创建二叉树，（期中\*\表示空结点）:);createBinaryTree(T);BiTreeCopy_Stack(T,U);//非递归将二叉树T复制到Uprintf(原来的二叉树的中序遍历为：);inOrderTaverse(T);printf(\n);printf(复制的二叉树的中序遍历为：);inOrderTaverse(U);printf(\n);return1;}