二叉樹(shù)：樹(shù)的每個(gè)節(jié)點(diǎn)最多有兩個(gè)子節(jié)點(diǎn)。

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來(lái)自于我們對(duì)這個(gè)行業(yè)的熱愛(ài)。我們立志把好的技術(shù)通過(guò)有效、簡(jiǎn)單的方式提供給客戶，將通過(guò)不懈努力成為客戶在信息化領(lǐng)域值得信任、有價(jià)值的長(zhǎng)期合作伙伴，公司提供的服務(wù)項(xiàng)目有：域名申請(qǐng)、虛擬空間、營(yíng)銷(xiāo)軟件、網(wǎng)站建設(shè)、驛城網(wǎng)站維護(hù)、網(wǎng)站推廣。

1.實(shí)現(xiàn)二叉鏈表的結(jié)構(gòu)：

//節(jié)點(diǎn)結(jié)構(gòu)

template<class T>

struct  BinaryTreeNode

{

BinaryTreeNode<T>* _left;//左子樹(shù)

BinaryTreeNode<T>* _right;//右子樹(shù)

T _data;//數(shù)據(jù)域

//構(gòu)造函數(shù)

BinaryTreeNode(const T& x)

:_left(NULL)//左孩子指針

,_right(NULL)//右孩子指針

,_data(x)//數(shù)據(jù)域

{}

};

2.求二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)_LeafSize:

葉結(jié)點(diǎn)：無(wú)后繼結(jié)點(diǎn)的結(jié)點(diǎn)。

方法一：設(shè)置一下全局變量或者靜態(tài)變量的size，遍歷二叉樹(shù)，每次遇到一個(gè)節(jié)點(diǎn)就加加一次size；

方法二：遞歸實(shí)現(xiàn)，總?cè)~結(jié)點(diǎn)數(shù)=左子樹(shù)葉結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)葉結(jié)點(diǎn)個(gè)數(shù)。

//方法1：后序遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)

size_t _LeafSize(Node* root)

{

static int size = 0;

if (root == NULL)

{

return size;

}

if (root->_left == NULL&&root->_right == NULL)

{

size++;

return size;

}

_LeafSize(root->_left);

_LeafSize(root->_right);

}

//方法2：后序遞歸遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)

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);

}

}

3.求二叉樹(shù)的深度_depth:

深度也稱(chēng)作為高度，就是左子樹(shù)和右子樹(shù)深度的較大值。

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;

}

4.求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)_size:

總結(jié)點(diǎn)數(shù)=左子樹(shù)結(jié)點(diǎn)個(gè)數(shù)+右子樹(shù)結(jié)點(diǎn)個(gè)數(shù)+根結(jié)點(diǎn)個(gè)數(shù)1

size_t _Size(Node* root)

{

if (root == NULL)

{

return 0;

}

return _Size(root->_left) + _Size(root->_right) + 1;

}

5.求第k層節(jié)點(diǎn)數(shù)：（默認(rèn)根節(jié)點(diǎn)為第1層）

方法與求葉結(jié)點(diǎn)同理。

size_t _kLevelSize(Node* root, int k)//默認(rèn)根結(jié)點(diǎn)為第1層

{

assert(k > 0);

if (root == NULL)

{

return 0;

}

if (k == 1)

{

return 1;

}

return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);

}

6.遍歷二叉樹(shù)：

6.1先序遍歷：訪問(wèn)根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)

//先序遍歷：根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

cout << root->_data << " ";

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

6.2先序遍歷非遞歸寫(xiě)法：

    用棧模擬前序遍歷，棧的特點(diǎn)是后進(jìn)先出，則將無(wú)條件地入棧根結(jié)點(diǎn)，在彈出根結(jié)點(diǎn)之前依次將根結(jié)點(diǎn)的右孩子結(jié)點(diǎn)和左孩子結(jié)點(diǎn)入棧。

//先序遍歷非遞歸,根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)，利用棧"后進(jìn)先出"特點(diǎn)實(shí)現(xiàn)

void _PrevOrderNon_R(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)//注意要先壓入右結(jié)點(diǎn)，才能讓右結(jié)點(diǎn)后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

6.3中序遍歷：訪問(wèn)左子樹(shù)->根結(jié)點(diǎn)->右子樹(shù)

//中序遍歷：左子樹(shù)->根結(jié)點(diǎn)->右子樹(shù)

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

6.4中序遍歷非遞歸寫(xiě)法：

二叉樹(shù)：

   1

  2    5

3  4  6

1、借助棧實(shí)現(xiàn)，先順著二叉樹(shù)找到最左邊且最下邊的結(jié)點(diǎn)3（一邊找一邊入棧），此時(shí)入棧序列為1，2，3。

2、按照中序遍歷要彈出棧頂元素3，則彈出棧頂元素3。

3、接著是右子樹(shù)，判斷它的右子樹(shù)是否為空， 若為空，往回返，打印2，彈出棧頂元素2；若不為空，    該右子樹(shù)，指針指向右子樹(shù)結(jié)點(diǎn)，再重復(fù)之前的步驟1，2，3。

//中序遍歷非遞歸,最左結(jié)點(diǎn)cur是要訪問(wèn)的第一個(gè)結(jié)點(diǎn)，先把左壓進(jìn)去，然后把右樹(shù)當(dāng)成子樹(shù)

void _InOrderNon_R(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;

}

}

}

6.5后序遍歷：訪問(wèn)左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn)

//后序遍歷：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn)

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

6.6后序遍歷非遞歸寫(xiě)法：

1、后序遍歷同樣借助棧實(shí)現(xiàn)，先找到最左邊且為最下面的結(jié)點(diǎn)3（一邊入棧一邊找）；

2、結(jié)點(diǎn)3若沒(méi)有右孩子，打印節(jié)點(diǎn)3，之后彈出棧頂結(jié)點(diǎn)3；

3、結(jié)點(diǎn)3若有右孩子，繼續(xù)遍歷它的右子樹(shù)，等遍歷結(jié)束才可打印3。遍歷重復(fù)步驟1,2,3

//后序遍歷非遞歸：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn),prev指向上一個(gè)剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)

void _PostOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stack<Node*>s;

Node* cur = root;

Node* prev = NULL;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子

//無(wú)右孩子和右孩子是剛剛被訪問(wèn)過(guò)的結(jié)點(diǎn)，此時(shí)應(yīng)該訪問(wèn)根結(jié)點(diǎn)

if (cur->_right == NULL || cur->_right == prev)

{

cout << cur->_data << " ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面兩種情況，均不訪問(wèn)根，繼續(xù)遍歷右子樹(shù)

}

}

}

6.7層序遍歷：

上一層遍歷結(jié)束，再遍歷下一層結(jié)點(diǎn)，如int arr1[10] = { 1, 2, 3, '#', '#', 4, '#', '#', 5, 6 }（#表示空）,則層次遍歷就應(yīng)為：1，2，5，3，4，6。

考慮用隊(duì)列解決該問(wèn)題：首先先給隊(duì)列無(wú)條件入隊(duì)根結(jié)點(diǎn)，接著在出隊(duì)根結(jié)點(diǎn)之前先入隊(duì)它的子女結(jié)點(diǎn)2、5，則出隊(duì)1后，隊(duì)頭元素為2，在出隊(duì)它之前入隊(duì)它的根結(jié)點(diǎn)3，4……

//層序遍歷

void _LevelOrder(Node* root)

{

queue<Node*> q;

if (root == NULL)

{

return;

}

q.push(root);

while (!q.empty())

{

if (q.front()->_left != NULL)

{

q.push(q.front()->_left);

}

if (q.front()->_right != NULL)

{

q.push(q.front()->_right);

}

cout << q.front()->_data << " ";

q.pop();

}

}

完整代碼實(shí)現(xiàn)：

#include<iostream>

using namespace std;

#include<assert.h>

#include<queue>

#include<stack>

//節(jié)點(diǎn)結(jié)構(gòu)

template<class T>

struct  BinaryTreeNode

{

BinaryTreeNode<T>* _left;//左子樹(shù)

BinaryTreeNode<T>* _right;//右子樹(shù)

T _data;//數(shù)據(jù)域

//構(gòu)造函數(shù)

BinaryTreeNode(const T& x)

:_left(NULL)//左孩子指針

,_right(NULL)//右孩子指針

,_data(x)//數(shù)據(jù)域

{}

};

//二叉樹(shù)類(lèi)

template<class T>

class BinaryTree

{

typedef BinaryTreeNode<T> Node;//Node結(jié)點(diǎn)結(jié)構(gòu)

public:

BinaryTree()

:_root(NULL)

{}

//構(gòu)造函數(shù)

BinaryTree(const T* arr, size_t size, const T& invalid)//arr為結(jié)點(diǎn)數(shù)組，size為結(jié)點(diǎn)個(gè)數(shù)，invalid非法值

:_root(NULL)

{

size_t index = 0;//index指向結(jié)點(diǎn)的位置

_root = _CreateTree(arr, size, invalid, index);

}

//拷貝構(gòu)造

BinaryTree<T>(const BinaryTree<T>& t)

: _root(NULL)

{

_root = _Copy(t._root);

}

////賦值運(yùn)算符重載的傳統(tǒng)寫(xiě)法

//BinaryTree<T>& operator=(const BinaryTree<T>& t)

//{

// if (&t != this)

// {

// _Copy(t._root);

// _Destroy(_root);

// }

// return *this;

//}

//賦值運(yùn)算符重載的現(xiàn)代寫(xiě)法

BinaryTree<T>& operator=(BinaryTree<T> t)

{

swap(this->_root, t._root);

return *this;

}

//析構(gòu)函數(shù)

~BinaryTree()

{

if (_root)

{

_Destroy(_root);

}

}

//前序遍歷

void PreOrder()

{

_PrevOrder(_root);

cout << endl;

}

//前序遍歷非遞歸寫(xiě)法

void PreOrderNon_R()

{

_PrevOrderNon_R(_root);

cout << endl;

}

//中序遍歷

void InOrder()

{

_InOrder(_root);

cout << endl;

}

//中序遍歷非遞歸寫(xiě)法

void InOrderNon_R()

{

_InOrderNon_R(_root);

cout << endl;

}

//后序遍歷

void PostOrder()

{

_PostOrder(_root);

cout << endl;

}

//后序遍歷非遞歸寫(xiě)法

void PostOrderNon_R()

{

_PostOrderNon_R(_root);

cout << endl;

}

//層序遍歷

void LevelOrder()

{

_LevelOrder(_root);

cout << endl;

}

//節(jié)點(diǎn)數(shù)

size_t Size()

{

return _Size(_root);

}

//深度（高度）

size_t Depth()

{

return _Depth(_root);

}

//葉子結(jié)點(diǎn)數(shù)（葉結(jié)點(diǎn):沒(méi)有后繼的結(jié)點(diǎn)）

size_t LeafSize()

{

return _LeafSize(_root);

}

//第k層節(jié)點(diǎn)數(shù)

size_t kLevelSize(int k)

{

return _kLevelSize(_root, k);

}

//此處用protected和private都可，protected可被繼承，private不能被繼承，提高安全性

private:

Node* _CreateTree(const T* arr, size_t size, const T& invalid, size_t& index)

{

Node* root = NULL;

if (index < size&&arr[index] != invalid)

{

root = new Node(arr[index]);

root->_left = _CreateTree(arr, size, invalid, ++index);

root->_right = _CreateTree(arr, size, invalid, ++index);

}

return root;

}

Node* _Copy(Node* troot)

{

if (troot == NULL)

{

return NULL;

}

Node* root = new Node(troot->_data);

root->_left = _Copy(troot->_left);

root->_right = _Copy(troot->_right);

return root;

}

void _Destroy(Node* root)

{

if (root == NULL)

{

return;

}

if (root->_left == NULL&&root->_right == NULL)

{

delete root;

root = NULL;

return;

}

_Destroy(root->_left);

_Destroy(root->_right);

}

//方法1：后序遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)

size_t _LeafSize(Node* root)

{

static int size = 0;

if (root == NULL)

{

return size;

}

if (root->_left == NULL&&root->_right == NULL)

{

size++;

return size;

}

_LeafSize(root->_left);

_LeafSize(root->_right);

}

////方法2：后序遞歸遍歷統(tǒng)計(jì)葉子節(jié)點(diǎn)數(shù)

//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 _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;

}

size_t _kLevelSize(Node* root, int k)//默認(rèn)根結(jié)點(diǎn)為第1層

{

assert(k > 0);

if (root == NULL)

{

return 0;

}

if (k == 1)

{

return 1;

}

return _kLevelSize(root->_left, k - 1) + _kLevelSize(root->_right, k - 1);

}

//先序遍歷：根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

cout << root->_data << " ";

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

//先序遍歷非遞歸,根結(jié)點(diǎn)->左子樹(shù)->右子樹(shù)，利用棧"后進(jìn)先出"特點(diǎn)實(shí)現(xiàn)

void _PrevOrderNon_R(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)//注意要先壓入右結(jié)點(diǎn)，才能讓右結(jié)點(diǎn)后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

//中序遍歷：左子樹(shù)->根結(jié)點(diǎn)->右子樹(shù)

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

cout << root->_data << " ";

_InOrder(root->_right);

}

//中序遍歷非遞歸,最左結(jié)點(diǎn)cur是要訪問(wèn)的第一個(gè)結(jié)點(diǎn)，先把左壓進(jìn)去，然后把右樹(shù)當(dāng)成子樹(shù)

void _InOrderNon_R(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;

}

}

}

//后序遍歷：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn)

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

cout << root->_data << " ";

}

//后序遍歷非遞歸：左子樹(shù)->右子樹(shù)->根結(jié)點(diǎn),prev指向上一個(gè)剛剛訪問(wèn)過(guò)的結(jié)點(diǎn)

void _PostOrderNon_R(Node* root)

{

if (root == NULL)

{

return;

}

stack<Node*>s;

Node* cur = root;

Node* prev = NULL;

while (cur || !s.empty())

{

while (cur)

{

s.push(cur);

cur = cur->_left;

}

cur = s.top();//將棧頂元素保存，以便后面判斷它是否有右孩子

//無(wú)右孩子和右孩子是剛剛被訪問(wèn)過(guò)的結(jié)點(diǎn)，此時(shí)應(yīng)該訪問(wèn)根結(jié)點(diǎn)

if (cur->_right == NULL || cur->_right == prev)

{

cout << cur->_data << " ";

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面兩種情況，均不訪問(wèn)根，繼續(xù)遍歷右子樹(shù)

}

}

}

//層序遍歷

void _LevelOrder(Node* root)

{

queue<Node*> q;

if (root == NULL)

{

return;

}

q.push(root);

while (!q.empty())

{

if (q.front()->_left != NULL)

{

q.push(q.front()->_left);

}

if (q.front()->_right != NULL)

{

q.push(q.front()->_right);

}

cout << q.front()->_data << " ";

q.pop();

}

}

private:

Node* _root;

};

void TestBinaryTree()

{

int arr1[10] = { 1,2,3,'#','#',4,'#','#',5,6 };

cout << "打印此二叉樹(shù)："<<endl;

cout << "    "<<arr1[0] <<endl;

cout << "  " << arr1[1] << "    " << arr1[8] << endl;

cout << arr1[2] << "  " << arr1[5] << "  " << arr1[9] << endl;

BinaryTree<int>t1(arr1, 10, '#');

cout << "先序遍歷：";

t1.PreOrder();

cout << "先序非遞歸遍歷：";

t1.PreOrderNon_R();

cout << "中序遍歷：";

t1.InOrder();

cout << "中序非遞歸遍歷：";

t1.InOrderNon_R();

cout << "后序遍歷：";

t1.PostOrder();

cout << "后序非遞歸遍歷：";

t1.PostOrderNon_R();

cout << "層序遍歷：";

t1.LevelOrder();

cout << "結(jié)點(diǎn)的總數(shù)：";

cout << t1.Size() << endl;

cout << "樹(shù)的深度：";

cout << t1.Depth() << endl;

cout << "葉結(jié)點(diǎn)的個(gè)數(shù)：";

cout << t1.LeafSize() << endl;

cout << "第3層結(jié)點(diǎn)的個(gè)數(shù)：";

cout << t1.kLevelSize(3) << endl;

}

int main()

{

TestBinaryTree();

system("pause");

return 0;

}

運(yùn)行結(jié)果：

打印此二叉樹(shù)：

   1

  2    5

3  4  6

先序遍歷：1 2 3 4 5 6

先序非遞歸遍歷：1 2 3 4 5 6

中序遍歷：3 2 4 1 6 5

中序非遞歸遍歷：3 2 4 1 6 5

后序遍歷：3 4 2 6 5 1

后序非遞歸遍歷：3 4 2 6 5 1

層序遍歷：1 2 5 3 4 6

結(jié)點(diǎn)的總數(shù)：6

樹(shù)的深度：3

葉結(jié)點(diǎn)的個(gè)數(shù)：3

第3層結(jié)點(diǎn)的個(gè)數(shù)：3

請(qǐng)按任意鍵繼續(xù). . .

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

文章名稱(chēng)：二叉樹(shù)的先序、中序、后序遍歷等基本操作c++實(shí)現(xiàn)-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://chinadenli.net/article48/ddephp.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站維護(hù)、ChatGPT、響應(yīng)式網(wǎng)站、網(wǎng)站導(dǎo)航、網(wǎng)站收錄、外貿(mào)建站

廣告

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