亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

C++實現二叉樹

發布時間:2020-07-21 21:06:36 來源:網絡 閱讀:453 作者:zgw285763054 欄目:編程語言
#include <assert.h>
#include <iostream>
using namespace std;
#include <stack>
#include <queue>

template<class T>
struct BinaryTreeNode
{
	BinaryTreeNode<T>* _left;
	BinaryTreeNode<T>* _right;
	T _data;

	BinaryTreeNode(const T& x)
		:_left(NULL)
		,_right(NULL)
		,_data(x)
	{}
};

template<class T>
class BinaryTree
{
public:
	BinaryTree()
		:_root(NULL)
	{}

	BinaryTree(const T* a, size_t size, const T& invalid)
	{
		size_t index = 0;
		_root = _CreateTree(a, size, index, invalid);
	}

	~BinaryTree()
	{
		_DestroyTree(_root);
		_root = NULL;
	}

	BinaryTree(const BinaryTree<T>& t)
	{
		_root = _CopyTree(t._root);
	}

	//賦值運算符重載的傳統寫法
	/*BinaryTree<T>& operator=(const BinaryTree& t)
	{
		if (this != &t)
		{
			_DestroyTree(_root);
			_root = _CopyTree(t._root);
		}

		return *this;
	}*/

	//賦值運算符重載的現代寫法
	BinaryTree<T>& operator=(BinaryTree<T> t)
	{
		swap(_root, t._root);

		return *this;
	}

	//遞歸前序遍歷
	void PreOrderTraverse()
	{
		_PreOrderTraverse(_root);

		cout<<endl;
	}

	//遞歸中序遍歷
	void InOrderTraverse()
	{
		_InOrderTraverse(_root);

		cout<<endl;
	}

	//遞歸后序遍歷
	void PostOrderTraverse()
	{
		_PostOrderTraverse(_root);

		cout<<endl;
	}

	//非遞歸層序遍歷
	void LevelOrderTraverse()
	{
		if (NULL == _root)
		{
			return;
		}

		queue<BinaryTreeNode<T>*> q;
		q.push(_root);
		while (!q.empty())
		{
			BinaryTreeNode<T>* front = q.front();
			q.pop();
			cout<<front._data<<" ";

			if (front->_left)
			{
				q.push(front->_left);
			}

			if (front->_right)
			{
				q.push(front->_right);
			}
		}
	}
	
	//非遞歸前序遍歷
	void PreOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack<BinaryTreeNode<T>*> s;
		s.push(_root);

		while (!s.empty())//當棧為空時遍歷完成
		{
			//先訪問根節點
			BinaryTreeNode<T>* top = s.top();
			s.pop();
			cout<<top->_data<<" ";

			//右節點存在時先入棧,后出棧
			if (top->_right)
			{
				s.push(top->_right);
			}

			//左結點存在時后入棧,先出棧
			if (top->_left)
			{
				s.push(top->_left);
			}
		}

		cout<<endl;
	}

	//非遞歸中序遍歷
	void InOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;

		while (cur || !s.empty())
		{
			//左結點全部入棧
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			if (!s.empty())
			{
				BinaryTreeNode<T>* top = s.top();
				cout<<top->_data<<" ";
				s.pop();

				cur = top->_right;//將棧頂結點的右節點看作子樹的根節點
			}
		}

		cout<<endl;
	}

	//非遞歸后序遍歷
	void PostOrderTraverse_NonR()
	{
		if (NULL == _root)
		{
			return;
		}

		stack<BinaryTreeNode<T>*> s;
		BinaryTreeNode<T>* cur = _root;
		BinaryTreeNode<T>* pre = NULL;

		while (cur || !s.empty())//當前結點為空和棧為空同時滿足時遍歷完成
		{
			//左結點全部入棧
			while (cur)
			{
				s.push(cur);
				cur = cur->_left;
			}

			BinaryTreeNode<T>* top = s.top();

			if (NULL == top->_right || pre == top->_right)//若當前結點的右結點為空或者右節點已經訪問過,可以訪問該結點
			{
				cout<<top->_data<<" ";
				pre = top;
				s.pop();
			}
			else//該結點的右節點不為空且未被訪問
			{
				cur = top->_right;//將該結點的右節點看作子樹的根節點
			}
		}

		cout<<endl;
	}

	//求結點數
	size_t Size()
	{
		size_t size = 0;
		_Size(_root, size);
		return size;
	}

	//求深度
	size_t Depth()
	{
		return _Depth(_root);
	}

	//求葉子結點數
	size_t LeafSize()
	{
		size_t leafSize = 0;
		_LeafSize(_root, leafSize);
		return leafSize;
	}

	//求第K層結點數
	size_t GetKLevel(const size_t& k)
	{
		 return _GetKLevel(_root, k);
	}
protected:
	BinaryTreeNode<T>* _CreateTree(const T* a, size_t size, size_t& index, const T& invalid)
	{
		BinaryTreeNode<T>* root = NULL;

		if (index < size && a[index] != invalid)
		{
			root = new BinaryTreeNode<T>(a[index]);
			root->_left = _CreateTree(a, size, ++index, invalid);
			root->_right = _CreateTree(a, size, ++index, invalid);
		}

		return root;
	}
	
	void _DestroyTree(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return;
		}

		if (NULL == root->_left && NULL == root->_right)
		{
			delete root;
			root = NULL;
			return;
		}

		_DestroyTree(root->_left);
		_DestroyTree(root->_right);
		delete root;
	}

	BinaryTreeNode<T>* _CopyTree(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return NULL;
		}

		BinaryTreeNode<T>* newRoot = new BinaryTreeNode<T>(root->_data);
		newRoot->_left = _CopyTree(root->_left);
		newRoot->_right = _CopyTree(root->_right);

		return newRoot;
	}

	void _PreOrderTraverse(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return;
		}

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

	void _InOrderTraverse(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return;
		}

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

	void _PostOrderTraverse(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return;
		}

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

	//_Size方法1:
	/*size_t _Size(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return;
		}

		return _Size(root->left) + _Size(root->_right) + 1;
	}*/

	//_Size方法2:(存在線程安全問題)
	/*size_t _Size(BinaryTreeNode<T>* root)
	{
		static size_t size = 0;
		if (NULL == root)
		{
			return 0;
		}
		else
		{
			++size;
		}

		_Size(root->_left);
		_Size(root->_right);

		return size;
	}*/

	//_Size方法3:
	void _Size(BinaryTreeNode<T>* root, size_t& size)
	{
		if (NULL == root)
		{
			return;
		}
		else
		{
			++size;
		}

		_Size(root->_left, size);
		_Size(root->_right, size);
	}

	size_t _Depth(BinaryTreeNode<T>* root)
	{
		if (NULL == root)
		{
			return 0;
		}

		size_t leftDepth = _Depth(root->_left);
		size_t rightDepth = _Depth(root->_right);

		return leftDepth > rightDepth ? leftDepth+1 : rightDepth+1;
	}

	void _LeafSize(BinaryTreeNode<T>* root, size_t& leafSize)
	{
		if (NULL == root)
		{
			return;
		}

		if (NULL == root->_left && NULL == root->_right)
		{
			++leafSize;
			return;
		}

		_LeafSize(root->_left, leafSize);
		_LeafSize(root->_right, leafSize);
	}

	size_t _GetKLevel(BinaryTreeNode<T>* root, const size_t& k)
	{
		assert(k > 0);

		if (NULL == root)
		{
			return 0;
		}

		if (k == 1)
		{
			return 1;
		}

		return _GetKLevel(root->_left, k-1) + _GetKLevel(root->_right, k-1);
	}
protected:
	BinaryTreeNode<T>* _root;
};

void BinaryTreeTest()
{
	int a[] = {1, 2, 3, '#', '#', 4, '#', '#', 5, 6};
	BinaryTree<int> t(a, sizeof(a)/sizeof(a[0]), '#');

	cout<<"遞歸前序遍歷:";
	t.PreOrderTraverse();
	cout<<"遞歸中序遍歷:";
	t.InOrderTraverse();
	cout<<"遞歸后序遍歷:";
	t.PostOrderTraverse();
	cout<<"非遞歸前序遍歷:";
	t.PreOrderTraverse_NonR();
	cout<<"非遞歸中序遍歷:";
	t.InOrderTraverse_NonR();
	cout<<"非遞歸后序遍歷:";
	t.PostOrderTraverse_NonR();

	cout<<"Size:"<<t.Size()<<endl;
	cout<<"Depth:"<<t.Depth()<<endl;
	cout<<"LeafSize:"<<t.LeafSize()<<endl;
	cout<<"Get3Level:"<<t.GetKLevel(3)<<endl;

	BinaryTree<int> t2(t);
	cout<<"t2:";
	t2.PreOrderTraverse();

	BinaryTree<int> t3;
	t3 = t2;
	cout<<"t3:";
	t3.PreOrderTraverse();
}

int main()
{
	BinaryTreeTest();

	return 0;
}

生成的二叉樹如下圖:

C++實現二叉樹

測試結果:

C++實現二叉樹

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

会同县| 陵水| 夏津县| 金华市| 邯郸市| 定襄县| 三门峡市| 如东县| 焦作市| 余庆县| 鲜城| 台南县| 闸北区| 榆树市| 遂昌县| 响水县| 信宜市| 库尔勒市| 比如县| 舒兰市| 贵德县| 伊春市| 城口县| 特克斯县| 尤溪县| 桑日县| 仙桃市| 东源县| 淮北市| 神农架林区| 林芝县| 大新县| 太和县| 泸西县| 紫金县| 泌阳县| 北安市| 嵩明县| 新乡市| 佛教| 江陵县|