溫馨提示×
您好，登錄后才能下訂單哦！
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》
您好，登錄后才能下訂單哦！
二叉樹：樹的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。
1.實(shí)現(xiàn)二叉鏈表的結(jié)構(gòu)：
//節(jié)點(diǎn)結(jié)構(gòu)
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _left;//左子樹
BinaryTreeNode<T>* _right;//右子樹
T _data;//數(shù)據(jù)域
//構(gòu)造函數(shù)
BinaryTreeNode(const T& x)
:_left(NULL)//左孩子指針
,_right(NULL)//右孩子指針
,_data(x)//數(shù)據(jù)域
{}
};
2.求二叉樹的葉子結(jié)點(diǎn)數(shù)_LeafSize:
葉結(jié)點(diǎn)：無后繼結(jié)點(diǎn)的結(jié)點(diǎn)。
方法一：設(shè)置一下全局變量或者靜態(tài)變量的size，遍歷二叉樹，每次遇到一個(gè)節(jié)點(diǎn)就加加一次size；
方法二：遞歸實(shí)現(xiàn)，總?cè)~結(jié)點(diǎn)數(shù)=左子樹葉結(jié)點(diǎn)個(gè)數(shù)+右子樹葉結(jié)點(diǎn)個(gè)數(shù)。
//方法1：后序遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)
size_t _LeafSize(Node* root)
{
static int size = 0;
if (root == NULL)
{
return size;
}
if (root->_left == NULL&&root->_right == NULL)
{
size++;
return size;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}
//方法2：后序遞歸遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)
size_t _LeafSize(Node* root)
{
if (root == NULL)
{
return 0;
}
else if (root->_left == NULL&&root->_right == NULL)
{
return 1;
}
else
{
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
}
3.求二叉樹的深度_depth:
深度也稱作為高度，就是左子樹和右子樹深度的較大值。
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
int LeftDepth = _Depth(root->_left);
int RightDepth = _Depth(root->_right);
return (LeftDepth>RightDepth) ? LeftDepth + 1 : RightDepth + 1;
}
4.求二叉樹的結(jié)點(diǎn)個(gè)數(shù)_size:
總結(jié)點(diǎn)數(shù)=左子樹結(jié)點(diǎn)個(gè)數(shù)+右子樹結(jié)點(diǎn)個(gè)數(shù)+根結(jié)點(diǎn)個(gè)數(shù)1
size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
5.求第k層節(jié)點(diǎn)數(shù)：（默認(rèn)根節(jié)點(diǎn)為第1層）
方法與求葉結(jié)點(diǎn)同理。
size_t _kLevelSize(Node* root, int k)//默認(rèn)根結(jié)點(diǎn)為第1層
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);
}
6.遍歷二叉樹：
6.1先序遍歷：訪問根結(jié)點(diǎn)->左子樹->右子樹
//先序遍歷：根結(jié)點(diǎn)->左子樹->右子樹
void _PrevOrder(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
6.2先序遍歷非遞歸寫法：
用棧模擬前序遍歷，棧的特點(diǎn)是后進(jìn)先出，則將無條件地入棧根結(jié)點(diǎn)，在彈出根結(jié)點(diǎn)之前依次將根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)和左孩子結(jié)點(diǎn)入棧。
//先序遍歷非遞歸,根結(jié)點(diǎn)->左子樹->右子樹，利用棧"后進(jìn)先出"特點(diǎn)實(shí)現(xiàn)
void _PrevOrderNon_R(Node* root)
{
stack<Node*>s;
if (root == NULL)
{
return;
}
s.push(root);
while (!s.empty())
{
root = s.top();
cout << root->_data << " ";
s.pop();
if (root->_right)//注意要先壓入右結(jié)點(diǎn)，才能讓右結(jié)點(diǎn)后出
{
s.push(root->_right);
}
if (root->_left)
{
s.push(root->_left);
}
}
}
6.3中序遍歷：訪問左子樹->根結(jié)點(diǎn)->右子樹
//中序遍歷：左子樹->根結(jié)點(diǎn)->右子樹
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
6.4中序遍歷非遞歸寫法：
二叉樹：
1
2 5
3 4 6
1、借助棧實(shí)現(xiàn)，先順著二叉樹找到最左邊且最下邊的結(jié)點(diǎn)3（一邊找一邊入棧），此時(shí)入棧序列為1，2，3。
2、按照中序遍歷要彈出棧頂元素3，則彈出棧頂元素3。
3、接著是右子樹，判斷它的右子樹是否為空， 若為空，往回返，打印2，彈出棧頂元素2；若不為空， 該右子樹，指針指向右子樹結(jié)點(diǎn)，再重復(fù)之前的步驟1，2，3。
//中序遍歷非遞歸,最左結(jié)點(diǎn)cur是要訪問的第一個(gè)結(jié)點(diǎn)，先把左壓進(jìn)去，然后把右樹當(dāng)成子樹
void _InOrderNon_R(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*>s;
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子
cout << s.top()->_data << " ";
s.pop();
if (cur->_right == NULL)
{
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
6.5后序遍歷：訪問左子樹->右子樹->根結(jié)點(diǎn)
//后序遍歷：左子樹->右子樹->根結(jié)點(diǎn)
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
6.6后序遍歷非遞歸寫法：
1、后序遍歷同樣借助棧實(shí)現(xiàn)，先找到最左邊且為最下面的結(jié)點(diǎn)3（一邊入棧一邊找）；
2、結(jié)點(diǎn)3若沒有右孩子，打印節(jié)點(diǎn)3，之后彈出棧頂結(jié)點(diǎn)3；
3、結(jié)點(diǎn)3若有右孩子，繼續(xù)遍歷它的右子樹，等遍歷結(jié)束才可打印3。遍歷重復(fù)步驟1,2,3
//后序遍歷非遞歸：左子樹->右子樹->根結(jié)點(diǎn),prev指向上一個(gè)剛剛訪問過的結(jié)點(diǎn)
void _PostOrderNon_R(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*>s;
Node* cur = root;
Node* prev = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子
//無右孩子和右孩子是剛剛被訪問過的結(jié)點(diǎn)，此時(shí)應(yīng)該訪問根結(jié)點(diǎn)
if (cur->_right == NULL || cur->_right == prev)
{
cout << cur->_data << " ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;//除上面兩種情況，均不訪問根，繼續(xù)遍歷右子樹
}
}
}
6.7層序遍歷：
上一層遍歷結(jié)束，再遍歷下一層結(jié)點(diǎn)，如int arr1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }（#表示空）,則層次遍歷就應(yīng)為：1，2，5，3，4，6。
考慮用隊(duì)列解決該問題：首先先給隊(duì)列無條件入隊(duì)根結(jié)點(diǎn)，接著在出隊(duì)根結(jié)點(diǎn)之前先入隊(duì)它的子女結(jié)點(diǎn)2、5，則出隊(duì)1后，隊(duì)頭元素為2，在出隊(duì)它之前入隊(duì)它的根結(jié)點(diǎn)3，4……
//層序遍歷
void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);
while (!q.empty())
{
if (q.front()->_left != NULL)
{
q.push(q.front()->_left);
}
if (q.front()->_right != NULL)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " ";
q.pop();
}
}
完整代碼實(shí)現(xiàn)：
#include<iostream>
using namespace std;
#include<assert.h>
#include<queue>
#include<stack>
//節(jié)點(diǎn)結(jié)構(gòu)
template<class T>
struct BinaryTreeNode
{
BinaryTreeNode<T>* _left;//左子樹
BinaryTreeNode<T>* _right;//右子樹
T _data;//數(shù)據(jù)域
//構(gòu)造函數(shù)
BinaryTreeNode(const T& x)
:_left(NULL)//左孩子指針
,_right(NULL)//右孩子指針
,_data(x)//數(shù)據(jù)域
{}
};
//二叉樹類
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;//Node結(jié)點(diǎn)結(jié)構(gòu)
public:
BinaryTree()
:_root(NULL)
{}
//構(gòu)造函數(shù)
BinaryTree(const T* arr, size_t size, const T& invalid)//arr為結(jié)點(diǎn)數(shù)組，size為結(jié)點(diǎn)個(gè)數(shù)，invalid非法值
:_root(NULL)
{
size_t index = 0;//index指向結(jié)點(diǎn)的位置
_root = _CreateTree(arr, size, invalid, index);
}
//拷貝構(gòu)造
BinaryTree<T>(const BinaryTree<T>& t)
: _root(NULL)
{
_root = _Copy(t._root);
}
////賦值運(yùn)算符重載的傳統(tǒng)寫法
//BinaryTree<T>& operator=(const BinaryTree<T>& t)
//{
// if (&t != this)
// {
// _Copy(t._root);
// _Destroy(_root);
// }
// return *this;
//}
//賦值運(yùn)算符重載的現(xiàn)代寫法
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(this->_root, t._root);
return *this;
}
//析構(gòu)函數(shù)
~BinaryTree()
{
if (_root)
{
_Destroy(_root);
}
}
//前序遍歷
void PreOrder()
{
_PrevOrder(_root);
cout << endl;
}
//前序遍歷非遞歸寫法
void PreOrderNon_R()
{
_PrevOrderNon_R(_root);
cout << endl;
}
//中序遍歷
void InOrder()
{
_InOrder(_root);
cout << endl;
}
//中序遍歷非遞歸寫法
void InOrderNon_R()
{
_InOrderNon_R(_root);
cout << endl;
}
//后序遍歷
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
//后序遍歷非遞歸寫法
void PostOrderNon_R()
{
_PostOrderNon_R(_root);
cout << endl;
}
//層序遍歷
void LevelOrder()
{
_LevelOrder(_root);
cout << endl;
}
//節(jié)點(diǎn)數(shù)
size_t Size()
{
return _Size(_root);
}
//深度（高度）
size_t Depth()
{
return _Depth(_root);
}
//葉子結(jié)點(diǎn)數(shù)（葉結(jié)點(diǎn):沒有后繼的結(jié)點(diǎn)）
size_t LeafSize()
{
return _LeafSize(_root);
}
//第k層節(jié)點(diǎn)數(shù)
size_t kLevelSize(int k)
{
return _kLevelSize(_root, k);
}
//此處用protected和private都可，protected可被繼承，private不能被繼承，提高安全性
private:
Node* _CreateTree(const T* arr, size_t size, const T& invalid, size_t& index)
{
Node* root = NULL;
if (index < size&&arr[index] != invalid)
{
root = new Node(arr[index]);
root->_left = _CreateTree(arr, size, invalid, ++index);
root->_right = _CreateTree(arr, size, invalid, ++index);
}
return root;
}
Node* _Copy(Node* troot)
{
if (troot == NULL)
{
return NULL;
}
Node* root = new Node(troot->_data);
root->_left = _Copy(troot->_left);
root->_right = _Copy(troot->_right);
return root;
}
void _Destroy(Node* root)
{
if (root == NULL)
{
return;
}
if (root->_left == NULL&&root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destroy(root->_left);
_Destroy(root->_right);
}
//方法1：后序遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)
size_t _LeafSize(Node* root)
{
static int size = 0;
if (root == NULL)
{
return size;
}
if (root->_left == NULL&&root->_right == NULL)
{
size++;
return size;
}
_LeafSize(root->_left);
_LeafSize(root->_right);
}
////方法2：后序遞歸遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)
//size_t _LeafSize(Node* root)
//{
// if (root == NULL)
// {
// return 0;
// }
// else if (root->_left == NULL&&root->_right == NULL)
// {
// return 1;
// }
// else
// {
// return _LeafSize(root->_left) + _LeafSize(root->_right);
// }
//}
size_t _Size(Node* root)
{
if (root == NULL)
{
return 0;
}
return _Size(root->_left) + _Size(root->_right) + 1;
}
size_t _Depth(Node* root)
{
if (root == NULL)
{
return 0;
}
int LeftDepth = _Depth(root->_left);
int RightDepth = _Depth(root->_right);
return (LeftDepth>RightDepth) ? LeftDepth + 1 : RightDepth + 1;
}
size_t _kLevelSize(Node* root, int k)//默認(rèn)根結(jié)點(diǎn)為第1層
{
assert(k > 0);
if (root == NULL)
{
return 0;
}
if (k == 1)
{
return 1;
}
return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);
}
//先序遍歷：根結(jié)點(diǎn)->左子樹->右子樹
void _PrevOrder(Node* root)
{
if (root == NULL)
{
return;
}
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
//先序遍歷非遞歸,根結(jié)點(diǎn)->左子樹->右子樹，利用棧"后進(jìn)先出"特點(diǎn)實(shí)現(xiàn)
void _PrevOrderNon_R(Node* root)
{
stack<Node*>s;
if (root == NULL)
{
return;
}
s.push(root);
while (!s.empty())
{
root = s.top();
cout << root->_data << " ";
s.pop();
if (root->_right)//注意要先壓入右結(jié)點(diǎn)，才能讓右結(jié)點(diǎn)后出
{
s.push(root->_right);
}
if (root->_left)
{
s.push(root->_left);
}
}
}
//中序遍歷：左子樹->根結(jié)點(diǎn)->右子樹
void _InOrder(Node* root)
{
if (root == NULL)
{
return;
}
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
//中序遍歷非遞歸,最左結(jié)點(diǎn)cur是要訪問的第一個(gè)結(jié)點(diǎn)，先把左壓進(jìn)去，然后把右樹當(dāng)成子樹
void _InOrderNon_R(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*>s;
Node* cur = root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子
cout << s.top()->_data << " ";
s.pop();
if (cur->_right == NULL)
{
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
//后序遍歷：左子樹->右子樹->根結(jié)點(diǎn)
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
//后序遍歷非遞歸：左子樹->右子樹->根結(jié)點(diǎn),prev指向上一個(gè)剛剛訪問過的結(jié)點(diǎn)
void _PostOrderNon_R(Node* root)
{
if (root == NULL)
{
return;
}
stack<Node*>s;
Node* cur = root;
Node* prev = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子
//無右孩子和右孩子是剛剛被訪問過的結(jié)點(diǎn)，此時(shí)應(yīng)該訪問根結(jié)點(diǎn)
if (cur->_right == NULL || cur->_right == prev)
{
cout << cur->_data << " ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;//除上面兩種情況，均不訪問根，繼續(xù)遍歷右子樹
}
}
}
//層序遍歷
void _LevelOrder(Node* root)
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);
while (!q.empty())
{
if (q.front()->_left != NULL)
{
q.push(q.front()->_left);
}
if (q.front()->_right != NULL)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " ";
q.pop();
}
}
private:
Node* _root;
};
void TestBinaryTree()
{
int arr1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };
cout << "打印此二叉樹："<<endl;
cout << " "<<arr1[0] <<endl;
cout << " " << arr1[1] << " " << arr1[8] << endl;
cout << arr1[2] << " " << arr1[5] << " " << arr1[9] << endl;
BinaryTree<int>t1(arr1, 10, '#');
cout << "先序遍歷：";
t1.PreOrder();
cout << "先序非遞歸遍歷：";
t1.PreOrderNon_R();
cout << "中序遍歷：";
t1.InOrder();
cout << "中序非遞歸遍歷：";
t1.InOrderNon_R();
cout << "后序遍歷：";
t1.PostOrder();
cout << "后序非遞歸遍歷：";
t1.PostOrderNon_R();
cout << "層序遍歷：";
t1.LevelOrder();
cout << "結(jié)點(diǎn)的總數(shù)：";
cout << t1.Size() << endl;
cout << "樹的深度：";
cout << t1.Depth() << endl;
cout << "葉結(jié)點(diǎn)的個(gè)數(shù)：";
cout << t1.LeafSize() << endl;
cout << "第3層結(jié)點(diǎn)的個(gè)數(shù)：";
cout << t1.kLevelSize(3) << endl;
}
int main()
{
TestBinaryTree();
system("pause");
return 0;
}
運(yùn)行結(jié)果：
打印此二叉樹：
1
2 5
3 4 6
先序遍歷：1 2 3 4 5 6
先序非遞歸遍歷：1 2 3 4 5 6
中序遍歷：3 2 4 1 6 5
中序非遞歸遍歷：3 2 4 1 6 5
后序遍歷：3 4 2 6 5 1
后序非遞歸遍歷：3 4 2 6 5 1
層序遍歷：1 2 5 3 4 6
結(jié)點(diǎn)的總數(shù)：6
樹的深度：3
葉結(jié)點(diǎn)的個(gè)數(shù)：3
第3層結(jié)點(diǎn)的個(gè)數(shù)：3
請(qǐng)按任意鍵繼續(xù). . .
免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。
億速云公眾號(hào)
手機(jī)網(wǎng)站二維碼
