#include "Btree.h"
#include<queue>
#include<stack>
void Btree::buildtree(int a[],int n) {
	if (n == 0) {
		return;
	}
	root = new BNode(a[0]);
	for (int i = 1;i < n;i++) {
		BNode* newnode = new BNode(a[i]);
		BNode* node = root;
		while (1) {
			if (newnode->val < node->val) {
				if (node->left == NULL) {
					node->left = newnode;
					break;
				}
				else {
					node = node->left;
				}
			}
			else {
				if (node->right == NULL) {
					node->right = newnode;
					break;
				}
				else {
					node = node->right;
				}
			}
		}
	}
}



 BNode* Btree::getroot() {
	return root;
}

  void Btree::bianli(BNode* root) {
	 if (root == NULL) {
		 return;
	 }
	 if (root) {
		 bianli(root->left);
		 std::cout << root->val << "\t";
		 bianli(root->right);
	 }
	 
 }
  void Btree::cengxu(BNode* root) {
	  if (root == NULL) {
		  return;
	  }
	  BNode* last = root;
	  BNode* nlast = NULL;
	  std::queue<BNode *>que;
	  que.push(root);
	  while (! que.empty()) {
		  BNode* front = que.front();
		  std::cout << front->val << "\t";
		  que.pop();
		  if (front->left) {
			  que.push(front->left);
			  nlast = front->left;

		  }
		  if (front->right) {
			  que.push(front->right);
			  nlast = front->right;
		  }
		  if (front == last) {
			  std::cout << std::endl;
			  last = nlast;
		  }

	  }

  }
  void Btree::preOrder(BNode* root) {
	  //非递归方式实现先序遍历
	  if (root == nullptr) {
		  return;
	  }
	  std::stack<BNode *>stk;
	  stk.push(root);
	  while (!stk.empty()) {
		  BNode *node = stk.top();
		  stk.pop();
		  std::cout << node->val;
		  if (node->right) {
			  stk.push(node->right);
		  }
		  if (node->left) {
			  stk.push(node->left);
		  }
	  }

  }
  void Btree::inOrder(BNode* root) {
	  //非递归方式实现中序遍历
	  if (root == nullptr) {
		  return;
	  }
	  BNode* cur = root;
	  std::stack<BNode*> stk;
	  while (!stk.empty() || cur) {
		  while (cur) {
			  stk.push(cur);
			  cur = cur->left;
		  }
		  BNode* node = stk.top();
		  stk.pop();
		  std::cout << node->val<<" ";
		  cur = node->right;

	  }

  }

  void Btree::postOrder(BNode* root) {
	  //非递归方式实现后序遍历
	  if (root == nullptr) {
		  return;
	  }
	  std::stack<BNode*> stk;
	  std::stack<BNode*> res;
	  stk.push(root);
	  while (!stk.empty()) {
		  BNode* node = stk.top();
		  stk.pop();
		  res.push(node);
		  if (node->left) {
			  stk.push(node->left);
		  }
		  if (node->right) {
			  stk.push(node->right);
		  }

	  }
	  while (!res.empty()) {
		  std::cout << res.top()->val;
	  }
  }