#include <stdio.h>
#include <stdlib.h>
#include "二叉树.h"

/*
  根据广义表创建二叉树
  广义表用如下字符数组表示
  (A(B(,E(H,)),C(F,G)))

 */
BTree initBTreeByGeneralizedTables(DataType tables[]) {
	BTree root = NULL;
	BTreeNode *tempNode = NULL;
	char flag; // l: next左孩子 r: next是右孩子
	int i=0;
	BTreeNodeStack *stack = initBTreeNodeStack();
	while(tables[i] != '\0') {
		switch(tables[i]) {
			// 将上一个创建的节点入栈, 并标记下一个要创建的是上一个节点的左孩子
			case '(':
				if(tempNode != NULL) {
					pushBTreeNodeStack(stack, tempNode);
				}
				flag = 'l';
				break;
			// 弹栈
			case ')':
				popBTreeNodeStack(stack); // 栈空返回NULL
				break;
			// 标记下一个要创建的是上一个节点的右孩子
			case ',':
				flag = 'r';
				break;
			// 字符
			default:
				tempNode = malloc(sizeof(BTreeNode));
				tempNode->data = tables[i];
				tempNode->lchild = tempNode->rchild = NULL;
				if(root == NULL) {
					root = tempNode;
				}
				// 栈非空代表节点有双亲
				if(!emptyBTreeNodeStack(stack)) {
					if(flag == 'l') {
						topBTreeNodeStack(stack)->lchild = tempNode;
					}else if (flag == 'r'){
						topBTreeNodeStack(stack)->rchild = tempNode;
					}
				}
				break;
		};
		i++;
	}
	free(stack);
	return root;
}


void printTables(DataType tables[]) {
	int i=0;
	while(tables[i] != '\0') {
		printf("%c", tables[i]);
		i++;
	}
	printf("\n");
}

int main29() {
	/*
	BTree btree;

	//(A(B(,E(H,)),C(F,G)))
	DataType tables[] = {'(', 'A', '(', 'B', '(', ',', 'E', '(', 'H', ',', ')', ')', ',', 'C', '(', 'F', ',', 'G', ')', ')', ')', '\0'};
	printTables(tables);
	
	// 根据广义表初始化二叉树
	btree = initBTreeByGeneralizedTables(tables);

	// 先序遍历二叉树；应该打印出：A B E H C F G
	precedenceForeachBTree(btree);
	printf("\n");

	// 中序遍历二叉树；应该打印出：B H E A F C G
	middleForeachBTree(btree);
	printf("\n");

	// 后序遍历二叉树；应该打印出：H E B F G C A
	postForeachBTree(btree);
	printf("\n");
	*/

		
	BTree btree;

	//(A(B(,D(E,F)),C))
	DataType tables[] = {'(', 'A', '(', 'B', '(', ',', 'D', '(', 'E', ',', 'F', ')', ')', ',', 'C', ')', ')', '\0'};
	printTables(tables);
	
	// 根据广义表初始化二叉树
	btree = initBTreeByGeneralizedTables(tables);

	// 先序遍历二叉树；应该打印出：A B D E F C
	precedenceForeachBTree(btree);
	printf("\n");

	// 中序遍历二叉树；应该打印出：B E D F A C
	middleForeachBTree(btree);
	printf("\n");

	// 后序遍历二叉树；应该打印出：E F D B C A
	postForeachBTree(btree);
	printf("\n");


	/* test stack!
	BTreeNodeStack *stack = initBTreeNodeStack();
	BTreeNode *n1 = malloc(sizeof(BTreeNode)),*n2 = malloc(sizeof(BTreeNode)),
		*n3 = malloc(sizeof(BTreeNode));
	n1->data = 'A';
	n2->data = 'B';
	n3->data = 'C';
	pushBTreeNodeStack(stack, n1);
	pushBTreeNodeStack(stack, n2);
	pushBTreeNodeStack(stack, n3);
	
	printBTreeNodeStack(stack);

	printf("pop stack: %c \n", popBTreeNodeStack(stack)->data);
	printBTreeNodeStack(stack);

	printf("pop stack: %c \n", popBTreeNodeStack(stack)->data);
	printBTreeNodeStack(stack);

	printf("top stack: %c \n", topBTreeNodeStack(stack)->data);
	printBTreeNodeStack(stack);

  */
	return 0;
}