二叉树的构造与遍历

为什么需要遍历二叉树？二叉树是非线性数据结构，通过遍历可以将二叉树中的结点访问一次且仅一次，从而得到访问结点的顺序序列。从这个意义上说，遍历操作就是将二叉树中的结点按一定规律线性化的操作，目的在于将非线性化数据结构变成可线性化的访问序列。二叉树的遍历操作是二叉树中最基本的运算。

#PRagma once#define _CRT_SECURE_NO_WARNINGS 1#include<iostream>#include<queue>#include<stack>using namespace std;template<class T>struct BinaryTreeNode{	BinaryTreeNode(const T& data = T())	:_data(data)	, _pLeftChild(NULL)	, _pRightChild(NULL)	{}	T _data;	BinaryTreeNode<T>* _pLeftChild;	BinaryTreeNode<T>* _pRightChild;};template<class T>class BinaryTree{public:	BinaryTree()		:_pRoot(NULL)	{}	BinaryTree(const T array[], size_t size)		:_pRoot(NULL)	{		size_t index = 0;		_CreatBinaryTree(_pRoot, array, size, index);	}	BinaryTree(BinaryTree<T>& tree)	{		_pRoot = _CopyBinartTree(tree._pRoot);	}	BinaryTree<T>& Operator=(BinaryTree<T>& tree)	{		if (this != &tree)		{			this->~BinaryTree();			_pRoot = _CopyBinartTree(tree._pRoot);		}		return *this;	}	void PreOrder()	{		_PreOreder(_pRoot);	}	void InOrder()	{		_InOrder(_pRoot);	}	void PostOrder()	{		_PostOrder(_pRoot);	}	~BinaryTree()	{		_DestoryBinaryTree(_pRoot);	}private:	void _CreatBinaryTree(BinaryTreeNode<T>*& pRoot, const T array[], size_t size, size_t& index)//构造二叉树	{		if (index < size && '#' != array[index])		{			pRoot = new BinaryTreeNode<T>(array[index]);			_CreatBinaryTree(pRoot->_pLeftChild, array, size, ++index);			_CreatBinaryTree(pRoot->_pRightChild, array, size, ++index);		}	}	BinaryTreeNode<T>*& _CopyBinartTree(BinaryTreeNode<T>*& pRoot)//拷贝二叉树	{		if (pRoot)		{			BinaryTreeNode<T>* pNewRoot = new BinaryTreeNode<T>(pRoot->_data);			pNewRoot->_pLeftChild = _CopyBinartTree(pRoot->_pLeftChild);			pNewRoot->_pRightChild = _CopyBinartTree(pRoot->_pRightChild);			return pNewRoot;		}		else			return _pRoot;	}	void _DestoryBinaryTree(BinaryTreeNode<T>*& pRoot)//销毁二叉树	{		if (pRoot)		{			_DestoryBinaryTree(pRoot->_pLeftChild);			_DestoryBinaryTree(pRoot->_pRightChild);			delete pRoot;			pRoot = NULL;		}	}	void _PreOreder(BinaryTreeNode<T>* proot) //前序遍历	{		if (proot)		{			cout << proot->_data << " ";			_PreOreder(proot->_pLeftChild);			_PreOreder(proot->_pRightChild);		}	}	void _InOrder(BinaryTreeNode<T>* proot) //中序遍历	{		if (proot)		{			_InOrder(proot->_pLeftChild);			cout << proot->_data << " ";			_InOrder(proot->_pRightChild);		}	}	void _PostOrder(BinaryTreeNode<T>* proot)  //后续遍历	{		if (proot)		{			_PostOrder(proot->_pLeftChild);			_PostOrder(proot->_pRightChild);			cout << proot->_data << " ";		}	}	void LevelOrder()//层序遍历	{		if (NULL == _pRoot)			return;		queue<BinaryTreeNode<T>*>q;		q.push(_pRoot);		while (!q.empty())		{			BinaryTreeNode<T>*pCur = q.front();			cout << pCur->_data << " ";			if (pCur->_pLeftChild)				q.push(pCur->_pLeftChild);			if (pCur->_pRightChild)				q.push(pCur->_pRightChild);			q.pop();		}	}public:	void _PreOrder_Nor()//前序遍历--非递归	{		if (NULL == _pRoot)			return;		stack<BinaryTreeNode<T>*> s;		s.push(_pRoot);		while (!s.empty())		{			BinaryTreeNode<T>*pTop = s.top();			cout << pTop->_data <<" ";			s.pop();			if (pTop->_pRightChild)				s.push(pTop->_pRightChild);			if (pTop->_pLeftChild)				s.push(pTop->_pLeftChild);					}		cout << endl;	}	void _InOrder_Nor()//中序遍历--非递归	{		if (NULL == _pRoot)			return;		stack<BinaryTreeNode<T>*> s;		BinaryTreeNode<T>* pCur = _pRoot;		while (pCur != NULL || !s.empty())		{			//找最左边节点			while (pCur)			{				s.push(pCur);				pCur = pCur->_pLeftChild;			}			BinaryTreeNode<T>* pTop = s.top();			cout << pTop->_data << " ";			s.pop();			pCur = pTop->_pRightChild;		}		cout << endl;	}	void _PostOrder_Nor()//后序遍历--非递归	{		if (NULL == _pRoot)			return;		stack<BinaryTreeNode<T>*> s;		BinaryTreeNode<T>* pCur = _pRoot;		BinaryTreeNode<T>* prev = NULL;//最近访问过的节点		while (pCur != NULL || !s.empty())		{			//找最左边节点			while (pCur)			{				s.push(pCur);				pCur = pCur->_pLeftChild;			}			BinaryTreeNode<T>* pTop = s.top();			if (pTop->_pRightChild == NULL || pTop->_pRightChild == prev)			{				cout << pTop->_data << " ";				prev = pTop;				s.pop();			}			else			{				pCur = pTop->_pRightChild;			}		}	}	BinaryTreeNode<T>* GetLeftChild(BinaryTreeNode<T>*pCur)	{		return (NULL == pCur) ? NULL : pCur->_pLeftChild;	}	BinaryTreeNode<T>* GetRightChild(BinaryTreeNode<T>*pCur)	{		return (NULL == pCur) ? NULL : pCur->_pRightChild;	}	BinaryTreeNode<T>* GetParent(BinaryTreeNode<T>*pCur)	{		return _GetParent(_pRoot, pCur);	}	BinaryTreeNode<T>*Find(const T& data)	{		return _Find(_pRoot,data);	}	size_t Height()	{		return _Height(_pRoot);	}	size_t GetLeefNode()	{		return _GetLeefNode(_pRoot);	}	size_t GetKLeveNode(size_t k)//求第k层节点数	{		return _GetKLeveNode(_pRoot,k);	}	bool IsNodeInTree(BinaryTreeNode<T>*pNode)//判断节点在不在树中	{		return _IsNodeInTree(_pRoot,pNode);	}	BinaryTreeNode<T>* GetCommonAncestor(BinaryTreeNode<T>*x1, BinaryTreeNode<T>*x2, stack<BinaryTreeNode<T>*>&s)	{		return  _GetCommonAncestor(_pRoot,x1,x2);		}	bool GetNodePath(BinaryTreeNode<T>*pNode, stack<BinaryTreeNode<T>*>&s)	{		return _GetNodePath(_pRoot,pNode,s);	}		BinaryTree<T>ReBuildBinaryTree(T pre[],size_t preSize,T in[],size_t inSize)	{		_ReBuildBinaryTree(_pRoot,pre,preSize,in,0,inSize);	}private:	BinaryTreeNode<T>* _GetParent(BinaryTreeNode<T>*pRoot,BinaryTreeNode<T>*pCur)//获取该结点的父亲结点	{		if (NULL == pRoot || NULL == pCur)			return NULL;		if (pCur == pRoot)			return NULL;		if (pRoot->_pLeftChild == pCur || pRoot->_pRightChild == pCur)			return pRoot;		BinaryTreeNode<T>* parent;		if (parent = _GetParent(pRoot->_pLeftChild, pCur))			return parent;		return _GetParent(pRoot->_pRightChild, pCur);	}	BinaryTreeNode<T>*_Find(BinaryTreeNode<T>*pRoot,const T&data)//查找值为data的结点	{		if (NULL == pRoot)			return NULL;		if (pRoot->_data == data)			return pRoot;		BinaryTreeNode<T>* ret;		if (ret = _Find(pRoot->_pLeftChild, data))			return ret;		return _Find(pRoot->_pRightChild, data);	}	size_t _Height(BinaryTreeNode<T>*pRoot)//求树的高度	{		if (NULL == pRoot)			return 0;		if (NULL == pRoot->_pLeftChild&&NULL == pRoot->_pRightChild)			return 1;		size_t _leftHeight = _Height(pRoot->_pLeftChild);		size_t _rightHeight = _Height(pRoot->_pRightChild);		return (_leftHeight > _rightHeight) ? (_leftHeight + 1) : (_rightHeight + 1);	}	size_t _GetLeefNode(BinaryTreeNode<T>* pRoot)//求叶子节点数	{		if (pRoot == NULL)			return 0;		if (pRoot->_pLeftChild == NULL && pRoot->_pRightChild == NULL)			return 1;		return _GetLeefNode(pRoot->_pLeftChild) + _GetLeefNode(pRoot->_pRightChild);	}	size_t _GetKLeveNode(BinaryTreeNode<T>*pRoot, size_t k)//第k层的节点数	{		if (NULL == pRoot || k<1 || k>Height())			return 0;		if (1 == k)			return 1;		return _GetKLeveNode(pRoot->_pLeftChild, k - 1) + _GetKLeveNode(pRoot->_pRightChild, k - 1);	}	bool _IsNodeInTree(BinaryTreeNode<T>*pRoot,BinaryTreeNode<T>*pNode)	{		if (NULL == pRoot || NULL == pNode)		{			return false;		}		if (pRoot == pNode)		{			return true;		}		if (_IsNodeInTree(pRoot->_pLeftChild, pNode) || _IsNodeInTree(pRoot->_pRightChild, pNode))		{			return true;		}		 return false;	}	BinaryTreeNode<T>* _GetCommonAncestor(BinaryTreeNode<T>*pRoot,BinaryTreeNode<T>*x1, BinaryTreeNode<T>*x2)//获取最近的祖先节点	{		if (NULL == pRoot || x1 == pRoot || x2 == pRoot)			return NULL;		if (!_IsNodeInTree(pRoot, x1) || !_IsNodeInTree(pRoot, x2))			return NULL;		bool x1InLeft = _IsNodeInTree(pRoot->_pLeftChild, x1);		bool x1InRight = _IsNodeInTree(pRoot->_pRightChild, x1);		bool x2InLeft = _IsNodeInTree(pRoot->_pLeftChild, x2);		bool x2InRight = _IsNodeInTree(pRoot->_pRightChild, x2);		if ((x1InLeft && x2InRight) || (x1InRight && x2InLeft))			return pRoot;		if ((x1InLeft && x2InLeft))			return _GetCommonAncestor(pRoot->_pLeftChild,x1,x2);		if ((x1InRight && x2InRight))			return _GetCommonAncestor(pRoot->_pRightChild, x1, x2);	}	bool _GetNodePath(BinaryTreeNode<T>*pRoot,BinaryTreeNode<T>*pNode, stack<BinaryTreeNode<T>*>&s)	{		if (NULL == pRoot)			return false;		if (pRoot == pNode)			return true;		s.push(pRoot);		if (pRoot->_pLeftChild &&  _GetNodePath(pRoot->_pLeftChild, pNode, s))			return true;		if (pRoot->_pRightChild && _GetNodePath(pRoot->_pRightChild, pNode, s))			return true;		s.pop();		return false;	}	void _ReBuildBinaryTree(BinaryTreeNode<T>*&pRoot, T pre[],size_t& index ,size_t preSize, T in[], size_t left, size_t right)	{		if (left >= right || preSize != (right - left))			return;		//在中序中找index的元素		size_t  idx = left;		while (idx < left)		{			if (pre[index] == in[idx])				break;			idx++;		}		if (idx == right)			return ;		pRoot = BinaryTreeNode<T>(pre[index]);		//创建根的左子树		_ReBuildBinaryTree(pRoot->_pLeftChild, pre, ++index, preSize, in, left, idx);		//创建根的右子树		_ReBuildBinaryTree(pRoot->_pRightChild, pre, ++index, preSize, in, idx+1, right);	}private:	BinaryTreeNode<T>* _pRoot;};void Test(){	char *pTreeInfo = "abd###ce##f";	BinaryTree<char> tree(pTreeInfo, strlen(pTreeInfo));	BinaryTree<char> t1(tree);	BinaryTree<char> t2;	t2 = tree;	BinaryTreeNode<char>* pCur = tree.Find('e');	BinaryTreeNode<char>* parent=tree.GetParent(pCur);	size_t size = tree.GetLeefNode();	//cout<<tree.GetCommonAncestor(tree.Find('b'), tree.Find('d'))->_data << endl;	//cout << size << endl;	//size = tree.GetKLeveNode(2);	//cout << size << endl;	//cout << tree.IsNodeInTree(tree.Find('e')) << endl;	tree._PreOrder_Nor();	//tree.PreOrder(); cout << endl;	//tree.InOrder(); cout << endl;	//tree.PostOrder();	//tree._InOrder_Nor();	//tree._PostOrder_Nor();}int main(){	Test();	system("pause");	return 0;}