二叉樹的先序、中序、后序遍歷等基本操作c++實現

二叉樹：樹的每個節點最多有兩個子節點。

1.實現二叉鏈表的結構：

//節點結構

template<class T>

struct  BinaryTreeNode

{

BinaryTreeNode<T>* _left;//左子樹

BinaryTreeNode<T>* _right;//右子樹

T _data;//數據域

//構造函數

BinaryTreeNode(const T& x)

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

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

,_data(x)//數據域

{}

};

2.求二叉樹的葉子結點數_LeafSize:

葉結點：無后繼結點的結點。

方法一：設置一下全局變量或者靜態變量的size，遍歷二叉樹，每次遇到一個節點就加加一次size；

方法二：遞歸實現，總葉結點數=左子樹葉結點個數+右子樹葉結點個數。

//方法1：后序遍歷統計葉子節點數

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：后序遞歸遍歷統計葉子節點數

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.求二叉樹的深度_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;

}

4.求二叉樹的結點個數_size:

總結點數=左子樹結點個數+右子樹結點個數+根結點個數1

size_t _Size(Node* root)

{

if (root == NULL)

{

return 0;

}

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

}

5.求第k層節點數：（默認根節點為第1層）

方法與求葉結點同理。

size_t _kLevelSize(Node* root, int k)//默認根結點為第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.遍歷二叉樹：

6.1先序遍歷：訪問根結點->左子樹->右子樹

//先序遍歷：根結點->左子樹->右子樹

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

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

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

6.2先序遍歷非遞歸寫法：

    用棧模擬前序遍歷，棧的特點是后進先出，則將無條件地入棧根結點，在彈出根結點之前依次將根結點的右孩子結點和左孩子結點入棧。

//先序遍歷非遞歸,根結點->左子樹->右子樹，利用棧"后進先出"特點實現

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)//注意要先壓入右結點，才能讓右結點后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

6.3中序遍歷：訪問左子樹->根結點->右子樹

//中序遍歷：左子樹->根結點->右子樹

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

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

_InOrder(root->_right);

}

6.4中序遍歷非遞歸寫法：

二叉樹：

      1

   2      5

3   4   6

1、借助棧實現，先順著二叉樹找到最左邊且最下邊的結點3（一邊找一邊入棧），此時入棧序列為1，2，3。

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

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

//中序遍歷非遞歸,最左結點cur是要訪問的第一個結點，先把左壓進去，然后把右樹當成子樹

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后序遍歷：訪問左子樹->右子樹->根結點

//后序遍歷：左子樹->右子樹->根結點

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

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

}

6.6后序遍歷非遞歸寫法：

1、后序遍歷同樣借助棧實現，先找到最左邊且為最下面的結點3（一邊入棧一邊找）；

2、結點3若沒有右孩子，打印節點3，之后彈出棧頂結點3；

3、結點3若有右孩子，繼續遍歷它的右子樹，等遍歷結束才可打印3。遍歷重復步驟1,2,3

//后序遍歷非遞歸：左子樹->右子樹->根結點,prev指向上一個剛剛訪問過的結點

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();//將棧頂元素保存，以便后面判斷它是否有右孩子

//無右孩子和右孩子是剛剛被訪問過的結點，此時應該訪問根結點

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

{

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

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面兩種情況，均不訪問根，繼續遍歷右子樹

}

}

}

6.7層序遍歷：

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

考慮用隊列解決該問題：首先先給隊列無條件入隊根結點，接著在出隊根結點之前先入隊它的子女結點2、5，則出隊1后，隊頭元素為2，在出隊它之前入隊它的根結點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();

}

}

完整代碼實現：

#include<iostream>

using namespace std;

#include<assert.h>

#include<queue>

#include<stack>

//節點結構

template<class T>

struct  BinaryTreeNode

{

BinaryTreeNode<T>* _left;//左子樹

BinaryTreeNode<T>* _right;//右子樹

T _data;//數據域

//構造函數

BinaryTreeNode(const T& x)

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

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

,_data(x)//數據域

{}

};

//二叉樹類

template<class T>

class BinaryTree

{

typedef BinaryTreeNode<T> Node;//Node結點結構

public:

BinaryTree()

:_root(NULL)

{}

//構造函數

BinaryTree(const T* arr, size_t size, const T& invalid)//arr為結點數組，size為結點個數，invalid非法值

:_root(NULL)

{

size_t index = 0;//index指向結點的位置

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

}

//拷貝構造

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

: _root(NULL)

{

_root = _Copy(t._root);

}

////賦值運算符重載的傳統寫法

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

//{

// if (&t != this)

// {

// _Copy(t._root);

// _Destroy(_root);

// }

// return *this;

//}

//賦值運算符重載的現代寫法

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

{

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

return *this;

}

//析構函數

~BinaryTree()

{

if (_root)

{

_Destroy(_root);

}

}

//前序遍歷

void PreOrder()

{

_PrevOrder(_root);

cout << endl;

}

//前序遍歷非遞歸寫法

void PreOrderNon_R()

{

_PrevOrderNon_R(_root);

cout << endl;

}

//中序遍歷

void InOrder()

{

_InOrder(_root);

cout << endl;

}

//中序遍歷非遞歸寫法

void InOrderNon_R()

{

_InOrderNon_R(_root);

cout << endl;

}

//后序遍歷

void PostOrder()

{

_PostOrder(_root);

cout << endl;

}

//后序遍歷非遞歸寫法

void PostOrderNon_R()

{

_PostOrderNon_R(_root);

cout << endl;

}

//層序遍歷

void LevelOrder()

{

_LevelOrder(_root);

cout << endl;

}

//節點數

size_t Size()

{

return _Size(_root);

}

//深度（高度）

size_t Depth()

{

return _Depth(_root);

}

//葉子結點數（葉結點:沒有后繼的結點）

size_t LeafSize()

{

return _LeafSize(_root);

}

//第k層節點數

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：后序遍歷統計葉子節點數

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：后序遞歸遍歷統計葉子節點數

//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)//默認根結點為第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);

}

//先序遍歷：根結點->左子樹->右子樹

void _PrevOrder(Node* root)

{

if (root == NULL)

{

return;

}

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

_PrevOrder(root->_left);

_PrevOrder(root->_right);

}

//先序遍歷非遞歸,根結點->左子樹->右子樹，利用棧"后進先出"特點實現

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)//注意要先壓入右結點，才能讓右結點后出

{

s.push(root->_right);

}

if (root->_left)

{

s.push(root->_left);

}

}

}

//中序遍歷：左子樹->根結點->右子樹

void _InOrder(Node* root)

{

if (root == NULL)

{

return;

}

_InOrder(root->_left);

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

_InOrder(root->_right);

}

//中序遍歷非遞歸,最左結點cur是要訪問的第一個結點，先把左壓進去，然后把右樹當成子樹

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;

}

}

}

//后序遍歷：左子樹->右子樹->根結點

void _PostOrder(Node* root)

{

if (root == NULL)

{

return;

}

_PostOrder(root->_left);

_PostOrder(root->_right);

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

}

//后序遍歷非遞歸：左子樹->右子樹->根結點,prev指向上一個剛剛訪問過的結點

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();//將棧頂元素保存，以便后面判斷它是否有右孩子

//無右孩子和右孩子是剛剛被訪問過的結點，此時應該訪問根結點

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

{

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

s.pop();

prev = cur;

cur = NULL;

}

else

{

cur = cur->_right;//除上面兩種情況，均不訪問根，繼續遍歷右子樹

}

}

}

//層序遍歷

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 << "打印此二叉樹："<<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 << "結點的總數：";

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

cout << "樹的深度：";

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

cout << "葉結點的個數：";

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

cout << "第3層結點的個數：";

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

}

int main()

{

TestBinaryTree();

system("pause");

return 0;

}

運行結果：

打印此二叉樹：

      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

結點的總數：6

樹的深度：3

葉結點的個數：3

第3層結點的個數：3

請按任意鍵繼續. . .