【代碼】C++實(shí)現(xiàn)二叉樹(shù)基本操作及測(cè)試用例-創(chuàng)新互聯(lián)

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

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

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

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

   層序遍歷

   不同于其他的遍歷方式，層序遍歷是以根節(jié)點(diǎn)為開(kāi)始，依次向下，每層從左到右依次訪問(wè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)//通過(guò)先序的字符串構(gòu)造二插樹(shù)‘#’為空
	{
		_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()//求二叉樹(shù)的大小
	{
		return _Size(_root);
	}
	size_t Depth()//求深度
	{
		return _Depth(_root);
	}
	void LevelOrder()//層序遍歷二叉樹(shù)
	{
		queue<_NODE*> NodeQueue;
		_NODE* cur = _root;
		NodeQueue.push(cur);
		while (!NodeQueue.empty())
		{
			_NODE*tmp = NodeQueue.front();//取隊(duì)頭
				cout << tmp->_data << " ";//訪問(wèn)
			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)//壓一顆樹(shù)的左子樹(shù)，直到最左
		{
			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)訪問(wèn)過(guò)的節(jié)點(diǎn)，則不彈出棧頂節(jié)點(diǎn)
			{
				visitor(top);
				prev = top;//將最后一次訪問(wèn)過(guò)得節(jié)點(diǎn)保存
				s.pop();
			}
			else//否則壓入以棧頂節(jié)的右節(jié)點(diǎn)點(diǎn)為根的左子樹(shù)，直到最左
			{
				cur = top->_rightChild;
			}
		}
	}
	void InOrder_NONREC()//中序非遞歸遍歷
	{
		stack<_NODE*> s;
		_NODE*cur = _root;
		while (!s.empty() || cur)
		{
			while (cur)//壓一棵樹(shù)的左節(jié)點(diǎn)直到最左，若為空則不進(jìn)行壓棧
			{
				s.push(cur);
				cur = cur->_leftChild;
			}
			_NODE* top = s.top();
			if (!s.empty())//訪問(wèn)棧頂節(jié)點(diǎn)，將另一顆被壓的樹(shù)，置為棧頂節(jié)點(diǎn)的右子樹(shù)
			{
				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();//先訪問(wèn)當(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)//訪問(wèn)函數(shù)，為了滿足測(cè)試，控制臺(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;
};

   如有不足或疑問(wèn)希望指正。

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

分享標(biāo)題：【代碼】C++實(shí)現(xiàn)二叉樹(shù)基本操作及測(cè)試用例-創(chuàng)新互聯(lián)
當(dāng)前地址：http://www.muchs.cn/article46/ipihg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開(kāi)發(fā)、手機(jī)網(wǎng)站建設(shè)、域名注冊(cè)、網(wǎng)站營(yíng)銷、品牌網(wǎng)站制作、Google

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

網(wǎng)站托管運(yùn)營(yíng)