溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
二叉樹概念
在計算機科學中，二叉樹是每個節點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實現二叉查找樹和二叉堆。
二 叉樹的每個結點至多只有二棵子樹(不存在度大于2的結點)，二叉樹的子樹有左右之分，次序不能顛倒。二叉樹的第i層至多有2^{i-1}個結點；深度為k 的二叉樹至多有2^k-1個結點；對任何一棵二叉樹T，如果其終端結點數為n_0，度為2的結點數為n_2，則n_0=n_2+1。
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，并且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
(1) 在非空二叉樹中，第i層的結點總數不超過2^(i-1) , i>=1；
(2) 深度為h的二叉樹最多有2^h - 1 個結點(h>=1)，最少有h個結點；
(3) 對于任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為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()
葉子結點的個數LeafSize()
K層也加點個數 GetKLevel()
實現如下：
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);
}至此，二叉樹的基本操作已經完成。
我們發現在實現二叉樹的前序，中序，后序遍歷時都是利用遞歸的機制，那么非遞歸又是怎么實現的呢？
在此，寫出三種不同遍歷方式的非遞歸方式實現：
前序遍歷（非遞歸）：
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.壓一棵樹的左路節點，直到最左節點
s.push(cur);
cur = cur->_left;
}
// 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環此操作，直至棧為空
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;
}
}
}發現，非遞歸的實現是利用棧結構存儲和管理二叉樹的。
附源代碼以及測試代碼：
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.壓一棵樹的左路節點，直到最左節點
s.push(cur);
cur = cur->_left;
}
// 2.棧不為空，出棧訪問，并移向右樹，判斷右樹是否為空，后循環此操作，直至棧為空
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;
}若有紕漏，歡迎指正。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
