【C++】 二叉树的基本知识及其遍历

二叉树：每个节点最多两个孩子节点。

二叉树的结构：         struct TreeNode

                      {  

                          DataType _value;     //节点值

                          TreeNode*  _left;    //左孩子

                          TreeNode*  _ridht;   //右孩子

                      };

二叉树的基础：        构造、拷贝构造、析构、赋值运算符的重载

二叉树的知识点：      高度、节点的个数、子节点的个数

二叉树的遍历：        前序、中序、后序遍历(递归及非递归)

遍历顺序：            前序——根左右          中序——左根右          后序——左右根

注意: 递归遍历时，应该注意不要出现栈溢出现象。

      因为++index返回对象，index++返回临时变量，所以传引用做参数时有++index。

#pragma once

#include<queue>
#include<stack>

//二叉树的结构
template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;
	//构造函数
	BinaryTreeNode(const T& x)
		:_left(NULL)
		, _right(NULL)
		, _data(x)
	{}
};
template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;  

public:
	//构造
	BinaryTree()
		:_root(NULL)
	{}
	// a--树的节点前序遍历的数组  size--数组中元素个数  invaild--无效值即节点为空
	BinaryTree(const T* a,size_t size,const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size,invalid,index);
	}
	//析构
	~BinaryTree()
	{
		_Destory(_root);
		_root = NULL;
	}
	//拷贝  
	BinaryTree(const BinaryTree<T>& t)
	{
		_root = _Copy(t._root);
	}
    //赋值重载(传统)
	//BinaryTree<T>& operator=(const BinaryTree<T>& t)
	//{
	//	if (this != &t)
	//	{
	//		Node* tmp = _Copy(t._root);
	//		_Destory(_root);
	//		_root = tmp;
	//	}
	//	return *this;
	//}
	//赋值重载(现代)
	BinaryTree<T>& operator=(BinaryTree<T> t)
	{
		swap(_root, t._root);
		return *this;
	}

	T& operator->()
	{
		return _root;
	}

public:
	void PrevOrder()//前序
	{
		_PrevOrder(_root);
		cout << endl;
	}
	void InOrder()//中序
	{
		_InOrder(_root);
		cout << endl;
	}
	void PostOrder()//后序
	{
		_PostOrder(_root);
		cout << endl;
	}

	size_t Size()  //节点个数
	{
		return _Size(_root);
	}
	size_t Depth()  //树的深度
	{
		return _Depth(_root);
	}
	size_t LeafSize()  //叶子节点个数
	{
		return _LeafSize(_root);
	}
	
	//层次遍历
	void LevelOrder()
	{
		queue<Node*> q;
		if (_root)
		{
			q.push(_root);
		}
		while (!q.empty())
		{
			Node* front = q.front();
			cout << front->_data << " ";
			q.pop();

			if (front->_left)
			{
				q.push(front->_left);
			}
			if (front->_right)
			{
				q.push(front->_right);
			}
		}
		cout << endl;
	}
public:
	//非递归的前中后序遍历（栈）
	void PrevOrder_NonR()
	{
		stack<Node*> s;
		if (_root)
			s.push(_root);
		while (!s.empty())
		{
			Node* top = s.top();
			cout << top->_data << " ";
			s.pop();
			//栈后进先出  ，所以 右先进，左先出
			if (top->_right)
				s.push(top->_right);
			if (top->_left)
				s.push(top->_left);
		}
		cout << endl;
	}
	void InOrder_NonR()
	{
		//压左树
		//取出一个节点即它的左路走完了，在访问右树（看作子问题）
		stack<Node*> s;
		Node* cur = _root;
		while (cur || !s.empty())
		{
			//压树的左路节点直至最左段节点
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			if (!s.empty())
			{
				Node* top = s.top();
				s.pop();
				cout << top->_data << " ";
				cur=top->_right;
			}
		}
		cout << endl;

	}

	void PostOrder_NonR()
	{
		Node* prev = NULL;
		Node* cur = _root;
		stack<Node*> s;
		while (cur || !s.empty())
		{
			//压树的左路节点直至最左段节点
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();
			if (top->_right == NULL || top->_right == prev)
			{
				cout << top->_data << " ";
				s.pop();
				prev = top;
			}
			else
			{
				cur = top->_right;
			}
		}
		cout << endl;
	}


protected:
        //注意 此处index要用引用传参
	Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) 
	{
		Node* root = NULL;
		if ((index < size) && (a[index] != invalid))
		{
			root = new Node(a[index]);
		
                        //注意下面只能用++index。此处传的是引用 
                       //因为++index返回对象，index++返回临时变量。
			root->_left = _CreateTree(a, size, invalid, ++index);
			root->_right = _CreateTree(a, size, invalid, ++index);
                 }
		return root;
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
			return;
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	Node* _Copy(Node* root)
	{
		if (root == NULL)
			return NULL;
		NOde* newRoot = new Node(root->_data);
		newRoot->_left = _Copy(root->_left);
		newRoot->_right = _Copy(root->_right);
		return newRoot;
	}
        //////////////
	void _PrevOrder(Node* root)
	{
		if (root == NULL)
			return;

		cout << root->_data << " ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}
	void _PostOrder(Node* root)
	{
		if (root == NULL)
			return;

		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout << root->_data << " ";
	}

	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;
		return (_Size(root->_left) + _Size(root->_right) + 1);
	}
	size_t _Depth(Node* root)
	{
		if (root == NULL)
			return 0;
		size_t LeftDepth = _Depth(root->_left);
		size_t RightDepth = _Depth(root->_right);

		return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 1);
	}

	size_t _LeafSize(Node* root)
	{
		if (root == NULL)
			return 0;
		if ((root->_left == NULL) && (root->_right == NULL))
			return 1;
		return (_LeafSize(root->_left) + _LeafSize(root->_right));
	}
private:
	Node *_root;
};