【数据结构】二叉树前中后序遍历、层序遍历（递归实现）

ゝ一世哀愁。 2022-06-13 10:39 132阅读 0赞

这里使用C++模板、前序遍历方式建立二叉树

主要介绍：递归实现二叉树建立，前序、中序、后续、层序遍历 ，求二叉树深度及节点个数

本文使用序列：array\[10\] = \{ 1, 2, 3, -1, -1, 4, -1, -1, 5, 6 \};

![SouthEast][]

前序遍历算法：

若二叉树为空，则算法结束，否则：

1）先访问根节点 2）前序遍历访问左子树 3）前序遍历访问右子树

前序遍历结果：1 2 3 4 5 6

中序遍历算法：

若二叉树为空，则算法结束，否则：

1）前序遍历访问左子树 2）访问根节点 3）后续遍历访问右子树

中序遍历结果： 3 2 4 1 6 5

后续遍历算法：

若二叉树为空，则算法结束，否则：

1）前序遍历访问左子树 2）后续遍历访问右子树 3）访问根节点

后序遍历结果： 3 4 2 6 5 1

层序遍历算法：

按照二叉树的层序次序(即从根节点层到叶结点层)，同一层中按先左子树再右子树的次序遍历二叉树。因此：在所有未被访问结点的集合中，排列在已访问结点集合中最前面结点的左子树的根节点将最先被访问，然后是该结点的右子树的根节点

1）先初始化一个队列 2）把根节点指针插入队列

3）当队列非空时：

a. 出队列取一个节点

b.若该节点的左子树不为空，则将该结点的左子树入队列

c.若该节点的右子树不为空，泽江该节点的右子树入队列

![SouthEast 1][] 层序遍历结果：1 2 6 3 4 5

以下是二叉树建立及遍历实现代码：

BinaryTree.hpp

#ifndef __BINARYTREE_H__
    #define __BINARYTREE_H__
    #include<iostream>
    #include<queue>
    using namespace std;
    template<class T>
    struct BinaryTreeNode
    {
    	T _value;
    	BinaryTreeNode<T>* _left;
    	BinaryTreeNode<T>* _right;
    
    	BinaryTreeNode(const T& data)
    		:_value(data)
    		, _left(NULL)
    		, _right(NULL)
    	{}
    };
    
    template<class T>
    class BinaryTree
    {
    public:
    	BinaryTree()
    		:_root(NULL)
    	{}
    	//先序遍历建立二叉树
    	BinaryTree(T* arr, int size,const T& invalid)
    	{
    		int index = 0;
    		_root = _CreateBinaryTree(arr, index, size, invalid);
    	}
    	//拷贝构造函数
    	BinaryTree(const BinaryTree<T>& t)
    	{
    		_root = _Copy(t._root);
    	}
    	//赋值操作符重载
    	BinaryTreeNode<T>& operator=(const BinaryTree<T>& t)
    	{
    		/*if (*this != t)
    		{
    			_root = _Copy(t._root);
    		}*/
    		swap(_root, t._root);//现代写法
    	}
    	//析构函数
    	~BinaryTree()
    	{
    		_Del(_root);
    	}
    	//前序遍历 中序遍历 后续遍历 层序遍历 求节点个数 深度（高度）
    	//前序遍历 
    	void PreOrder()
    	{
    		_PreOrder(_root);
    		cout << endl;
    	}
    	void InOrder()
    	{
    		_InOrder(_root);
    		cout << endl;
    	}
    	void PostOrder()
    	{
    		_PostOrder(_root);
    		cout << endl;
    	}
    	void LevelOrder()
    	{
    		_LevelOrder(_root);
    		cout << endl;
    	}
    	size_t Size()
    	{
    		size_t size = _Size(_root);
    		return size;
    	}
    	size_t Depth()
    	{
    		size_t depth = _Depth(_root);
    		return depth;
    	}
    protected:
    	//创建二叉树函数
    	BinaryTreeNode<T>* _CreateBinaryTree(const T* arr, int& index, int size, const T& invalid)
    	{
    		//先序遍历创建 
    		//若插入个数==数据个数则退出/或者数据为空（#）
    		BinaryTreeNode<T>* root = NULL;
    		if (index < size && arr[index] != invalid)
    		{
    			//递归创建
    			root = new BinaryTreeNode<T>(arr[index]);
    			root->_left = _CreateBinaryTree(arr, ++index, size, invalid);//先创建左子树节点
    			root->_right = _CreateBinaryTree(arr, ++index, size, invalid);//再创建右子树节点
    		}
    		return root;
    	}
    	//拷贝函数
    	BinaryTreeNode<T>* _Copy(const BinaryTreeNode<T>* root)
    	{
    		BinaryTreeNode<T>* tmp = NULL;
    		if (root)
    		{
    			tmp = new BinaryTreeNode<T>(root->_value);
    			tmp->_left = _Copy(root->_left);
    			tmp->_right = _Copy(root->_right);
    		}
    		return tmp;
    	}
    	//销毁函数
    	void _Del(BinaryTreeNode<T>* root)
    	{
    		if (root)
    		{
    			_Del(root->_left);
    			_Del(root->_right);
    			delete root;
    		}
    	}
    	//前序遍历 
    	void _PreOrder(BinaryTreeNode<T>* root)
    	{
    		if (root)
    		{
    			cout << root->_value << " ";
    			_PreOrder(root->_left);
    			_PreOrder(root->_right);
    		}
    	}
    	//中序遍历
    	void _InOrder(BinaryTreeNode<T>* root)
    	{
    		if (root)
    		{
    			_InOrder(root->_left);
    			cout << root->_value << " ";
    			_InOrder(root->_right);
    		}
    	}
    	//后序遍历
    	void _PostOrder(BinaryTreeNode<T>* root)
    	{
    		if (root)
    		{
    			_PostOrder(root->_left);
    			_PostOrder(root->_right);
    			cout << root->_value << " ";
    		}
    	}
    	//层序遍历
    	void _LevelOrder(BinaryTreeNode<T>* root)
    	{
    		queue<BinaryTreeNode<T>*> q;
    		q.push(root);
    		while (!q.empty())
    		{
    			if (q.front())
    			{
    				BinaryTreeNode<T>* tmp = q.front();
    				cout << tmp->_value << " ";
    				if (tmp->_left)
    					q.push(tmp->_left);
    				if (tmp->_right)
    					q.push(tmp->_right);
    				q.pop();
    			}
    		}
    	}
    	//计算节点个数
    	size_t _Size(BinaryTreeNode<T>* root)
    	{
    		if (root == NULL)
    			return 0;
    		return _Size(root->_left) + _Size(root->_right) + 1;
    	}
    	//计算二叉树深度
    	size_t _Depth(BinaryTreeNode<T>* root)
    	{
    		int depth = 0;
    		if (root)
    		{
    			int leftdepth = _Depth(root->_left);
    			int rightdepth = _Depth(root->_right);
    			depth = leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
    			return depth;
    		}
    		return depth;
    	}
    private:
    	BinaryTreeNode<T>* _root;
    };
    
    #endif

测试代码：

#include"BinaryTree.hpp"
    
    void Funtest1()
    {
    	int array[10] = { 1, 2, 3, -1, -1, 4, -1, -1, 5, 6 };
    	//1, 2, 3, '#', '#', 4, '#', '#', 5, 6
    	BinaryTree<int> bt(array, 10, -1);
    	cout << "前序遍历： " ;
    	bt.PreOrder();
    	cout << "中序遍历： " ;
    	bt.InOrder();
    	cout << "后序遍历： " ;
    	bt.PostOrder();
    	cout << "层序遍历： " ;
    	bt.LevelOrder();
    
    	cout << "size: " << bt.Size() << endl;
    	cout << "depth: " << bt.Depth() << endl;	
    }
    
    int main()
    {
    	Funtest1();
    	system("pause");
    	return 0;
    }

测试结果：

![SouthEast 2][]

[SouthEast]: /images/20220613/3eacab8233ff4950990b3c88bd4dcaf9.png
[SouthEast 1]: /images/20220613/8931b500d2bc46c28ed1e1d5a3dd95c3.png
[SouthEast 2]: /images/20220613/e333f5a490384c579c9b029332757f57.png