Binary Tree

今天写二叉树快写吐了，要写递归和非递归的版本 不是很明白为什么二叉树要非递归 老师上课说，递归其实时间特别长 好吧，反正上课一顿骚操作愣是看懵了 最后是参考的腾讯云上的这篇文章看了个大概

最终代码如下

#include <iostream>
#include <queue>
#include <stack>
using namespace std;

typedef int DataType;

class BinaryTree
{
public:
	DataType data;
	BinaryTree *leftChild;
	BinaryTree *rightChild;
	BinaryTree()
	{
		leftChild = nullptr;
		rightChild = nullptr;
	}
	BinaryTree(DataType e)
	{
		data = e;
		leftChild = nullptr;
		rightChild = nullptr;
	}
};

class BT
{
private:
	BinaryTree *root;
public:
	BT()
	{
		root = nullptr;
		create();

		// pre visit
		cout << "===============================" << endl;
		preOrderNonRecursive();
		cout << "preOrderRecursive" << endl;
		preOrderRecursive(root);

		// index visit
		cout << "===============================" << endl;
		indexOrderNonRecursive();
		cout << "indexOrderRecursive" << endl;
		indexOrderRecursive(root);

		// post visit
		cout << "===============================" << endl;
		postOrderNonRecursive();
		cout << "postOrderRecursive" << endl;
		postOrderRecursive(root);

		// bf
		cout << "===============================" << endl;
		cout << "bf" << endl;
		bf();
	}
	BinaryTree* create();

	void preOrderNonRecursive();
	void preOrderRecursive(BinaryTree *p);
	void indexOrderNonRecursive();
	void indexOrderRecursive(BinaryTree *p);
	void postOrderNonRecursive();
	void postOrderRecursive(BinaryTree *p);

	void bf();
};

BinaryTree* BT::create()
{
	int data;
	cout << "data: ";
	cin >> data;
	if (data < 0)
	{
		cout << "minux error" << endl;
		return nullptr;
	}
	if (!root)
	{
		root = new BinaryTree(data);
		root->leftChild = create();
		root->rightChild = create();
		return root;
	}
	else
	{
		BinaryTree *p = new BinaryTree(data);
		p->leftChild = create();
		p->rightChild = create();
		return p;
	}
}

void BT::preOrderNonRecursive()
{
	cout << "preOrderNonRecursive" << endl;
	if (!root)
	{
		cout << "empty tree" << endl;
		return;
	}
	stack<BinaryTree *> preStack;
	preStack.push(root);
	BinaryTree *cur = nullptr;
	while (!preStack.empty())
	{
		cur = preStack.top();
		cout << cur->data << endl;
		preStack.pop();
		if (cur->rightChild)	// left output first so push right first
		{
			preStack.push(cur->rightChild);
		}
		if (cur->leftChild)
		{
			preStack.push(cur->leftChild);
		}
	}
}

void BT::preOrderRecursive(BinaryTree *p)
{
	if (!root)
	{
		cout << "empty tree" << endl;
	}
	else if (!p)
	{
		return;
	}
	else
	{
		cout << p->data << endl;
		preOrderRecursive(p->leftChild);
		preOrderRecursive(p->rightChild);
	}
}

void BT::indexOrderNonRecursive()
{
	cout << "indexOrderNonRecursive" << endl;
	if (!root)
	{
		cout << "empty tree" << endl;
		return;
	}
	stack<BinaryTree *> indexStack;
	BinaryTree *cur = root;
	while (!indexStack.empty() || cur)
	{
		while (cur)
		{
			indexStack.push(cur);
			cur = cur->leftChild;
		}
		cur = indexStack.top();
		cout << cur->data << endl;
		indexStack.pop();
		cur = cur->rightChild;
	}
}

void BT::indexOrderRecursive(BinaryTree *p)
{
	if (!root)
	{
		cout << "empty tree" << endl;
	}
	else if (!p)
	{
		return;
	}
	else
	{
		indexOrderRecursive(p->leftChild);
		cout << p->data << endl;
		indexOrderRecursive(p->rightChild);
	}
}

void BT::postOrderNonRecursive()
{
	cout << "postOrderNonRecursive" << endl;
	if (!root)
	{
		cout << "empty tree" << endl;
		return;
	}
	stack<BinaryTree *> postStack;
	BinaryTree *cur, *pre = nullptr;
	postStack.push(root);
	while (!postStack.empty())
	{
		cur = postStack.top();
		if ((!cur->leftChild && !cur->rightChild) || (pre && (pre == cur->leftChild || pre == cur->rightChild)))
		{
			cout << cur->data << endl;
			postStack.pop();
			pre = cur;
		}
		else
		{
			if (cur->rightChild)
				postStack.push(cur->rightChild);
			if (cur->leftChild)
				postStack.push(cur->leftChild);
		}
	}
}

void BT::postOrderRecursive(BinaryTree *p)
{
	if (!root)
	{
		cout << "empty tree" << endl;
	}
	else if (!p)
	{
		return;
	}
	else
	{
		postOrderRecursive(p->leftChild);
		postOrderRecursive(p->rightChild);
		cout << p->data << endl;
	}
}

void BT::bf()
{
	if (!root)
	{
		cout << "empty tree" << endl;
		return;
	}
	queue<BinaryTree *> bfQ;
	bfQ.push(root);
	while (!bfQ.empty())
	{
		BinaryTree *cur = bfQ.front();
		cout << cur->data << endl;
		bfQ.pop();
		if (cur->leftChild)
			bfQ.push(cur->leftChild);
		if (cur->rightChild)
			bfQ.push(cur->rightChild);
	}
}

int main(int argc, const char *argv[])
{
	BT bt;

	return 0;
}