【C++】二叉樹的基本知識及其遍歷-創(chuàng)新互聯(lián)

二叉樹：每個節(jié)點最多兩個孩子節(jié)點。

網(wǎng)站建設(shè)哪家好，找成都創(chuàng)新互聯(lián)公司！專注于網(wǎng)頁設(shè)計、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序開發(fā)、集團企業(yè)網(wǎng)站建設(shè)等服務(wù)項目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了寶雞免費建站歡迎大家使用！

二叉樹的結(jié)構(gòu)： struct TreeNode

{

DataType _value; //節(jié)點值

TreeNode* _left; //左孩子

TreeNode* _ridht; //右孩子

};

二叉樹的基礎(chǔ)：構(gòu)造、拷貝構(gòu)造、析構(gòu)、賦值運算符的重載

二叉樹的知識點：高度、節(jié)點的個數(shù)、子節(jié)點的個數(shù)

二叉樹的遍歷：前序、中序、后序遍歷(遞歸及非遞歸)

遍歷順序：前序——根左右中序——左根右后序——左右根

注意: 遞歸遍歷時，應(yīng)該注意不要出現(xiàn)棧溢出現(xiàn)象。

因為++index返回對象，index++返回臨時變量，所以傳引用做參數(shù)時有++index。

#pragma once

#include<queue>
#include<stack>

//二叉樹的結(jié)構(gòu)
template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;
	//構(gòu)造函數(shù)
	BinaryTreeNode(const T& x)
		:_left(NULL)
		, _right(NULL)
		, _data(x)
	{}
};
template<class T>
class BinaryTree
{
	typedef BinaryTreeNode<T> Node;  

public:
	//構(gòu)造
	BinaryTree()
		:_root(NULL)
	{}
	// a--樹的節(jié)點前序遍歷的數(shù)組  size--數(shù)組中元素個數(shù)  invaild--無效值即節(jié)點為空
	BinaryTree(const T* a,size_t size,const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size,invalid,index);
	}
	//析構(gòu)
	~BinaryTree()
	{
		_Destory(_root);
		_root = NULL;
	}
	//拷貝  
	BinaryTree(const BinaryTree<T>& t)
	{
		_root = _Copy(t._root);
	}
    //賦值重載(傳統(tǒng))
	//BinaryTree<T>& operator=(const BinaryTree<T>& t)
	//{
	//	if (this != &t)
	//	{
	//		Node* tmp = _Copy(t._root);
	//		_Destory(_root);
	//		_root = tmp;
	//	}
	//	return *this;
	//}
	//賦值重載(現(xiàn)代)
	BinaryTree<T>& operator=(BinaryTree<T> t)
	{
		swap(_root, t._root);
		return *this;
	}

	T& operator->()
	{
		return _root;
	}

public:
	void PrevOrder()//前序
	{
		_PrevOrder(_root);
		cout << endl;
	}
	void InOrder()//中序
	{
		_InOrder(_root);
		cout << endl;
	}
	void PostOrder()//后序
	{
		_PostOrder(_root);
		cout << endl;
	}

	size_t Size()  //節(jié)點個數(shù)
	{
		return _Size(_root);
	}
	size_t Depth()  //樹的深度
	{
		return _Depth(_root);
	}
	size_t LeafSize()  //葉子節(jié)點個數(shù)
	{
		return _LeafSize(_root);
	}
	
	//層次遍歷
	void LevelOrder()
	{
		queue<Node*> q;
		if (_root)
		{
			q.push(_root);
		}
		while (!q.empty())
		{
			Node* front = q.front();
			cout << front->_data << " ";
			q.pop();

			if (front->_left)
			{
				q.push(front->_left);
			}
			if (front->_right)
			{
				q.push(front->_right);
			}
		}
		cout << endl;
	}
public:
	//非遞歸的前中后序遍歷（棧）
	void PrevOrder_NonR()
	{
		stack<Node*> s;
		if (_root)
			s.push(_root);
		while (!s.empty())
		{
			Node* top = s.top();
			cout << top->_data << " ";
			s.pop();
			//棧后進先出  ，所以 右先進，左先出
			if (top->_right)
				s.push(top->_right);
			if (top->_left)
				s.push(top->_left);
		}
		cout << endl;
	}
	void InOrder_NonR()
	{
		//壓左樹
		//取出一個節(jié)點即它的左路走完了，在訪問右樹（看作子問題）
		stack<Node*> s;
		Node* cur = _root;
		while (cur || !s.empty())
		{
			//壓樹的左路節(jié)點直至最左段節(jié)點
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			if (!s.empty())
			{
				Node* top = s.top();
				s.pop();
				cout << top->_data << " ";
				cur=top->_right;
			}
		}
		cout << endl;

	}

	void PostOrder_NonR()
	{
		Node* prev = NULL;
		Node* cur = _root;
		stack<Node*> s;
		while (cur || !s.empty())
		{
			//壓樹的左路節(jié)點直至最左段節(jié)點
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			Node* top = s.top();
			if (top->_right == NULL || top->_right == prev)
			{
				cout << top->_data << " ";
				s.pop();
				prev = top;
			}
			else
			{
				cur = top->_right;
			}
		}
		cout << endl;
	}


protected:
        //注意 此處index要用引用傳參
	Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index) 
	{
		Node* root = NULL;
		if ((index < size) && (a[index] != invalid))
		{
			root = new Node(a[index]);
		
                        //注意下面只能用++index。此處傳的是引用 
                       //因為++index返回對象，index++返回臨時變量。
			root->_left = _CreateTree(a, size, invalid, ++index);
			root->_right = _CreateTree(a, size, invalid, ++index);
                 }
		return root;
	}

	void _Destory(Node* root)
	{
		if (root == NULL)
			return;
		_Destroy(root->_left);
		_Destroy(root->_right);
		delete root;
	}
	Node* _Copy(Node* root)
	{
		if (root == NULL)
			return NULL;
		NOde* newRoot = new Node(root->_data);
		newRoot->_left = _Copy(root->_left);
		newRoot->_right = _Copy(root->_right);
		return newRoot;
	}
        //////////////
	void _PrevOrder(Node* root)
	{
		if (root == NULL)
			return;

		cout << root->_data << " ";
		_PrevOrder(root->_left);
		_PrevOrder(root->_right);
	}
	void _InOrder(Node* root)
	{
		if (root == NULL)
			return;

		_InOrder(root->_left);
		cout << root->_data << " ";
		_InOrder(root->_right);
	}
	void _PostOrder(Node* root)
	{
		if (root == NULL)
			return;

		_PostOrder(root->_left);
		_PostOrder(root->_right);
		cout << root->_data << " ";
	}

	size_t _Size(Node* root)
	{
		if (root == NULL)
			return 0;
		return (_Size(root->_left) + _Size(root->_right) + 1);
	}
	size_t _Depth(Node* root)
	{
		if (root == NULL)
			return 0;
		size_t LeftDepth = _Depth(root->_left);
		size_t RightDepth = _Depth(root->_right);

		return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 1);
	}

	size_t _LeafSize(Node* root)
	{
		if (root == NULL)
			return 0;
		if ((root->_left == NULL) && (root->_right == NULL))
			return 1;
		return (_LeafSize(root->_left) + _LeafSize(root->_right));
	}
private:
	Node *_root;
};

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

本文題目：【C++】二叉樹的基本知識及其遍歷-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://bm7419.com/article48/diopep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站導(dǎo)航、網(wǎng)站策劃、關(guān)鍵詞優(yōu)化、用戶體驗、品牌網(wǎng)站設(shè)計、企業(yè)建站

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

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