數(shù)據(jù)結(jié)構(gòu)--二叉樹(shù)(1)-創(chuàng)新互聯(lián)

二叉樹(shù)

創(chuàng)新互聯(lián)是網(wǎng)站建設(shè)專(zhuān)家,致力于互聯(lián)網(wǎng)品牌建設(shè)與網(wǎng)絡(luò)營(yíng)銷(xiāo)，專(zhuān)業(yè)領(lǐng)域包括成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站、電商網(wǎng)站制作開(kāi)發(fā)、微信平臺(tái)小程序開(kāi)發(fā)、微信營(yíng)銷(xiāo)、系統(tǒng)平臺(tái)開(kāi)發(fā)，與其他網(wǎng)站設(shè)計(jì)及系統(tǒng)開(kāi)發(fā)公司不同，我們的整合解決方案結(jié)合了恒基網(wǎng)絡(luò)品牌建設(shè)經(jīng)驗(yàn)和互聯(lián)網(wǎng)整合營(yíng)銷(xiāo)的理念，并將策略和執(zhí)行緊密結(jié)合，且不斷評(píng)估并優(yōu)化我們的方案，為客戶(hù)提供全方位的互聯(lián)網(wǎng)品牌整合方案！

構(gòu)建：二叉樹(shù)的構(gòu)建采用的是先序遍歷，->先儲(chǔ)存根節(jié)點(diǎn)然后左右節(jié)點(diǎn)，用遞歸的思想將所有數(shù)據(jù)放在樹(shù)中。

代碼實(shí)現(xiàn)：實(shí)現(xiàn)了4種訪問(wèn)方法，先序，中序，后序，和層序的訪問(wèn)方法都采用遞歸的方式。

#include<iostream>
#include<queue>
#include<stack>
using namespace std;

template<class T> 
struct rootnode
{
	T _value;
	rootnode<T> *_leftnode;
	rootnode<T> *_rightnode;
	rootnode<T>(T value)
		: _value(value),
		_leftnode(NULL),
		_rightnode(NULL)
	{}
};

template <class T>
class BinaryTree
{
public:
	BinaryTree<T>( T *str)
	{
		T *tmp = str;
		_root = _BinaryTree(tmp);
	}
	~BinaryTree()
	{
		_Clear(_root);
	}
	BinaryTree<T> (BinaryTree &t)
	{
		_root=_Copy(t._root);
	}
	BinaryTree<T>& operator=(BinaryTree t)
	{
		if (*this != t)
		{
			swap(_root, t._root);
		}
	}
	void Fastorder()
	{
		_Fastorder(_root);
	}
	void Inorder()
	{
		_Inorder(_root);
	}
	void Postorder()
	{
		_Postorder(_root);
	}
	void Levelorder()
	{
		queue<rootnode<T>*> q;
			if (_root == NULL)
			{
				return;
			}
			q.push(_root);
			while (!q.empty())
			{
				rootnode<T>* root = q.front();
				cout << root->_value;
				q.pop();
				if (root->_leftnode != NULL)
				{
					q.push(root->_leftnode);
				}
				if (root->_rightnode != NULL)
				{
					q.push(root->_rightnode);
				}
			}	
	}
	int leafnum()
	{
		int num = 0;
		num=_Leafnum(_root,num);
		return num;
	}
	int Size()
	{
		int size = 0;
		_Size(_root,size);
		return size;
	}
	int Depth()
	{
		int Depth = _Depth(_root);
		return Depth;
	}
	void NRfastorder()
	{
		stack<rootnode<T>*> s;
		if (_root != NULL)
		{
			s.push(_root);
		}
		while (!s.empty())
		{
			rootnode<T>* front=s.top();
			cout<<front->_value;
			s.pop();
			if (front->_rightnode != NULL)
			{
				s.push(front->_rightnode);
			}
			if (front->_leftnode != NULL)
			{
				s.push(front->_leftnode);
			}
		}
	}
	void NRinorder()
	{
		stack<rootnode<T>*>s;
		rootnode<T>*cur = _root;
		rootnode<T>* top = NULL;
		while (cur||!s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_leftnode;
			}			
			if (top != s.top()->_rightnode)
			{
				top = s.top();
				cout << top->_value;
				s.pop();
				cur = top->_rightnode;
			}
			else
			{
				top = s.top();
				cout << top->_value;
				s.pop();
			}

		}
	}

	void NRpostorder()
	{
		rootnode<T>*cur = _root;
		stack<rootnode<T>*> s;
		rootnode<T>*top = NULL;
		while (cur || !s.empty())
		{
			while (cur)
			{
				s.push(cur);
				cur = cur->_leftnode;
			}
			if (s.top()->_rightnode != NULL&&top != s.top()->_rightnode)
			{

				top = s.top();
				cur = top->_rightnode;
			
			}
			else
			{
				top = s.top();
				s.pop();
				cout << top->_value;
			}
		

		}
	}
protected:
	rootnode<T>* _BinaryTree(T *&str)
	{
		rootnode<T> *root = NULL;
		if (*str != '#'&&*str != '\0')
		{
			root = new rootnode<T>(*str);
			str++;
			root->_leftnode = _BinaryTree(str);
			str++;
			root->_rightnode = _BinaryTree(str);
		}
		return root;
	}
	void _Fastorder(rootnode<T> *&root)
	{
		if (root == NULL)
		{
			
			return;
		}
		else
		{
			cout << root->_value;
			_Fastorder(root->_leftnode);
			_Fastorder(root->_rightnode);
			
		}
	}
	void _Inorder(rootnode<T> *root)
	{
		if (root == NULL)
		{
			return;
		}
		_Inorder(root->_leftnode);
		cout << root->_value;
		_Inorder(root->_rightnode);
	}

	void _Postorder(rootnode<T> *root)
	{
		if (root == NULL)
		{
			return;
		}
		_Postorder(root->_leftnode);
		_Postorder(root->_rightnode);
		cout << root->_value;
	}
	void _Clear(rootnode<T> *root)
	{
		if (root == NULL)
		{
			return;
		}
		rootnode<T> *tmp = root->_leftnode;
		rootnode<T> *tmp2 = root->_rightnode;
		delete root;
		_Clear(tmp);
		_Clear(tmp2);
	}
	rootnode<T>* _Copy(rootnode<T> *root)
	{
		rootnode<T> *newroot = NULL;
		if (root == NULL)
		{
			return newroot;
		}
		newroot = new rootnode<T>(root->_value);
		newroot->_leftnode = _Copy(root->_leftnode);
		newroot->_rightnode = _Copy(root->_rightnode);
		return newroot;
	}
	int _Size(rootnode<T> *root,int &size)
	{
		if (root == NULL)
		{
			return 0;
		}
		size++;
		_Size(root->_leftnode,size);
		_Size(root->_rightnode,size);
		return size;
	}
	int _Depth(rootnode<T> *root)
	{
		if (root==NULL)
		{
			return 0;
		}
		int hight = 1;
		int left = 0;
		int right = 0;
		left += _Depth(root->_leftnode) + hight;
		right += _Depth(root->_rightnode) + hight;
		if (left > right)
		{
			return left;
		}
		else
		{
			return right;
		}
		
	}
	int _Leafnum(rootnode<T>* root,int &num)
	{
		if (root == NULL)
		{
			return 0;
		}
		if (root->_leftnode == NULL&&root->_rightnode == NULL)
		{
			num++;
		}
		_Leafnum(root->_leftnode, num);
		_Leafnum(root->_rightnode, num);
		return num;
	}
private:
	rootnode<T> *_root;
};

void Test1()
{
	char *str = "123##45##6##78###";
	BinaryTree<char> b1(str);
	BinaryTree<char> b2(b1);
	BinaryTree<char> b3 = b2;
	b1.Fastorder();
	cout << endl;
	b1.Inorder();
	cout << endl;
	b1.Postorder();
	cout << endl;
	b2.Fastorder();
	cout << endl;
	b3.Fastorder();
	cout << endl;
	cout << b3.Size()<<endl;
	cout << b3.Depth() << endl;
	b3.Levelorder();
	cout << endl;
	cout << b3.leafnum()<<endl;
}
int main()
{    
    Test1();
}

創(chuàng)新互聯(lián)www.cdcxhl.cn，專(zhuān)業(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ù)器買(mǎi)多久送多久。

分享名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)--二叉樹(shù)(1)-創(chuàng)新互聯(lián)
本文鏈接：http://www.rwnh.cn/article24/iihce.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、網(wǎng)站建設(shè)、網(wǎng)站導(dǎo)航、微信公眾號(hào)、品牌網(wǎng)站建設(shè)、網(wǎng)站營(yíng)銷(xiāo)

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

猜你還喜歡下面的內(nèi)容

中文字幕日韩精品一区二区免费_精品一区二区三区国产精品无卡在_国精品无码专区一区二区三区_国产αv三级中文在线

數(shù)據(jù)結(jié)構(gòu)--二叉樹(shù)(1)-創(chuàng)新互聯(lián)