利用栈非递归复制二叉树
非递归复制二叉树
#include
typedef struct BiTNode { //二叉树节点
char data;
struct BiTNode *lChild, *rChild;
} BiTNode, *BiTree; typedef struct { //栈的定义
BiTree *base; BiTree *top; int stackSize;
} Stack;
void initStack(Stack &stack) { //初始化栈 }
void pop(Stack &S, BiTree &T) {//出栈 }
void push(Stack &S, BiTree &T) {//入栈 }
bool stackEmpty(Stack S) {//栈是否为空 }
void createBinaryTree(BiTree &T) {//创建二叉树
char c = getchar(); if(c == '*') T = NULL; else { }
T = (BiTree)malloc(sizeof(BiTNode)); T->data = c; createBinaryTree(T->lChild); createBinaryTree(T->rChild); return S.top == S.base ? true : false; if(S.top - S.base >= S.stackSize) { }
*S.top++ = T;
S.base=(BiTree*)realloc(S.base,(S.stackSize+STACK_INCR)*sizeof(BiTree)); S.top = S.base + S.stackSize; S.stackSize += STACK_INCR; if(S.top == S.base) { }
T = *--S.top;
T = NULL; return ;
stack.base = stack.top = (BiTree *)malloc(sizeof(BiTree) * STACK_INIT_SIZE); stack.stackSize = STACK_INIT_SIZE;
}
void inOrderTaverse(BiTree T) {//中序便利二叉树 }
void BiTreeCopy_Stack(BiTree T, BiTree &U) { //非递归复制二叉树，T复制到U }
Stack S1, S2;
initStack(S1); initStack(S2); BiTree p = T, q, pre;
U = pre = (BiTree)malloc(sizeof(BiTNode)); while(p || !stackEmpty(S1)) { } pre = U; U = U->lChild;
free(pre); //删除临时头结点
while(p) { //只要左子树存在，一路往左走 }
pop(S1, p); pop(S2, q);
while(!p->rChild && !stackEmpty(S1)) { }
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; pop(S1, p); pop(S2, q);
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;
if(T) { }
inOrderTaverse(T->lChild); printf(\inOrderTaverse(T->rChild);
int main() { }
BiTree T, U;
printf(\先序创建二叉树，（期中\\\表示空结点）:\createBinaryTree(T);
BiTreeCopy_Stack(T, U);//非递归将二叉树T复制到U printf(\原来的二叉树的中序遍历为：\inOrderTaverse(T); printf(\
printf(\复制的二叉树的中序遍历为：\inOrderTaverse(U); printf(\return 1;