使用栈非递归实现复制二叉树

#include "iostream"
using namespace std;
#define max 20  //the number of node
typedef struct BTNode
{
	char data;
	struct BTNode *lc,*rc;
}BTree;

#define STACK_INIT_SIZE 100
#define STACK_INCR 10

typedef struct 
{ 
	BTree *base;
	BTree *top;
	int stackSize;
} Stack;

void initStack(Stack &stack)   //初始化栈
{ 
	stack.base = stack.top = (BTree *)malloc(sizeof(BTree) * STACK_INIT_SIZE);
	stack.stackSize = STACK_INIT_SIZE;
}

void pop(Stack &S, BTree * &T)  //出栈
{
	if(S.top == S.base) 
	{
		T = NULL;
		return ;
	}
	T = --S.top;
}

void push(Stack &S, BTree * &T)   //进栈
{
	if(S.top - S.base >= S.stackSize) 
	{
		S.base=(BTree*)realloc(S.base,(S.stackSize+STACK_INCR)*sizeof(BTree));
		S.top = S.base + S.stackSize;
		S.stackSize += STACK_INCR;
	}
	*S.top++ = *T;
}

bool stackEmpty(Stack S)   //判断栈是否为空
{
	return S.top == S.base ? true : false;
}

BTree *createtree(char *str,int i,int m)  //创建树
{
	BTree *p;
	if(i >= m)
		return 0;
	p = (BTree*)malloc(sizeof(BTree));
	p->data = str[i];
	p->lc = createtree(str,2*i+1,m);
	p->rc = createtree(str,2*i+2,m);
	return (p);
}

void PreOrder(BTree *t)  //树的先序遍历
{
	if(t != NULL)
	{
		cout<<t->data;
		if(t->lc)
		{
			cout<<"->";
			PreOrder(t->lc);
		}
		if(t->rc)
		{
			cout<<"->";
			PreOrder(t->rc);
		}
	}
}

void BiTreeCopy_Stack(BTree *root, BTree * ©root) //非递归复制二叉树，将root复制到copyroot
{ 
	/*指针与引用的区别
	指针：存放变量地址的一个变量，逻辑上是独立的，它可以被改变。
	引用：是一个别名，逻辑上不是独立的，它的存在具有依附性，必须在一开始就被初始化，且"从一而终"
	*/
	Stack S1, S2;
	initStack(S1); //初始化栈
	initStack(S2);

	BTree *p = root;
	BTree *q, *pre;  //q用来每次创建新结点； pre为临时根结点

	copyroot = pre = (BTree*)malloc(sizeof(BTree));

	while(p||!stackEmpty(S1)) //如果当前结点有左孩子，则一直向左走
	{
		while(p) 
		{ 
			q = (BTree*)malloc(sizeof(BTree));
			q->data = p->data;
			q->lc = q->rc = NULL;
			pre->lc = q;
			pre = q;
			push(S1, p);
			push(S2, q);
			p = p->lc;
		}

		pop(S1, p); //指针移到栈中最后一个元素
		pop(S2, q);

		while(!p->rc && !stackEmpty(S1))  //如果当前结点的右孩子为空，则栈中存放的左孩子全部出栈
		{
			pop(S1, p); 
			pop(S2, q);
		}

		p = p->rc; //p指向root中第一个有右孩子的结点
		q = q->rc;

		if(p) //对右子树进行操作
		{
			q = (BTree*)malloc(sizeof(BTree));
			q->data = p->data;
			q->lc = q->rc = NULL;
			pre->rc = q;
			pre = q;
			push(S1, p);
			push(S2, q);
			p = p->lc;
		}
	}
	pre = copyroot; //使临时根结点重新指回根结点
	copyroot = copyroot->lc;
	free(pre);   //释放指临时根结点
}

int main()
{
	int i,n;
	char str[max];
	BTree *root,*copyroot;

	cout<<"please input the number of node:";
	cin>>n;
	cout<<endl;

	cout<<"please input "<<n<<" nodes:";
	for(i = 0;i < n;i++)
		cin>>str[i];

	root = createtree(str,0,n); 
	cout<<"the PreOrder:";
	PreOrder(root);
	cout<<endl;

	BiTreeCopy_Stack(root, copyroot);
	cout<<"after the copy the PreOrder:";
	PreOrder(copyroot);
	cout<<endl;

	system("pause");
	return 0;
}