数据结构cpp二叉树

using namespace std;


typedef struct btreenode
{
	char data;
	struct btreenode *lchild;
	struct btreenode *rchild;
}BTreeNode, *BTree;

typedef struct
{
	BTree link;
	int flag;
}Stack;


void InitBTree(BTree &BT)
{
	BT = NULL;
}


void CreatBTree(BTree &BT)
{
	char ch;
	ch = getchar();
	if (ch == ' ')
		BT = NULL;
	else
	{
		BT = new BTreeNode;
		BT->data = ch;
		CreatBTree(BT->lchild);
		CreatBTree(BT->rchild);
	}
}
void PreOrder(BTree BT)
{
	if (BT == NULL)
	{
		cout << "NULL";
		return;
	}
	else
	{
		cout << BT->data;
		if (BT->lchild != NULL)
			PreOrder(BT->lchild);
		if (BT->rchild != NULL)
			PreOrder(BT->rchild);
	}
}


void InOrder(BTree BT)
{
	if (BT == NULL)
	{
		cout << "NULL";
		return;
	}



	if (BT->lchild != NULL)
		InOrder(BT->lchild);


	cout << BT->data;


	if (BT->rchild != NULL)
		InOrder(BT->rchild);

}


void PostOrder(BTree BT)
{
	if (BT == NULL)
	{
		cout << "NULL";
		return;
	}


	if (BT->lchild != NULL)
		PostOrder(BT->lchild);


	if (BT->rchild != NULL)
		PostOrder(BT->rchild);


	cout << BT->data;

}


void LevelOrder(BTree BT)
{
	BTree Queue[30];
	int front, rear;
	if (BT == NULL) return;

	front = -1;
	rear = 0;
	Queue[rear] = BT;


	while (front != rear)
	{
		front++;
		cout << Queue[front]->data;
		if (Queue[front]->lchild != NULL)
		{
			rear++;
			Queue[rear] = Queue[front]->lchild;
		}


		if (Queue[front]->rchild != NULL)
		{
			rear++;
			Queue[rear] = Queue[front]->rchild;
		}
	}
}


void PreOrder_2(BTree BT)
{
	BTree stack[30], p;
	int top;
	if (BT == NULL) return;
	top = -1;
	p = BT;
	while (!(p == NULL && top == -1))
	{
		while (p != NULL)
		{
			cout << p->data;
			if (top < 30)
			{
				stack[top + 1] = p;
				top++;
			}
			else
			{
				cout << "Stack is full!" << endl;
				return;
			}
			p = p->lchild;
		}

		if (top < 0) return;
		else
		{
			top--;
			p = stack[top + 1];
			p = p->rchild;
		}
	}
}


void PostOrder_2(BTree BT)
{
	Stack s[30];
	BTree p;
	int top, sign;
	if (BT == NULL) return;
	top = -1;
	p = BT;
	while (!(p == NULL && top == -1))
	{
		if (p != NULL)
		{
			s[++top].link = p;
			s[top].flag = 1;
			p = p->lchild;
		}
		else
		{
			p = s[top].link;
			sign = s[top].flag;
			top--;
			if (sign == 1)
			{
				s[++top].link = p;
				s[top].flag = 2;
				p = p->rchild;
			}
			else
			{
				cout << p->data;
				p = NULL;
			}
		}
	}
}


void main()
{
	BTree T;
	InitBTree(T);
	cout << "InitTree completed!" << endl;
	cout << "Create Tree:" << endl;
	CreatBTree(T);
	cout << "/nPreOrder:" << endl;
	PreOrder(T);
	cout << "/nInOrder:" << endl;
	InOrder(T);
	cout << "/nPosetOrder:" << endl;
	PostOrder(T);
	cout << "/nLevelOrder:" << endl;
	LevelOrder(T);
	cout << "/nPreOrder_2:" << endl;
	PreOrder_2(T);
	cout << "/nPostOrder_2:" << endl;
	PostOrder_2(T);
	system("pause");
}