【數(shù)據(jù)結構】二叉樹-創(chuàng)新互聯(lián)
二叉樹概念
在計算機科學中，二叉樹是每個節(jié)點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現(xiàn)二叉查找樹和二叉堆。
二 叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k 的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數(shù)為n_0，度為2的結點數(shù)為n_2，則n_0=n_2+1。
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數(shù)都達到大個數(shù)，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
二叉樹性質
(1) 在非空二叉樹中，第i層的結點總數(shù)不超過2^(i-1) , i>=1；
(2) 深度為h的二叉樹最多有2^h - 1 個結點(h>=1)，最少有h個結點；
(3) 對于任意一棵二叉樹，如果其葉結點數(shù)為N0，而度數(shù)為2的結點總數(shù)為N2，則N0=N2+1；
(4) 具有n個結點的完全二叉樹的深度為log 2 (n+1) [ log 以2為底的 n+1 ]
存儲結構：順序存儲，鏈式存儲
遍歷方式：前序遍歷，中序遍歷，后序遍歷
前序遍歷：
void _PreOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_data << " ";
_PreOrder(root->_left);
_PreOrder(root->_right);
}中序遍歷：
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}后序遍歷：
void _PostOrder(Node* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}此外，對于二叉樹的操作還有：
樹的深度Depth()
樹的大小Size()
葉子結點的個數(shù)LeafSize()
K層也加點個數(shù) GetKLevel()
實現(xiàn)如下：
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;
}Size()：
size_t _Size(Node* root)
{
if (root == NULL)
return 0;
return _Size(root->_left) + _Size(root->_right) + 1;
}LeafSize()：
void _LeafSize(Node* root, size_t& size) // size需傳引用，以保證每次在上次的調用加值，否則size結果為0
{
if (root == NULL)
return;
if (root->_left == NULL && root->_right == NULL)
{
++size;
return;
}
_LeafSize(root->_left,size);
_LeafSize(root->_right, size);
}GetKLevel()：
void _GetKLevel(Node* root, int k,
size_t level, size_t& kSize)
{
if (root == NULL)
{
return;
}
if (level == k)
{
++kSize;
return;
}
_GetKLevel(root->_left, k, level + 1, kSize);
_GetKLevel(root->_right, k, level + 1, kSize);
}至此，二叉樹的基本操作已經(jīng)完成。
我們發(fā)現(xiàn)在實現(xiàn)二叉樹的前序，中序，后序遍歷時都是利用遞歸的機制，那么非遞歸又是怎么實現(xiàn)的呢？
在此，寫出三種不同遍歷方式的非遞歸方式實現(xiàn)：
前序遍歷（非遞歸）：
void _PreOrder_NoR()
{
stack<Node*> s;
if (_root)
{
s.push(_root);
}
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
if (top->_right) // 先壓右樹，后壓左樹
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
}中序遍歷（非遞歸）：
void _InOrder_NoR()
{
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
// 1.壓一棵樹的左路節(jié)點，直到最左節(jié)點
s.push(cur);
cur = cur->_left;
}
// 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環(huán)此操作，直至棧為空
if (!s.empty())
{
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur = top->_right;
}
}
}后序遍歷（非遞歸）：
void _PostOrder_NoR()
{
Node* pre = NULL;
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == pre)
{
cout << top->_data << " ";
s.pop();
pre = top;
}
else
{
cur = top->_right;
}
}
}發(fā)現(xiàn)，非遞歸的實現(xiàn)是利用棧結構存儲和管理二叉樹的。
附源代碼以及測試代碼：
BinaryTree.h 文件：
#pragma once
#include <stack>
template <class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode<T>* _left;
BinaryTreeNode<T>* _right;
BinaryTreeNode(const T& x)
: _data(x)
, _left(NULL)
, _right(NULL)
{}
};
template <class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)
{
size_t index = 0;
_root = _CreatBinaryTree( a, size, index, invalid);
}
BinaryTree(const BinaryTree<T>& t)
{
_root = _Copy(t._root);
}
//BinaryTree<T>& operator=(const BinaryTree<T>& t)
//{
// if (this != &t)
// {
// Node* tmp = _Copy(t._root);
// _Destory(_root);
// _root = tmp;
// }
// return *this;
//}
BinaryTree<T>& operator=(BinaryTree<T> t)
{
swap(this->_root, t._root);
return *this;
}
~BinaryTree()
{
_Destory(_root);
_root = NULL;
}
void PreOrder()
{
_PreOrder(_root);
cout << endl;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}
void PostOrder()
{
_PostOrder(_root);
cout << endl;
}
size_t Size()
{
return _Size(_root);
}
size_t Depth()
{
return _Depth(_root);
}
size_t LeafSize()
{
size_t size = 0;
_LeafSize(_root,size);
return size;
}
size_t GetKLevel(int k)
{
size_t kSize = 0;
size_t level = 1;
_GetKLevel(_root,k,level,kSize);
return kSize;
}
void PreOrder_NoR()
{
_PreOrder_NoR();
cout << endl;
}
void InOrder_NoR()
{
_InOrder_NoR();
cout << endl;
}
void PostOrder_NoR()
{
_PostOrder_NoR();
cout << endl;
}
protected:
void _Destory(Node* root)
{
if (root == NULL)
{
return;
}
_Destory(root->_left);
_Destory(root->_right);
delete root;
}
Node* _Copy(Node* root)
{
if (root == NULL)
{
return NULL;
}
Node* newRoot = new Node(root->_data);
newRoot->_left = _Copy(root->_left);
newRoot->_right = _Copy(root->_right);
return newRoot;
}
Node* _CreatBinaryTree(const T* a, size_t size,
size_t& index, const T& invalid)
{
Node* root = NULL;
while (index < size && a[index] != invalid)
{
root = new Node(a[index]); // new并初始化
root->_left = _CreatBinaryTree( a, size, ++index, invalid);
root->_right = _CreatBinaryTree( a, size, ++index, invalid);
}
return root;
}
void _PreOrder(Node* root)
{
if (root == NULL)
return;
cout << root->_data << " ";
_PreOrder(root->_left);
_PreOrder(root->_right);
}
void _InOrder(Node* root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
void _PostOrder(Node* root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
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;
}
void _LeafSize(Node* root, size_t& size) // size需傳引用，以保證每次在上次的調用加值，否則size結果為0
{
if (root == NULL)
return;
if (root->_left == NULL && root->_right == NULL)
{
++size;
return;
}
_LeafSize(root->_left,size);
_LeafSize(root->_right, size);
}
void _GetKLevel(Node* root, int k,
size_t level, size_t& kSize)
{
if (root == NULL)
{
return;
}
if (level == k)
{
++kSize;
return;
}
_GetKLevel(root->_left, k, level + 1, kSize);
_GetKLevel(root->_right, k, level + 1, kSize);
}
void _PreOrder_NoR() // 前序遍歷->非遞歸
{
stack<Node*> s;
if (_root)
{
s.push(_root);
}
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
if (top->_right) // 先壓右樹，后壓左樹
{
s.push(top->_right);
}
if (top->_left)
{
s.push(top->_left);
}
}
}
void _InOrder_NoR()
{
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
// 1.壓一棵樹的左路節(jié)點，直到最左節(jié)點
s.push(cur);
cur = cur->_left;
}
// 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環(huán)此操作，直至棧為空
if (!s.empty())
{
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur = top->_right;
}
}
}
void _PostOrder_NoR()
{
Node* pre = NULL;
Node* cur = _root;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == pre)
{
cout << top->_data << " ";
s.pop();
pre = top;
}
else
{
cur = top->_right;
}
}
}
protected:
Node* _root;
};Test.cpp 文件：
#include <iostream>
using namespace std;
#include "BinaryTree.h"
int main()
{
int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> t( a, 10, '#');
cout << t.Depth() << endl;
cout << t.Size() << endl;
t.PreOrder();
t.InOrder();
t.PostOrder();
cout<< t.GetKLevel(1) << endl;
cout << t.GetKLevel(3) << endl;
cout << t.LeafSize() << endl;
t.PreOrder_NoR();
t.InOrder_NoR();
t.PostOrder_NoR();
system("pause");
return 0;
}若有紕漏，歡迎指正。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務器，動態(tài)BGP最優(yōu)骨干路由自動選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡助力業(yè)務部署。公司持有工信部辦法的idc、isp許可證， 機房獨有T級流量清洗系統(tǒng)配攻擊溯源，準確進行流量調度，確保服務器高可用性。佳節(jié)活動現(xiàn)已開啟，新人活動云服務器買多久送多久。
網(wǎng)站欄目：【數(shù)據(jù)結構】二叉樹-創(chuàng)新互聯(lián)
網(wǎng)頁鏈接：http://bm7419.com/article32/dgohpc.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián)，為您提供移動網(wǎng)站建設、品牌網(wǎng)站設計、企業(yè)網(wǎng)站制作、虛擬主機、網(wǎng)站營銷、電子商務
聲明：本網(wǎng)站發(fā)布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經(jīng)允許不得轉載，或轉載時需注明來源： 創(chuàng)新互聯(lián)
猜你還喜歡下面的內容
- 企業(yè)網(wǎng)站建設注冊域名的重要性 2016-11-09
- 成都網(wǎng)站制作淺析注冊域名需要哪些資料？ 2016-08-18
- 注冊域名后接下來怎么建站？ 2016-05-19
- 如何申請域名域名注冊方法_深圳網(wǎng)站制作公司 2021-12-10
- 如何域名注冊 這些事項要知曉 2016-11-15
- .vip域名注冊優(yōu)勢在哪 2022-07-11
- 品牌網(wǎng)站建設時如何做好對網(wǎng)站域名注冊和維護 2021-10-16
- 域名注冊哪個好？ 2022-08-03
- 域名注冊可以不實名嗎？注冊域名如何進行實名認證？ 2021-03-02
- 網(wǎng)站開發(fā)有哪些流程步驟?先注冊域名嗎 2015-01-23
- 域名注冊有多搶手？ 2023-01-22
- .top域名注冊量躍居全球新頂級域名首位！ 2021-02-28