二叉樹:二叉樹是一棵特殊的樹，二叉樹每個(gè)節(jié)點(diǎn)最多有兩個(gè)孩子結(jié)點(diǎn)，分別稱為左孩子和右孩子。

在合山等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都網(wǎng)站建設(shè)、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作按需設(shè)計(jì)網(wǎng)站,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),高端網(wǎng)站設(shè)計(jì),網(wǎng)絡(luò)營銷推廣,成都外貿(mào)網(wǎng)站建設(shè),合山網(wǎng)站建設(shè)費(fèi)用合理。

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>
#include<assert.h>
#include<stack>
#include<queue>

using namespace std;
//節(jié)點(diǎn)結(jié)構(gòu)
template<class T>
class BinaryTreeNode//節(jié)點(diǎn)
{
public:
BinaryTreeNode(const T& data)
:_data(data)
,_left(NULL)
,_right(NULL)
{}
T _data;//值
BinaryTreeNode* _left;//左子樹
BinaryTreeNode* _right;//右子樹
};
template<class T>
class BinaryTree
{
typedef BinaryTreeNode<T> Node;
public:
BinaryTree()//無參構(gòu)造函數(shù)
:_root(NULL)
{}
BinaryTree(const T* a, size_t size, const T& invalid)//構(gòu)造函數(shù)
{
assert(a);
size_t index = 0;
_root = _CreateTree(a, size, invalid, index);
}
BinaryTree(const BinaryTree<T>& t)//拷貝構(gòu)造
{
_root = _Copy(t._root);
}
BinaryTree<T>& operator=(const BinaryTree<T>& t)//賦值函數(shù)
{
if (this != &t)
{
BinaryTreeNode<T>* tmp = _Copy(t._root);
_Destroy(_root);
_root = temp;
}
return *this;
}
~BinaryTree()//析構(gòu)
{
_Destroy(_root);
_root = NULL;
}
public:
void PrevOrder()//先根遍歷
{
cout << "先根遍歷:";
_PrevOrder(_root);
cout << endl;
}
void InOrder()//中根遍歷
{
cout << "中根遍歷:";
_InOrder(_root);
cout << endl;
}
void PostOrder()//后根遍歷
{
cout << "后根遍歷:";
_PostOrder(_root);
cout << endl;
}
void LevelOrder()//層次遍歷
{
cout << "層次遍歷:";
_LevelOrder(_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);
}
protected:
Node* _CreateTree(const T* a, size_t size, const T& invalid, size_t&  index)
//index要傳引用，需要更改index的值
{
Node* root = NULL;
//判斷數(shù)組是否越界和輸入的值是否合法
if (index < size&&a[index] != invalid)
{
root = new Node(a[index]);//創(chuàng)建根節(jié)點(diǎn)
root->_left = _CreateTree(a, size, invalid, ++index);//遞歸創(chuàng)建左子樹
root->_right = _CreateTree(a, size, invalid, ++index);//遞歸創(chuàng)建右子樹
}
return root;//返回根節(jié)點(diǎn)
}
//void _PrevOrder(Node* root)
//{
////如果節(jié)點(diǎn)為空則直接返回
//if (root == NULL)
//{
//return;
//}
//cout << root->_data << " ";//訪問根節(jié)點(diǎn)
//_PrevOrder(root->_left);//遞歸訪問左子樹
//_PrevOrder(root->_right);//遞歸訪問右子樹
//}
void _PrevOrder(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)
{
s.push(root->_right);
}
if (root->_left)
{
s.push(root->_left);
}
}
}
//void _InOrder(Node* root)
//{
////如果節(jié)點(diǎn)為空則直接返回
//if (root == NULL)
//{
//return;
//}
//_InOrder(root->_left);//遞歸訪問左子樹
//cout << root->_data << " ";//遞歸訪問根節(jié)點(diǎn)
//_InOrder(root->_right);//遞歸訪問右子樹
//}
void _InOrder(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;
}
}
}
//void _PostOrder(Node* root)
//{
//if(root == NULL)
//{
//return;
//}
//_PostOrder(root->_left);//遞歸訪問左子樹
//_PostOrder(root->_right);//遞歸訪問右子樹
//cout << root->_data << " ";//遞歸訪問根節(jié)點(diǎn)
//}
void _PostOrder(Node* root)
{
if (root == NULL)
{
return;
}
Node* cur = root;
Node* prev = NULL;
stack<Node*> s;
while (cur || !s.empty())
{
while (cur)
{
s.push(cur);
cur = cur->_left;
}
cur = s.top();
if (cur->_right == NULL || cur->_right == prev)
{
cout << cur->_data << " ";
s.pop();
prev = cur;
cur = NULL;
}
else
{
cur = cur->_right;
}
}
}
void  _Destory(Node* root)//析構(gòu)---相當(dāng)于后序刪除
{
if (root == NULL)
{
return;
}
//刪除葉結(jié)點(diǎn)
if (root->_left== NULL&&root->_right == NULL)
{
delete root;
root = NULL;
return;
}
_Destory(root->_left);//遞歸刪除左子樹
_Destory(root->_right);//遞歸刪除右子樹
delete root;
}
size_t _Size(Node* root)//節(jié)點(diǎn)的個(gè)數(shù)
{
size_t count = 0;
if (root == NULL)
{
return count;//樹為空
}
count = _Size(root->_left) + _Size(root->_right);
return count + 1;
}
size_t _Depth(Node* root)//樹的深度
{
size_t left = 0;
size_t right = 0;
size_t max = 0;
if (root == 0)
{
return 0;
}
else
{
left = _Depth(root->_left);
right = _Depth(root->_right);
max = left > right ? left : right;
return max + 1;
}
}
size_t _LeafSize(Node* root)//葉子節(jié)點(diǎn)的個(gè)數(shù)
{
if (root == NULL)
{
return 0;
}
if (root->_left == NULL && root->_right == NULL)
{
return 1;
}
return _LeafSize(root->_left) + _LeafSize(root->_right);
}
Node* _Copy(Node* root)
{
if (roo == NULL)
{
return;
}
Node* newroot = new Node(root->_data);
newroot->_left = Copy(root->_left);
newroot->_right = Copy(root->_right);
return newroot;
}
void _LevelOrder(Node* root)//層次遍歷
{
queue<Node*> q;
if (root == NULL)
{
return;
}
q.push(root);//根節(jié)點(diǎn)入隊(duì)
while (!q.empty())//當(dāng)隊(duì)列不為空
{
if (q.front()->_left)
{
q.push(q.front()->_left);
}
if (q.front()->_right)
{
q.push(q.front()->_right);
}
cout << q.front()->_data << " ";
q.pop();
}
cout << endl;
}
private:
Node* _root;//根節(jié)點(diǎn)
};
void Test()
{
int a[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 };
BinaryTree<int> b(a, 10, '#');
b.PrevOrder();
b.InOrder();
b.PostOrder();
b.LevelOrder();
cout << "size:" << b.Size() << endl;
cout << "depth:" << b.Depth() << endl;
cout << "leafSize:" << b.LeafSize() << endl;
}
int main()
{
Test();
getchar();
return 0;
}

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章名稱：二叉樹的相關(guān)操作-創(chuàng)新互聯(lián)
URL分享：http://www.rwnh.cn/article2/joiic.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供響應(yīng)式網(wǎng)站、軟件開發(fā)、網(wǎng)頁設(shè)計(jì)公司、微信公眾號(hào)、外貿(mào)網(wǎng)站建設(shè)、面包屑導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)