二叉树的先序、中序、后序遍历等基本操作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

请按任意键继续. . .