數據結構：樹tree和二叉樹BinaryTree的實現與代碼分析

1些概念：

1棵樹是1些結點的集合。這個集合可以是空集，若不是空集，則樹由稱作根（root）的結點r和零個或多個非空的（子）樹T1，T2...Ta組成，子樹中每個棵的根都被來自根r的1條有向的邊（edge）所連接。

每棵子樹的根叫做根r的兒子（child），而r是每棵子樹的根的父親（parent）。

沒有兒子的結點成為葉（leaf）結點。

具有相同父親的結點為兄弟（siblings）結點。

對任意結點n，n的深度（depth）為從根到n的唯1路徑的長。因此根的深度為0.

n的高度是從n到1片樹葉的最長路徑的長。因此所有的樹葉的高度都是0.

1棵樹的高等于它的根的高。

1棵樹的深度等于它最深的樹葉的深度。等于根的高度。

前序遍歷：對結點的處理工作是在它的諸兒子結點被處理之前進行的。

后序遍歷：對結點的處理工作是在它的諸兒子結點被處理以后進行的。

內部路徑長（internal path length）1棵樹所有結點的深度總和。

	//普通的樹結點
	template <typename Object>
	struct TreeNode 
	{
		Object element;//結點的數據
		TreeNode* firstChild;//第1個兒子的指針
		TreeNode* nexSibling;//當前結點的兄弟結點的指針
	};

2叉樹：每一個結點最多有兩個兒子的樹。

每一個2叉樹，具有N個結點，N+1個NULL結點

	//2叉樹結點
	template<typename Object>
	struct BinaryNode 
	{
		Object element;//結點的數據
		BinaryNode* left;//左結點
		BinaryNode* right;//右結點
	};

//  
//  Vector.h  
//  HelloWorld  
//  csdn blog：http://blog.csdn.net/u012175089  
//  Created by Fable on 17/1/7.  
//  Copyright (c) 2017年 Fable. All rights reserved.  
//  

#ifndef __HelloWorld__Tree__  
#define __HelloWorld__Tree__
#include <iostream>
namespace Fable
{ 
	//2叉查找樹，對Comparable,必須實現了><=的比較
	template<typename Comparable>
	class BinarySearchTree
	{
	public:
		//構造函數
		BinarySearchTree(){}
		//復制構造函數
		BinarySearchTree(const BinarySearchTree& rhs)
		{
			root = clone(rhs.root);
		}
		//析構函數
		~BinarySearchTree()
		{
			makeEmpty(root);
		}
		//復制賦值運算符
		const BinarySearchTree& operator=(const BinarySearchTree& rhs)
		{
			if (this != &rhs)
			{
				makeEmpty(root);//先清除
				root = clone(rhs.root);//再復制
			}
			return *this;
		}
		//查找最小的對象
		const Comparable& findMin()const
		{
			findMin(root);
		}
		//查找最大的對象
		const Comparable& findMax()const
		{
			findMax(root);
		}
		//是不是包括了某個對象
		bool contains(const Comparable& x)const
		{
			return contains(x, root);
		}
		//樹為空
		bool isEmpty()const
		{
			return root == nullptr;
		}
		//打印整棵樹
		void printTree()const
		{
			printTree(root);
		}

		//清空樹
		void makeEmpty()
		{
			makeEmpty(root);
		}
		//插入某個對象
		void insert(const Comparable& x)
		{
			insert(x, root);
		}
		//移除某個對象
		void remove(const Comparable& x)
		{
			remove(x, root);
		} 
	private:
		struct BinaryNode 
		{
			Comparable element;
			BinaryNode* left;
			BinaryNode* right;
			BinaryNode(const Comparable& theElement, BinaryNode* lt, BinaryNode* rt)
				:element(theElement), left(lt), right(rt){}
		};
		BinaryNode* root;//根結點
		//插入對象，這里使用了援用
		void insert(const Comparable& x, BinaryNode*& t)const
		{
			if (!t)
			{
				t = new BinaryNode(x, nullptr, nullptr);
			}
			else if (x < t->element)
			{
				insert(x, t->left);//比根結點小，插入左側
			}
			else if (x > t->element)
			{
				insert(x, t->right);//比根結點大，插入右側
			}
			else
			{
				//相同的
			}
		} 
		void removeMin(BinaryNode*& x, BinaryNode*& t)const
		{
			if (!t)
			{
				return nullptr;//找不到
			}
			if (t->left)
			{
				return removeMin(t->left);//使用了遞歸的方式
			}
			else
			{
				//找到最小的結點了
				x->element = t->element;
				BinaryNode* oldNode = t;
				t = t->right;
				delete oldNode;//刪除原來要刪除的結點
				return t;
			}
			
		}
		//刪除某個對象，這里必須要援用
		void remove(const Comparable& x, BinaryNode*& t)const
		{
			if (!t)
			{
				return;//樹為空
			}
			else if (x < t->element)
			{
				remove(x, t->left);//比根結點小，去左側查找
			}
			else if (x > t->element)
			{
				remove(x, t->right);//比根結點大，去右側查找
			}
			else if (!t->left && !t->right)//找到結點了，有兩個葉子
			{
				removeMin(t, t->right);
			}
			else
			{
				BinaryNode* oldNode = t;
				t = (t->left) ? t->left : t->right;//走到這里，t最多只有1個葉子，將t指向這個葉子
				delete oldNode;//刪除原來要刪除的結點
			}
		}
		//左側子樹的結點肯定比當前根小的，所以1直往左側尋覓
		BinaryNode* findMin(BinaryNode* t)const
		{
			if (!t)
			{
				return nullptr;//找不到
			}
			if (!t->left)
			{
				return t;
			}
			return findMin(t->left);//使用了遞歸的方式
		}
		//右側子樹的結點肯定比當前根大，所以1直往右側找
		BinaryNode* findMax(BinaryNode* t)const
		{
			if (t)
			{
				while (t->right)//使用了循環的方式
				{
					t = t->right;
				}
			}
			return t;
		}
		//判斷是不是包括某個對象，由于要使用遞歸，所以還有1個public版本的
		bool contains(const Comparable& x, BinaryNode* t)const
		{
			if ( !t )
			{
				return false;//空結點了
			}
			else if (x < t->element)
			{
				//根據2叉樹的定義，比某個結點小的對象，肯定只能存在與這個結點的左側的子樹
				return contains(x, t->left);
			}
			else if (x > t->element)
			{
				//根據2叉樹的定義，比某個結點大的對象，肯定只能存在與這個結點的右側的子樹
				return contains(x, t->right);
			}
			else
			{
				//相等，就是找到啦。
				return true;
			}
		}
		//清空子樹
		void makeEmpty(BinaryNode*& t)
		{
			if (t)
			{
				makeEmpty(t->left);//清空左側
				makeEmpty(t->right);//清空右側
				delete t;//釋放本身
			}
			t = nullptr;//置為空
		}
		//打印子樹，這里沒有使用復雜的排位，純屬打印
		void printTree(BinaryNode* t)const
		{
			if (!t)
			{
				return;
			}
			std::cout << t->element << std::endl;//輸出本身的對象
			printTree(t->left);//打印左子樹
			printTree(t->right);//打印右子樹
		}
		BinaryNode* clone(BinaryNode* t)const
		{
			if (!t)
			{
				return nullptr;
			}
			return new BinaryNode(t->element, clone(t->left), clone(t->right));
		}
	};
}
#endif

但是在極真個情況下，是有可能失衡的，例如常常插入和刪除數據，按上面的算法來講，是會造成左子樹的比右子樹深。

當極度失衡，就變成1個單向鏈表了。

有些經過轉變的樹會斟酌著方面的問題，會做調劑。下1章再說了。

生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈