樹相關(guān)的一些概念。
田東網(wǎng)站制作公司哪家好，找創(chuàng)新互聯(lián)建站！從網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、APP開發(fā)、自適應(yīng)網(wǎng)站建設(shè)等網(wǎng)站項(xiàng)目制作，到程序開發(fā)，運(yùn)營(yíng)維護(hù)。創(chuàng)新互聯(lián)建站成立與2013年到現(xiàn)在10年的時(shí)間，我們擁有了豐富的建站經(jīng)驗(yàn)和運(yùn)維經(jīng)驗(yàn)，來保證我們的工作的順利進(jìn)行。專注于網(wǎng)站建設(shè)就選創(chuàng)新互聯(lián)建站。
樹是n（n>=0）個(gè)有限個(gè)數(shù)據(jù)的元素集合，形狀像一顆倒過來的樹。
結(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)：沒有子節(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)開始到該節(jié)點(diǎn)所經(jīng)的所有節(jié)點(diǎn)都可以稱為該節(jié)點(diǎn)的祖先。
子孫：以某節(jié)點(diǎn)為根的子樹中任一節(jié)點(diǎn)都稱為該節(jié)點(diǎn)的子孫。
樹的高度：樹中距離根節(jié)點(diǎn)最遠(yuǎn)結(jié)點(diǎn)的路徑長(zhǎng)度。
樹的存儲(chǔ)結(jié)構(gòu)：
二叉樹的結(jié)構(gòu)
二叉樹:二叉樹是一棵特殊的樹，二叉樹每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，分別稱為左孩子和右孩子。
滿二叉樹:高度為N的滿二叉樹有2^N - 1個(gè)節(jié)點(diǎn)的二叉樹。
完全二叉樹: 若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第 h 層所有的結(jié)點(diǎn)都連續(xù)集中在最左邊，這就是完全二叉樹
前序遍歷(先根遍歷):
（1）：先訪問根節(jié)點(diǎn)；
（2）：前序訪問左子樹；
（3）：前序訪問右子樹；
中序遍歷:
（1）：中序訪問左子樹
（2）：訪問根節(jié)點(diǎn)；
（3）：中序訪問右子樹；
后序遍歷(后根遍歷):
（1）：后序訪問左子樹；
（2）：后序訪問右子樹；
（3）：訪問根節(jié)點(diǎn)；
層序遍歷：
（1）：一層層節(jié)點(diǎn)依次遍歷。
下面是二叉樹的具體實(shí)現(xiàn)：
template
struct BinaryTreeNode
{
BinaryTreeNode
BinaryTreeNode
T _data;
};
template
class BinaryTree
{
Typedef BinaryTreeNode< T> Node;
protected:
Node *_root;
public:
BinaryTree() //無參構(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;
}
//前序遍歷--------遞歸寫法，缺點(diǎn)是：有大量的壓棧開銷。
void Prevorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
cout << root->_data << " " ;
_prevorder( root->_left);
_prevorder( root->_right);
}
}
//前序遍歷------------非遞歸寫法
//前序遍歷的非遞歸寫法思想：需要借助棧。
void PrevOrderRonR()
{
stack
if (_root == NULL )//根結(jié)點(diǎn)為空的話直接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)行訪問棧頂元素
s.pop(); //訪問完棧頂元素將其從棧中pop掉。
if (top->_right)//要根據(jù)棧進(jìn)行先序遍歷，則必須是先訪問根節(jié)點(diǎn)，再訪問左子樹，最后訪問右子樹，因?yàn)闂Ｊ恰昂筮M(jìn)先出的”，要想先訪問左子樹，則必須先入右子樹，再入左子樹。如果棧頂元素的右子樹不為空，
{
s.push(top->_right); //棧頂?shù)挠易訕洳粸榭?，將其進(jìn)行壓棧。
}
if (top->_left)
{
s.push(top->_left); //棧頂?shù)淖笞訕洳粸榭?，將其進(jìn)行壓棧。
}
}
cout << endl;
}
//中序遍歷----------遞歸寫法
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);
}
}
}
}
//中序遍歷的非遞歸寫法，思想是：也是借助棧，主要核心是找最左結(jié)點(diǎn)，定義一個(gè)cur指針，讓它最開始指向_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;
}
}
//后序遍歷---------遞歸寫法
void Postorder(Node *root )
{
if (root == NULL)
{
return;
}
else
{
Postorder( root->_left);
Postorder( root->_right);
cout << root->_data << " " ;
}
}
//后序遍歷----------非遞歸寫法，思想是：先找最左結(jié)點(diǎn)，找到后但不能訪問最左結(jié)點(diǎn)，要先判斷最左結(jié)點(diǎn)的右子樹是否為空，若為空， 則可以訪問最左結(jié)點(diǎn)，否則不可以訪問最左結(jié)點(diǎn)，需要訪問右子樹。
//可以訪問根結(jié)點(diǎn)的條件：上一層訪問的節(jié)點(diǎn)為右子樹。所以我們需要定義兩個(gè)指針prev與cur ，cur用來保存當(dāng)前結(jié)點(diǎn)，prev用來保存上一層訪問的結(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è)棧頂指針，用來指向棧頂元素。
if (top->_right == NULL || top->_right == prev)//棧頂節(jié)點(diǎn)的右子樹為空或者上一次訪問的節(jié)點(diǎn)為右子樹，則可以訪問棧頂元素。
{
cout << top->_data << " " ;
s.pop();
prev = top;
}
else
{
cur = top->_left;
}
}
}
//二叉樹的層序遍歷（即是一層一層的進(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)前深度=（左子樹和右子樹中深度較大的一個(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),遞歸寫法。
{
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ù),思想：左子樹的葉子結(jié)點(diǎn)數(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);
}
//遞歸即是=子問題+返回條件
//方法一：
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ì)讓程序有線程安全問題
if (root == NULL )
{
return sSize;
}
++sSize;
_size(root->_left);
_size(root->_right);
return sSize;６
}
};
重慶分公司
重慶分公司
