樹(shù)相關(guān)的一些概念。
樹(shù)是n（n>=0）個(gè)有限個(gè)數(shù)據(jù)的元素集合，形狀像一顆倒過(guò)來(lái)的樹(shù)。
結(jié)點(diǎn)：結(jié)點(diǎn)包含數(shù)據(jù)和指向其它結(jié)點(diǎn)的指針。
結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子節(jié)點(diǎn)個(gè)數(shù)。
葉子節(jié)點(diǎn)：沒(méi)有子節(jié)點(diǎn)的節(jié)點(diǎn)(度為0)。
父子節(jié)點(diǎn)：一個(gè)節(jié)點(diǎn)father指向另一個(gè)節(jié)點(diǎn)child，則child為孩子節(jié)點(diǎn)，father為父親結(jié)點(diǎn)。
兄弟節(jié)點(diǎn)：具有相同父節(jié)點(diǎn)的節(jié)點(diǎn)互為兄弟節(jié)點(diǎn)。
節(jié)點(diǎn)的祖先：從根節(jié)點(diǎn)開(kāi)始到該節(jié)點(diǎn)所經(jīng)的所有節(jié)點(diǎn)都可以稱(chēng)為該節(jié)點(diǎn)的祖先。
子孫：以某節(jié)點(diǎn)為根的子樹(shù)中任一節(jié)點(diǎn)都稱(chēng)為該節(jié)點(diǎn)的子孫。
樹(shù)的高度：樹(shù)中距離根節(jié)點(diǎn)最遠(yuǎn)結(jié)點(diǎn)的路徑長(zhǎng)度。
樹(shù)的存儲(chǔ)結(jié)構(gòu)：
二叉樹(shù)的結(jié)構(gòu)
二叉樹(shù):二叉樹(shù)是一棵特殊的樹(shù)，二叉樹(shù)每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，分別稱(chēng)為左孩子和右孩子。
滿(mǎn)二叉樹(shù):高度為N的滿(mǎn)二叉樹(shù)有2^N - 1個(gè)節(jié)點(diǎn)的二叉樹(shù)。
完全二叉樹(shù) 若設(shè)二叉樹(shù)的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹(shù)
前序遍歷(先根遍歷):
（1）：先訪問(wèn)根節(jié)點(diǎn)；
（2）：前序訪問(wèn)左子樹(shù)；
（3）：前序訪問(wèn)右子樹(shù)；
中序遍歷:
（1）：中序訪問(wèn)左子樹(shù)
（2）：訪問(wèn)根節(jié)點(diǎn)；
（3）：中序訪問(wèn)右子樹(shù)；
后序遍歷(后根遍歷):
（1）：后序訪問(wèn)左子樹(shù)；
（2）：后序訪問(wèn)右子樹(shù)；
（3）：訪問(wèn)根節(jié)點(diǎn)；
層序遍歷：
（1）：一層層節(jié)點(diǎn)依次遍歷。
下面是二叉樹(shù)的具體實(shí)現(xiàn)：
template
struct BinaryTreeNode
{
BinaryTreeNode
BinaryTreeNode
T _data;
};
template
class BinaryTree
{
Typedef BinaryTreeNode< T> Node;
protected:
Node *_root;
public:
BinaryTree() //無(wú)參構(gòu)造函數(shù)
:_root( NULL)
{
}
BinaryTree( const T *a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreateTree( a, size , invalid, index);
}
protected:
Node *__CreateTree( const T *a, size_t size, const T& invalid, size_t &index )
{
Node *root = NULL;
if (index < size && a[index ] != invalid) //是有效值時(shí)
{
root = new Node(a [index]);
root->_left = __CreateTree( a, size , invalid, ++ index);
root->_right = __CreateTree( a, size , invalid, ++index);
}
return root;
}
//前序遍歷--------遞歸寫(xiě)法，缺點(diǎn)是：有大量的壓棧開(kāi)銷(xiāo)。
void Prevorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
cout << root->_data << " " ;
_prevorder( root->_left);
_prevorder( root->_right);
}
}
//前序遍歷------------非遞歸寫(xiě)法
//前序遍歷的非遞歸寫(xiě)法思想：需要借助棧。
void PrevOrderRonR()
{
stack
if (_root == NULL )//根結(jié)點(diǎn)為空的話(huà)直接return掉即可。
{
return;
}
if (_root)
{
s.push(_root); //根不為空的時(shí)候?qū)⒏Y(jié)點(diǎn)進(jìn)行壓棧。
}
while (!s.empty())//判斷棧是否為空
{
Node *top = s.top(); //棧不為空，則取棧頂元素
cout << top->_data << " ";//然后進(jìn)行訪問(wèn)棧頂元素
s.pop(); //訪問(wèn)完棧頂元素將其從棧中pop掉。
if (top->_right)//要根據(jù)棧進(jìn)行先序遍歷，則必須是先訪問(wèn)根節(jié)點(diǎn)，再訪問(wèn)左子樹(shù)，最后訪問(wèn)右子樹(shù)，因?yàn)闂Ｊ恰昂筮M(jìn)先出的”，要想先訪問(wèn)左子樹(shù)，則必須先入右子樹(shù)，再入左子樹(shù)。如果棧頂元素的右子樹(shù)不為空，
{
s.push(top->_right); //棧頂?shù)挠易訕?shù)不為空，將其進(jìn)行壓棧。
}
if (top->_left)
{
s.push(top->_left); //棧頂?shù)淖笞訕?shù)不為空，將其進(jìn)行壓棧。
}
}
cout << endl;
}
//中序遍歷----------遞歸寫(xiě)法
void _Inorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
_Inorder(Node * root)
{
if (root == NULL )
{
return;
}
else
{
_Inorder(root->_left);
cout << root->_data << " " ;
Inorder(root->_right);
}
}
}
}
//中序遍歷的非遞歸寫(xiě)法，思想是：也是借助棧，主要核心是找最左結(jié)點(diǎn)，定義一個(gè)cur指針，讓它最開(kāi)始指向_root。
void TnOrderNonR()
{
stack
Node *cur = _root;
while (cur || !s.empty())
{
whie(cur) //找最左結(jié)點(diǎn)
{
s.push(cur); //將cur壓棧。
cur = cur->_left; //cur指向它的左孩子
}
Node *top = s.top();
cout << top->_data << " ";
s.pop();
cur = top->_right;
}
}
//后序遍歷---------遞歸寫(xiě)法
void Postorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
Postorder( root->_left);
Postorder( root->_right);
cout << root->_data << " " ;
}
}
//后序遍歷----------非遞歸寫(xiě)法，思想是：先找最左結(jié)點(diǎn)，找到后但不能訪問(wèn)最左結(jié)點(diǎn)，要先判斷最左結(jié)點(diǎn)的右子樹(shù)是否為空，若為空， 則可以訪問(wèn)最左結(jié)點(diǎn)，否則不可以訪問(wèn)最左結(jié)點(diǎn)，需要訪問(wèn)右子樹(shù)。
//可以訪問(wèn)根結(jié)點(diǎn)的條件：上一層訪問(wèn)的節(jié)點(diǎn)為右子樹(shù)。所以我們需要定義兩個(gè)指針prev與cur ，cur用來(lái)保存當(dāng)前結(jié)點(diǎn)，prev用來(lái)保存上一層訪問(wèn)的結(jié)點(diǎn)。
void PostOrderNonR()
{
stack
Node *prev = NULL;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)//找最左結(jié)點(diǎn)
{
s.push(cur);
cur = cur->_left;
}
Node *top = s.top(); //定義一個(gè)棧頂指針，用來(lái)指向棧頂元素。
if (top->_right == NULL || top->_right == prev)//棧頂節(jié)點(diǎn)的右子樹(shù)為空或者上一次訪問(wèn)的節(jié)點(diǎn)為右子樹(shù)，則可以訪問(wèn)棧頂元素。
{
cout << top->_data << " " ;
s.pop();
prev = top;
}
else
{
cur = top->_left;
}
}
}
//二叉樹(shù)的層序遍歷（即是一層一層的進(jìn)行遍歷）：思想是：需要借助隊(duì)列，首先取隊(duì)頭，判斷它是否為空，若為空直接return；不為空的時(shí)候，進(jìn)行入隊(duì)操作。
//如何取到隊(duì)頭？入數(shù)據(jù)還是入指針？最好入指針，需要保存數(shù)據(jù)或者節(jié)點(diǎn)的時(shí)候最好入指針。
void LevelOrder()
{
queue
if (_root == NULL )
{
return;
}
q.push(_root);
while (!q.empty())
{
Node *front = q.front(); //取隊(duì)頭元素
q.pop();
cout << front->_data<< " ";
if (front->_left)//隊(duì)頭元素的左孩子不為空的時(shí)候，將它的左孩子壓入隊(duì)列
{
q.push(front->_left);
}
if (front->_right)//隊(duì)頭元素的右孩子不為空的時(shí)候，將它的右孩子壓入隊(duì)列
{
q.push(front->_right);
}
}
}
size_t _Depth(Node *root )//思想：當(dāng)前深度=（左子樹(shù)和右子樹(shù)中深度較大的一個(gè)）+1；
{
if（root == NULL）
{
return 0；
}
int left = _Depth(root->_left);
int right = _Depth(root ->_right);
return left > right ? left + 1 : right + 1;
}
size_t _GetKLevel(Node *root , size_t K)//取第K層結(jié)點(diǎn),遞歸寫(xiě)法。
{
if (root == NULL)
{
return 0;
}
if (K == 1)
{
return 1;
}
return _GetKLevel(root ->_left, K - 1) + _GetKLevel(root->_right, K - 1);
}
Node* _Find(Node * root, const T& x)//查找結(jié)點(diǎn)為x的結(jié)點(diǎn)
{
if (root == NULL)
{
return NULL ;
}
if (root ->_data == x)
{
return root ;
}
Node *ret = _Find( root->_left, x );
if (ret)
{
return ret;
}
else
{
return _Find(root ->_right, x);
}
}
size_t _leafsize(Node *root )//求葉子節(jié)點(diǎn)的個(gè)數(shù),思想：左子樹(shù)的葉子結(jié)點(diǎn)數(shù)目+右子樹(shù)的葉子結(jié)點(diǎn)的數(shù)目。
{
if (root == NULL)
{
return 0;
}
if (root ->_left == NULL&& root->_right == NULL )
{
return 1;
}
return _leafsize(root ->_left) + _leafsize(root->_right);
}
//遞歸即是=子問(wèn)題+返回條件
//方法一：
size_t _size(Node *root )//結(jié)點(diǎn)的數(shù)目
{
if (root == NULL)
{
return 0;
}
return _size(root ->_left) + _size(root->_right) + 1;
}
//方法二：遍歷法
size_t _size(Node *root)
{
static size_t sSize = 0;//此句代碼會(huì)讓程序有線程安全問(wèn)題
if (root == NULL )
{
return sSize;
}
++sSize;
_size(root->_left);
_size(root->_right);
return sSize;６
}
};
另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性?xún)r(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿(mǎn)足用戶(hù)豐富、多元化的應(yīng)用場(chǎng)景需求。
重慶分公司
重慶分公司
