數(shù)據(jù)結(jié)構(gòu)：樹tree和二叉樹BinaryTree的實(shí)現(xiàn)與代碼分析

1些概念：

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

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

沒有兒子的結(jié)點(diǎn)成為葉（leaf）結(jié)點(diǎn)。

具有相同父親的結(jié)點(diǎn)為兄弟（siblings）結(jié)點(diǎn)。

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

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

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

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

前序遍歷：對結(jié)點(diǎn)的處理工作是在它的諸兒子結(jié)點(diǎn)被處理之前進(jìn)行的。

后序遍歷：對結(jié)點(diǎn)的處理工作是在它的諸兒子結(jié)點(diǎn)被處理以后進(jìn)行的。

內(nèi)部路徑長（internal path length）1棵樹所有結(jié)點(diǎn)的深度總和。

	//普通的樹結(jié)點(diǎn)
	template <typename Object>
	struct TreeNode 
	{
		Object element;//結(jié)點(diǎn)的數(shù)據(jù)
		TreeNode* firstChild;//第1個(gè)兒子的指針
		TreeNode* nexSibling;//當(dāng)前結(jié)點(diǎn)的兄弟結(jié)點(diǎn)的指針
	};

2叉樹：每一個(gè)結(jié)點(diǎn)最多有兩個(gè)兒子的樹。

每一個(gè)2叉樹，具有N個(gè)結(jié)點(diǎn)，N+1個(gè)NULL結(jié)點(diǎn)

	//2叉樹結(jié)點(diǎn)
	template<typename Object>
	struct BinaryNode 
	{
		Object element;//結(jié)點(diǎn)的數(shù)據(jù)
		BinaryNode* left;//左結(jié)點(diǎn)
		BinaryNode* right;//右結(jié)點(diǎn)
	};

//  
//  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,必須實(shí)現(xiàn)了><=的比較
	template<typename Comparable>
	class BinarySearchTree
	{
	public:
		//構(gòu)造函數(shù)
		BinarySearchTree(){}
		//復(fù)制構(gòu)造函數(shù)
		BinarySearchTree(const BinarySearchTree& rhs)
		{
			root = clone(rhs.root);
		}
		//析構(gòu)函數(shù)
		~BinarySearchTree()
		{
			makeEmpty(root);
		}
		//復(fù)制賦值運(yùn)算符
		const BinarySearchTree& operator=(const BinarySearchTree& rhs)
		{
			if (this != &rhs)
			{
				makeEmpty(root);//先清除
				root = clone(rhs.root);//再復(fù)制
			}
			return *this;
		}
		//查找最小的對象
		const Comparable& findMin()const
		{
			findMin(root);
		}
		//查找最大的對象
		const Comparable& findMax()const
		{
			findMax(root);
		}
		//是不是包括了某個(gè)對象
		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);
		}
		//插入某個(gè)對象
		void insert(const Comparable& x)
		{
			insert(x, root);
		}
		//移除某個(gè)對象
		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;//根結(jié)點(diǎn)
		//插入對象，這里使用了援用
		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);//比根結(jié)點(diǎn)小，插入左側(cè)
			}
			else if (x > t->element)
			{
				insert(x, t->right);//比根結(jié)點(diǎn)大，插入右側(cè)
			}
			else
			{
				//相同的
			}
		} 
		void removeMin(BinaryNode*& x, BinaryNode*& t)const
		{
			if (!t)
			{
				return nullptr;//找不到
			}
			if (t->left)
			{
				return removeMin(t->left);//使用了遞歸的方式
			}
			else
			{
				//找到最小的結(jié)點(diǎn)了
				x->element = t->element;
				BinaryNode* oldNode = t;
				t = t->right;
				delete oldNode;//刪除原來要?jiǎng)h除的結(jié)點(diǎn)
				return t;
			}
			
		}
		//刪除某個(gè)對象，這里必須要援用
		void remove(const Comparable& x, BinaryNode*& t)const
		{
			if (!t)
			{
				return;//樹為空
			}
			else if (x < t->element)
			{
				remove(x, t->left);//比根結(jié)點(diǎn)小，去左側(cè)查找
			}
			else if (x > t->element)
			{
				remove(x, t->right);//比根結(jié)點(diǎn)大，去右側(cè)查找
			}
			else if (!t->left && !t->right)//找到結(jié)點(diǎn)了，有兩個(gè)葉子
			{
				removeMin(t, t->right);
			}
			else
			{
				BinaryNode* oldNode = t;
				t = (t->left) ? t->left : t->right;//走到這里，t最多只有1個(gè)葉子，將t指向這個(gè)葉子
				delete oldNode;//刪除原來要?jiǎng)h除的結(jié)點(diǎn)
			}
		}
		//左側(cè)子樹的結(jié)點(diǎn)肯定比當(dāng)前根小的，所以1直往左側(cè)尋覓
		BinaryNode* findMin(BinaryNode* t)const
		{
			if (!t)
			{
				return nullptr;//找不到
			}
			if (!t->left)
			{
				return t;
			}
			return findMin(t->left);//使用了遞歸的方式
		}
		//右側(cè)子樹的結(jié)點(diǎn)肯定比當(dāng)前根大，所以1直往右側(cè)找
		BinaryNode* findMax(BinaryNode* t)const
		{
			if (t)
			{
				while (t->right)//使用了循環(huán)的方式
				{
					t = t->right;
				}
			}
			return t;
		}
		//判斷是不是包括某個(gè)對象，由于要使用遞歸，所以還有1個(gè)public版本的
		bool contains(const Comparable& x, BinaryNode* t)const
		{
			if ( !t )
			{
				return false;//空結(jié)點(diǎn)了
			}
			else if (x < t->element)
			{
				//根據(jù)2叉樹的定義，比某個(gè)結(jié)點(diǎn)小的對象，肯定只能存在與這個(gè)結(jié)點(diǎn)的左側(cè)的子樹
				return contains(x, t->left);
			}
			else if (x > t->element)
			{
				//根據(jù)2叉樹的定義，比某個(gè)結(jié)點(diǎn)大的對象，肯定只能存在與這個(gè)結(jié)點(diǎn)的右側(cè)的子樹
				return contains(x, t->right);
			}
			else
			{
				//相等，就是找到啦。
				return true;
			}
		}
		//清空子樹
		void makeEmpty(BinaryNode*& t)
		{
			if (t)
			{
				makeEmpty(t->left);//清空左側(cè)
				makeEmpty(t->right);//清空右側(cè)
				delete t;//釋放本身
			}
			t = nullptr;//置為空
		}
		//打印子樹，這里沒有使用復(fù)雜的排位，純屬打印
		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

但是在極真?zhèn)€情況下，是有可能失衡的，例如常常插入和刪除數(shù)據(jù)，按上面的算法來講，是會造成左子樹的比右子樹深。

當(dāng)極度失衡，就變成1個(gè)單向鏈表了。

有些經(jīng)過轉(zhuǎn)變的樹會斟酌著方面的問題，會做調(diào)劑。下1章再說了。

生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈