typedef struct Node {
	char data;
	struct Node * leftChild;
	struct Node * rightChild;
} Node;

Node * preCreateBt(Node *);
void preOrderTransverse(Node*);
void inOrderTransverse(Node*);
void postOrderTransverse(Node*);
int getLeafNumber(Node*);
int getNumber(Node*);
int getHigh(Node*);
bool findData(Node*, char);
void inOrderByStack(Node *);

int main(void)// ABEH###C#D##MN###
{
	Node * btn = NULL;
	btn = preCreateBt(btn);

	printf("前序递归遍历:");
	preOrderTransverse(btn);
	putchar('\n');

	printf("中序递归遍历:");
	inOrderTransverse(btn);
	putchar('\n');

	printf("后序递归遍历:");
	postOrderTransverse(btn);
	putchar('\n');

	printf("叶子个数：%d\n", getLeafNumber(btn));
	printf("节点总个数：%d\n", getNumber(btn));
	printf("树的高度：%d\n", getHigh(btn));
	printf(findData(btn, 'Z') ? "查找成功\n" : "查找失败\n");

	cout << "中序非递归遍历：";
	inOrderByStack(btn);
	return 0;
}

void inOrderByStack(Node * root) {
	// 创建栈
	stack<Node> stack ;
	Node * current = root;
	while (current != NULL || !stack.empty()) {
		while (current != NULL) {
			stack.push(*current);
			current = current->leftChild;
		}

		if (!stack.empty()) {
			current = &stack.top();
			stack.pop();
			cout << current->data <<  " ";
			current = current->rightChild;
		}
	}
	cout << endl;
}

bool findData(Node * root, char ch) {
	if (root == NULL) {
		return 0;
	}
	if (root->data == ch) {
		return 1;
	}
	return findData(root->leftChild, ch) + findData(root->rightChild, ch);
}

int getHigh(Node* root) {
	if (root == NULL) {
		return 0;
	}
	int nLeft = getHigh(root->leftChild);
	int nright = getHigh(root->rightChild);
	return nLeft > nright ? nLeft + 1 : nright + 1;
}

int getNumber(Node * root) {
	if (root == NULL) {
		return 0;
	}
	return getNumber(root->leftChild) + getNumber(root->rightChild) + 1;
}

int getLeafNumber(Node* root) {
	if (root == NULL) {
		return 0;
	}
	if (root->leftChild == NULL && root->rightChild == NULL) {
		return 1;
	}
	return getLeafNumber(root->leftChild) + getLeafNumber(root->rightChild);
}

void postOrderTransverse(Node * root) {
	if (root != NULL) {
		postOrderTransverse(root->leftChild);
		postOrderTransverse(root->rightChild);
		printf("%c ", root->data);
	}
}

void inOrderTransverse(Node * root) {
	if (root != NULL) {
		inOrderTransverse(root->leftChild);
		printf("%c ", root->data);
		inOrderTransverse(root->rightChild);
	}
}

void preOrderTransverse(Node * root) {
	if (root != NULL) {
		printf("%c ", root->data);
		preOrderTransverse(root->leftChild);
		preOrderTransverse(root->rightChild);
	}
}


Node * preCreateBt(Node * root) {
	char ch = getchar();
	if (ch == '#') {
		root = NULL;
	}
	else {
		root = (Node *)malloc(sizeof(Node));
		root->data = ch;
		root->leftChild = preCreateBt(root->leftChild);
		root->rightChild = preCreateBt(root->rightChild);
	}
	return root;
}