二叉樹：每個(gè)節(jié)點(diǎn)最多兩個(gè)孩子節(jié)點(diǎn)。
網(wǎng)站建設(shè)哪家好，找
成都創(chuàng)新互聯(lián)公司！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、
微信小程序開發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了
寶雞免費(fèi)建站歡迎大家使用！
二叉樹的結(jié)構(gòu)： struct TreeNode
{
DataType _value; //節(jié)點(diǎn)值
TreeNode* _left; //左孩子
TreeNode* _ridht; //右孩子
};
二叉樹的基礎(chǔ)： 構(gòu)造、拷貝構(gòu)造、析構(gòu)、賦值運(yùn)算符的重載
二叉樹的知識(shí)點(diǎn)： 高度、節(jié)點(diǎn)的個(gè)數(shù)、子節(jié)點(diǎn)的個(gè)數(shù)
二叉樹的遍歷： 前序、中序、后序遍歷(遞歸及非遞歸)
遍歷順序： 前序——根左右 中序——左根右 后序——左右根
注意: 遞歸遍歷時(shí)，應(yīng)該注意不要出現(xiàn)棧溢出現(xiàn)象。
因?yàn)?+index返回對(duì)象，index++返回臨時(shí)變量，所以傳引用做參數(shù)時(shí)有++index。
#pragma once
#include
#include
//二叉樹的結(jié)構(gòu)
template
struct BinaryTreeNode
{
BinaryTreeNode* _left;
BinaryTreeNode* _right;
T _data;
//構(gòu)造函數(shù)
BinaryTreeNode(const T& x)
:_left(NULL)
, _right(NULL)
, _data(x)
{}
};
template
class BinaryTree
{
typedef BinaryTreeNode Node;
public:
//構(gòu)造
BinaryTree()
:_root(NULL)
{}
// a--樹的節(jié)點(diǎn)前序遍歷的數(shù)組 size--數(shù)組中元素個(gè)數(shù) invaild--無效值即節(jié)點(diǎn)為空
BinaryTree(const T* a,size_t size,const T& invalid)
{
size_t index = 0;
_root = _CreateTree(a, size,invalid,index);
}
//析構(gòu)
~BinaryTree()
{
_Destory(_root);
_root = NULL;
}
//拷貝
BinaryTree(const BinaryTree& t)
{
_root = _Copy(t._root);
}
//賦值重載(傳統(tǒng))
//BinaryTree& operator=(const BinaryTree& t)
//{
// if (this != &t)
// {
// Node* tmp = _Copy(t._root);
// _Destory(_root);
// _root = tmp;
// }
// return *this;
//}
//賦值重載(現(xiàn)代)
BinaryTree& operator=(BinaryTree t)
{
swap(_root, t._root);
return *this;
}
T& operator->()
{
return _root;
}
public:
void PrevOrder()//前序
{
_PrevOrder(_root);
cout << endl;
}
void InOrder()//中序
{
_InOrder(_root);
cout << endl;
}
void PostOrder()//后序
{
_PostOrder(_root);
cout << endl;
}
size_t Size() //節(jié)點(diǎn)個(gè)數(shù)
{
return _Size(_root);
}
size_t Depth() //樹的深度
{
return _Depth(_root);
}
size_t LeafSize() //葉子節(jié)點(diǎn)個(gè)數(shù)
{
return _LeafSize(_root);
}
//層次遍歷
void LevelOrder()
{
queue q;
if (_root)
{
q.push(_root);
}
while (!q.empty())
{
Node* front = q.front();
cout << front->_data << " ";
q.pop();
if (front->_left)
{
q.push(front->_left);
}
if (front->_right)
{
q.push(front->_right);
}
}
cout << endl;
}
public:
//非遞歸的前中后序遍歷（棧）
void PrevOrder_NonR()
{
stack s;
if (_root)
s.push(_root);
while (!s.empty())
{
Node* top = s.top();
cout << top->_data << " ";
s.pop();
//棧后進(jìn)先出 ，所以 右先進(jìn)，左先出
if (top->_right)
s.push(top->_right);
if (top->_left)
s.push(top->_left);
}
cout << endl;
}
void InOrder_NonR()
{
//壓左樹
//取出一個(gè)節(jié)點(diǎn)即它的左路走完了，在訪問右樹（看作子問題）
stack s;
Node* cur = _root;
while (cur || !s.empty())
{
//壓樹的左路節(jié)點(diǎn)直至最左段節(jié)點(diǎn)
while (cur)
{
s.push(cur);
cur = cur->_left;
}
if (!s.empty())
{
Node* top = s.top();
s.pop();
cout << top->_data << " ";
cur=top->_right;
}
}
cout << endl;
}
void PostOrder_NonR()
{
Node* prev = NULL;
Node* cur = _root;
stack s;
while (cur || !s.empty())
{
//壓樹的左路節(jié)點(diǎn)直至最左段節(jié)點(diǎn)
while (cur)
{
s.push(cur);
cur = cur->_left;
}
Node* top = s.top();
if (top->_right == NULL || top->_right == prev)
{
cout << top->_data << " ";
s.pop();
prev = top;
}
else
{
cur = top->_right;
}
}
cout << endl;
}
protected:
//注意 此處index要用引用傳參
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t& index)
{
Node* root = NULL;
if ((index < size) && (a[index] != invalid))
{
root = new Node(a[index]);
//注意下面只能用++index。此處傳的是引用
//因?yàn)?+index返回對(duì)象，index++返回臨時(shí)變量。
root->_left = _CreateTree(a, size, invalid, ++index);
root->_right = _CreateTree(a, size, invalid, ++index);
}
return root;
}
void _Destory(Node* root)
{
if (root == NULL)
return;
_Destroy(root->_left);
_Destroy(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;
}
//////////////
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;
return (_Size(root->_left) + _Size(root->_right) + 1);
}
size_t _Depth(Node* root)
{
if (root == NULL)
return 0;
size_t LeftDepth = _Depth(root->_left);
size_t RightDepth = _Depth(root->_right);
return (LeftDepth > RightDepth) ? (LeftDepth + 1) : (RightDepth + 1);
}
size_t _LeafSize(Node* root)
{
if (root == NULL)
return 0;
if ((root->_left == NULL) && (root->_right == NULL))
return 1;
return (_LeafSize(root->_left) + _LeafSize(root->_right));
}
private:
Node *_root;
};
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
網(wǎng)頁標(biāo)題：【C++】二叉樹的基本知識(shí)及其遍歷-創(chuàng)新互聯(lián)
文章地址：
http://weahome.cn/article/diopep.html
重慶分公司
重慶分公司
