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

成都創(chuàng)新互聯(lián)公司主要從事網(wǎng)頁設(shè)計(jì)、PC網(wǎng)站建設(shè)（電腦版網(wǎng)站建設(shè)）、wap網(wǎng)站建設(shè)（手機(jī)版網(wǎng)站建設(shè)）、成都響應(yīng)式網(wǎng)站建設(shè)公司、程序開發(fā)、網(wǎng)站優(yōu)化、微網(wǎng)站、微信平臺小程序開發(fā)等，憑借多年來在互聯(lián)網(wǎng)的打拼，我們在互聯(lián)網(wǎng)網(wǎng)站建設(shè)行業(yè)積累了豐富的成都網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、網(wǎng)站設(shè)計(jì)、網(wǎng)絡(luò)營銷經(jīng)驗(yàn)，集策劃、開發(fā)、設(shè)計(jì)、營銷、管理等多方位專業(yè)化運(yùn)作于一體。

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

   這三種遍歷，如果用非遞歸的方式實(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
using namespace std;
#include
#include
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ù)，為了滿足測試，控制臺打印數(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;
};

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

創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。

名稱欄目：【代碼】C++實(shí)現(xiàn)二叉樹基本操作及測試用例-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/ipihg.html