C++實現(xiàn)二叉樹基本操作詳解
更新時間：2017年12月06日 11:30:34 作者：tttjp
這篇文章主要為大家詳細介紹了C++實現(xiàn)二叉樹基本操作，具有一定的參考價值，感興趣的小伙伴們可以參考一下
樹是一種重要的非線性數(shù)據(jù)結構，二叉樹是樹型結構的一種重要類型。本學年論文介紹了二叉樹的定義，二叉樹的存儲結構，二叉樹的相關術語，以此引入二叉樹這一概念，為展開二叉樹的基本操作做好理論鋪墊。二叉樹的基本操作主要包含以下幾個模塊：二叉樹的遍歷方法，計算二叉樹的結點個數(shù)，計算二叉樹的葉子結點個數(shù)，二叉樹深度的求解等內(nèi)容。
前序遍歷（遞歸&非遞歸）
- 訪問根節(jié)點
- 前序訪問左子樹
- 前序訪問右子樹
//前序非遞歸
void PrevOrder()
{
stack<Node*> s;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
//此時當前節(jié)點的左子樹已遍歷完畢
Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//前序遞歸
void PrevOrderR()
{
_PrevOrder(_root);
cout << endl;
}
void _PrevOrder(Node *root)
{
if (root == NULL) //必須有遞歸出口?。?！
return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(root->_right);
}
中序遍歷（遞歸&非遞歸）
- 中序訪問左子樹
- 訪問根節(jié)點
- 中序訪問右子樹
//中序非遞歸
void InOrder()
{
stack<Node*> s;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
//此時當前節(jié)點的左子樹已遍歷完畢
Node *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//中序遞歸
void InOrderR()
{
_InOrder(_root);
cout << endl;
}
void _InOrder(Node *root)
{
if (root == NULL)
return;
_InOrder(root->_left);
cout << root->_data << " ";
_InOrder(root->_right);
}
后序遍歷（遞歸&非遞歸）
//后序非遞歸
//后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點
void PostOrder()
{
stack<Node*> s;
Node *cur = _root;
Node *prev = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
if (tmp->_right && tmp->_right != prev)
{
cur = tmp->_right;
}
else
{
cout << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}
//后序遞歸
void PostOrderR()
{
_PostOrder(_root);
cout << endl;
}
void _PostOrder(Node *root)
{
if (root == NULL)
return;
_PostOrder(root->_left);
_PostOrder(root->_right);
cout << root->_data << " ";
}
層序遍歷
從根節(jié)點開始，依次訪問每層結點。
利用隊列先進先出的特性，把每層結點從左至右依次放入隊列。
void LevelOrder() //利用隊列?。?！
{
queue<Node*> q;
Node *front = NULL;
//1.push根節(jié)點
if (_root)
{
q.push(_root);
}
//2.遍歷當前節(jié)點，push當前節(jié)點的左右孩子，pop當前節(jié)點
//3.遍歷當前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空
while (!q.empty())
{
front = q.front();
cout << front->_data << " ";
if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);
q.pop();
}
cout << endl;
}
求二叉樹的高度
size_t Depth()
{
return _Depth(_root);
}
size_t _Depth(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
{
size_t leftDepth = _Depth(root->_left) + 1;
size_t rightDepth = _Depth(root->_right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}
求葉子節(jié)點的個數(shù)
size_t LeafSize()
{
return _LeafSize(_root);
}
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);
}
求二叉樹第k層的節(jié)點個數(shù)
size_t GetKLevel(int k)
{
return _GetKLevel(_root, k);
}
size_t _GetKLevel(Node *root, int k)
{
if (root == NULL)
return 0;
else if (k == 1)
return 1;
else
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}
完整代碼如下：
template<class T>
struct BinaryTreeNode
{
T _data;
BinaryTreeNode *_left;
BinaryTreeNode *_right;
BinaryTreeNode(const T& d)
:_data(d)
, _left(NULL)
, _right(NULL)
{}
};
template<class T>
class BinaryTree
{
public:
typedef BinaryTreeNode<T> Node;
BinaryTree()
:_root(NULL)
{}
BinaryTree(T *arr, size_t n, const T& invalid)
{
size_t index = 0;
_root = _CreateBinaryTree(arr, n, invalid, index);
}
BinaryTree(const BinaryTree<T>& t)
:_root(NULL)
{
_root = _CopyTree(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)
{
if (this != t)
{
Node *tmp = new Node(t._root);
if (tmp != NULL)
{
delete _root;
_root = tmp;
}
}
return *this;
}
~BinaryTree()
{
_DestroyTree(_root);
cout << endl;
}
//前序非遞歸
void PrevOrder()
{
stack<Node*> s;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)
{
cout << cur->_data << " ";
s.push(cur);
cur = cur->_left;
}
//此時當前節(jié)點的左子樹已遍歷完畢
Node *tmp = s.top();
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//前序遞歸
void PrevOrderR()
{
_PrevOrder(_root);
cout << endl;
}
//中序非遞歸
void InOrder()
{
stack<Node*> s;
Node *cur = _root;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
//此時當前節(jié)點的左子樹已遍歷完畢
Node *tmp = s.top();
cout << tmp->_data << " ";
s.pop();
cur = tmp->_right;
}
cout << endl;
}
//中序遞歸
void InOrderR()
{
_InOrder(_root);
cout << endl;
}
//后序非遞歸
//后序遍歷可能會出現(xiàn)死循環(huán)，所以要記錄下前一個訪問的節(jié)點
void PostOrder()
{
stack<Node*> s;
Node *cur = _root;
Node *prev = NULL;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node *tmp = s.top();
if (tmp->_right && tmp->_right != prev)
{
cur = tmp->_right;
}
else
{
cout << tmp->_data << " ";
prev = tmp;
s.pop();
}
}
cout << endl;
}
//后序遞歸
void PostOrderR()
{
_PostOrder(_root);
cout << endl;
}
void LevelOrder() //利用隊列?。?！
{
queue<Node*> q;
Node *front = NULL;
//1.push根節(jié)點
if (_root)
{
q.push(_root);
}
//2.遍歷當前節(jié)點，push當前節(jié)點的左右孩子，pop當前節(jié)點
//3.遍歷當前節(jié)點的左孩子，再遍歷右孩子，循環(huán)直至隊列為空
while (!q.empty())
{
front = q.front();
cout << front->_data << " ";
if (front->_left)
q.push(front->_left);
if (front->_right)
q.push(front->_right);
q.pop();
}
cout << endl;
}
size_t Size()
{
return _Size(_root);
}
size_t LeafSize()
{
return _LeafSize(_root);
}
size_t GetKLevel(int k)
{
return _GetKLevel(_root, k);
}
size_t Depth()
{
return _Depth(_root);
}
Node* Find(const T& d)
{
return _Find(_root, d);
}
protected:
Node* _CreateBinaryTree(T *arr, size_t n, const T& invalid, size_t& index)
{
Node *root = NULL;
if (index < n && arr[index] != invalid)
{
root = new Node(arr[index]);
index++;
root->_left = _CreateBinaryTree(arr, n, invalid, index);
index++;
root->_right = _CreateBinaryTree(arr, n, invalid, index);
}
return root;
}
Node* _CopyTree(Node *root)
{
Node *newRoot = NULL;
if (root)
{
newRoot = new Node(root->_data);
newRoot->_left = _CopyTree(root->_left);
newRoot->_right = _CopyTree(root->_right);
}
return newRoot;
}
void _DestroyTree(Node *root)
{
if (root)
{
_Destroy(root->_left);
_Destroy(root->_right);
delete root;
}
}
void _PrevOrder(Node *root)
{
if (root == NULL) //必須有遞歸出口?。?！
return;
cout << root->_data << " ";
_PrevOrder(root->_left);
_PrevOrder(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;
else
return _Size(root->_left) + _Size(root->_right) + 1;
}
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 _GetKLevel(Node *root, int k)
{
if (root == NULL)
return 0;
else if (k == 1)
return 1;
else
return _GetKLevel(root->_left, k - 1) + _GetKLevel(root->_right, k - 1);
}
size_t _Depth(Node *root)
{
if (root == NULL)
return 0;
else if (root->_left == NULL && root->_right == NULL)
return 1;
else
{
size_t leftDepth = _Depth(root->_left) + 1;
size_t rightDepth = _Depth(root->_right) + 1;
return leftDepth > rightDepth ? leftDepth : rightDepth;
}
}
Node* _Find(Node *root, const T& d)
{
if (root == NULL)
return NULL;
else if (root->_data == d)
return root;
else if (Node *ret = _Find(root->_left, d))
return ret;
else
_Find(root->_right, d);
}
protected:
Node *_root;
};
以上就是本文的全部內(nèi)容，希望對大家的學習有所幫助，也希望大家多多支持腳本之家。
相關文章
這篇文章主要介紹了C++模擬實現(xiàn)stack和Queue的操作示例,文中通過代碼示例給大家介紹的非常詳細,對大家的學習或工作有一定的幫助,需要的朋友可以參考下2024-06-06
這篇文章主要介紹了opencv車道線檢測的實現(xiàn)方法，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-08-08
這篇文章主要為大家介紹了如何實現(xiàn)C語言常用字符串庫函數(shù)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2021-11-11
這篇文章主要為大家詳細介紹了C++控制臺實現(xiàn)貪吃蛇，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-04-04
析構函數(shù)：在撤銷對象占用的內(nèi)存之前，進行一些操作的函數(shù)。析構函數(shù)不能被重載，只能有一個2013-09-09
這篇文章主要為大家詳細介紹了基于C語言實現(xiàn)簡單的掃雷小游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-11-11
這篇文章給大家介紹了c++使用正則表達式提取關鍵字的方法，相對來說比較簡單，同時給大家提到了c++通過正則表達式提取匹配到的字符串的方法，非常不錯，具有一定的參考借鑒價值，需要的朋友參考下吧2018-08-08
這篇文章主要介紹了C++ 中函數(shù)重載、覆蓋與隱藏詳解的相關資料,需要的朋友可以參考下2017-05-05
C++對cin輸入字符的判斷及分段函數(shù)處理方法示例
這篇文章主要介紹了C++對cin輸入字符的判斷及分段函數(shù)處理方法,結合實例形式分析了C++輸入判斷及處理相關操作技巧,需要的朋友可以參考下2017-09-09
這篇文章主要為大家詳細介紹了C/C++實現(xiàn)投骰子游戲，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2020-11-11