【代碼】C++實(shí)現(xiàn)二叉樹基本操作及測試用例

    二叉樹是一種常見的數(shù)據(jù)結(jié)構(gòu)，這里我們需要要注意的是，二叉樹的非遞歸的遍歷。

    先序遍歷，中序遍歷，后序遍歷

    這三種遍歷，如果用非遞歸的方式實(shí)現(xiàn)，我們則需要借助棧這個(gè)結(jié)構(gòu)，首先我們需要遍歷所有左子樹的左節(jié)點(diǎn)。進(jìn)行壓棧，完成壓棧之后，根據(jù)不同的需求，判斷是否該繼續(xù)訪問或者彈出亦或者是壓入該節(jié)點(diǎn)的右子樹。

    層序遍歷

    不同于其他的遍歷方式，層序遍歷是以根節(jié)點(diǎn)為開始，依次向下，每層從左到右依次訪問。

    這里我們需要借助與隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)，層層入隊(duì)，層層出隊(duì)，完成遍歷。

代碼如下：

#pragma once
#include<iostream>
using namespace std;
#include<queue>
#include<stack>
typedef  char DataType;
struct BinaryTreeNode//節(jié)點(diǎn)結(jié)構(gòu)體
{
	BinaryTreeNode(DataType data = (DataType)0)
	:_data(data)
	, _leftChild(NULL)
	, _rightChild(NULL)
	{}
	DataType _data;
	BinaryTreeNode* _leftChild;
	BinaryTreeNode* _rightChild;
};
class BinaryTree
{
	typedef BinaryTreeNode _NODE;
public:
	BinaryTree(char* str)//通過先序的字符串構(gòu)造二插樹‘#’為空
	{
		_root = _CreatTree(_root,str);
	}
	BinaryTree(const BinaryTree &t)
	{
		_root = _Copy(t._root);
	}
	BinaryTree operator =(BinaryTree t)
	{
		swap(_root, t._root);
		return *this;
	}
	~BinaryTree()
	{
		_Destory(_root);
	}
	size_t Size()//求二叉樹的大小
	{
		return _Size(_root);
	}
	size_t Depth()//求深度
	{
		return _Depth(_root);
	}
	void LevelOrder()//層序遍歷二叉樹
	{
		queue<_NODE*> NodeQueue;
		_NODE* cur = _root;
		NodeQueue.push(cur);
		while (!NodeQueue.empty())
		{
			_NODE*tmp = NodeQueue.front();//取隊(duì)頭
				cout << tmp->_data << " ";//訪問
			NodeQueue.pop();
			if (tmp->_leftChild)//左不為空入左，右不為空入右
				NodeQueue.push(tmp->_leftChild);
			if (tmp->_rightChild)
				NodeQueue.push(tmp->_rightChild);
		}
	}
	void BackOrder_NONREC()//后續(xù)非遞歸遍歷
	{
		stack<_NODE*> s;
		_NODE*prev = NULL;
		_NODE*cur = _root;
		while (!s.empty()||cur)//壓一顆樹的左子樹，直到最左
		{
			while (cur)
			{
				s.push(cur);

				cur = cur->_leftChild;
			}
			_NODE* top = s.top();
			if (top->_rightChild==NULL||top->_rightChild==prev)//若棧頂節(jié)點(diǎn)的右節(jié)點(diǎn)為空，或者是已經(jīng)訪問過的節(jié)點(diǎn)，則不彈出棧頂節(jié)點(diǎn)
			{
				visitor(top);
				prev = top;//將最后一次訪問過得節(jié)點(diǎn)保存
				s.pop();
			}
			else//否則壓入以棧頂節(jié)的右節(jié)點(diǎn)點(diǎn)為根的左子樹，直到最左
			{
				cur = top->_rightChild;
			}
		}
	}
	void InOrder_NONREC()//中序非遞歸遍歷
	{
		stack<_NODE*> s;
		_NODE*cur = _root;
		while (!s.empty() || cur)
		{
			while (cur)//壓一棵樹的左節(jié)點(diǎn)直到最左，若為空則不進(jìn)行壓棧
			{
				s.push(cur);
				cur = cur->_leftChild;
			}
			_NODE* top = s.top();
			if (!s.empty())//訪問棧頂節(jié)點(diǎn)，將另一顆被壓的樹，置為棧頂節(jié)點(diǎn)的右子樹
			{
				visitor(top);
				s.pop();
				cur = top->_rightChild;
			}
		}
	}
	void PrevOrder_NONREC()//先序非遞歸遍歷
	{
		stack<_NODE*> s;
		_NODE* cur = NULL;
		s.push(_root);
		while (!s.empty())
		{
			cur = s.top();//先訪問當(dāng)前節(jié)點(diǎn)
			visitor(cur);
			s.pop();
			if (cur->_rightChild)//當(dāng)前右節(jié)點(diǎn)不為空壓入
				s.push(cur->_rightChild);
			if (cur->_leftChild)
				s.push(cur->_leftChild);
		}
		cout << endl;
	}
protected:
	static void visitor(_NODE* cur)//訪問函數(shù)，為了滿足測試，控制臺(tái)打印數(shù)據(jù)
	{
		cout << cur->_data << " ";
	}
	_NODE* _Copy(_NODE* root)
	{
		_NODE* newRoot = NULL;
		if (root == NULL)
			return NULL;
		else
		{
			newRoot = new _NODE(root->_data);
			newRoot->_leftChild = _Copy(root->_leftChild);
			newRoot->_rightChild = _Copy(root->_rightChild);
		}
		return newRoot;
	}
	size_t _Depth(_NODE* root)
	{
		size_t depth = 0;
		if (root == NULL)
			return depth;
		else
		{
			depth = _Depth(root->_leftChild) + 1;
			size_t newdepth = _Depth(root->_rightChild) + 1;
			depth = depth > newdepth ? depth : newdepth;
		}
		return depth;
	}
	size_t _Size(_NODE* root)
	{
		if (root==NULL)
			return 0;
		else
			return _Size(root->_leftChild) + _Size(root->_rightChild) + 1;

	}
	void _Destory(_NODE* &root)
	{
		if (root)
		{
			if ((root->_leftChild == NULL)
				&&(root->_rightChild == NULL))
			{
				delete root;
				root = NULL;
			}
			else
			{
				_Destory(root->_leftChild);
				_Destory(root->_rightChild);
				_Destory(root);
			}
		}
	}
	_NODE*_CreatTree(_NODE* root,char* &str)
	{
		_NODE*cur = root;
		if (*str == '#' ||
			*str == 0)

		{
			return NULL;
		}
		else
		{
			cur = new _NODE(*str);
			cur->_leftChild = _CreatTree(cur->_leftChild, ++str);
			cur->_rightChild = _CreatTree(cur->_rightChild,++str);
		}
		return cur;
	}
protected:
	_NODE* _root;
};

    如有不足或疑問希望指正。