二叉树的遍历C++代码实现

红太狼 2022-04-16 03:50 189阅读 0赞

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次

且仅被访问一次。

二叉树的遍历方式常用的有四种：前序遍历、中序遍历、后序遍历和层序遍历。

二叉树结点的定义代码如下：

//Definition for binary tree
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };

前序遍历：简单来说就是：根->左->右。

规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。

c++代码实现：

//前序遍历二叉树:根--左--右
    void preScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	cout << t->val <<" ";
    	preScanf(t->left);
    	preScanf(t->right);
    }

中序遍历：简单来说就是：左->根->右。

规则：若二叉树为空，则空操作返回，否则从根结点开始，先中序遍历根结点的左子树，然后是访问

根结点，最后中序遍历右子树。

c++代码如下：

//中序遍历二叉树：左---根---右
    void middleScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	middleScanf(t->left);
    	cout << t->val << " ";
    	middleScanf(t->right);
    }

后序遍历：简单来说就是：左->右->根。

规则：若二叉树为空，则空操作返回，否则从根结点开始，先后序遍历根结点的左子树，再后序遍历

根结点的右子树，最后访问根结点。

c++代码如下：

//后序遍历二叉树：左---右---根
    void backScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	backScanf(t->left);
    	backScanf(t->right);
    	cout << t->val <<" ";
    }

层序遍历：从上到下，从左到右。

规则：若二叉树为空，则空操作返回，否则从二叉树的第一层也就是根结点开始访问，从上而下逐层遍历，

在同一层中，按从左到右的顺序对结点逐个访问。

代码思路讲解：若要实现按层遍历，那么应该先访问根结点，然后再访问遍历结点的两个子节点，放入容器，

按照从左到右的顺序遍历到左子节点时就把其的两个子节点放到容器，最后输出的时候，就是从容器中按照顺序输出，

先进先出，所以想到可以用队列做为数据容器。

从上到下打印二叉树的规律：每一次打印一个节点的时候，如果该结点有子结点，则把该结点的子结点放到一个队列的末尾，

接下来从队列的头部取出最早进入队列的结点，重复输出，直至队列中所有结点都被打印出来。

c++代码如下：

//层序遍历二叉树：从上到下，从左到右
    void fromTopToBottomScanf(TreeNode* t)
    {
    	if (t==NULL)
    	{
    		return;
    	}
    	deque<TreeNode*> dequeTreeNode;
    	dequeTreeNode.push_back(t);
     
    	while (dequeTreeNode.size())
    	{
    		TreeNode* pNode = dequeTreeNode.front(); //依次取出队列中的头部元素进行打印
    		dequeTreeNode.pop_front(); //
     
    		cout << pNode->val << " ";
    		if (pNode->left)
    		{
    			dequeTreeNode.push_back(pNode->left);
    		}
    		if (pNode->right)
    		{
    			dequeTreeNode.push_back(pNode->right);
    		}
    	}
    }

下面结合具体的例子说明：

编程实现：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列\{1,2,4,7,3,5,6,8\}和中序遍历序列\{4,7,2,1,5,3,8,6\}，则重建二叉树并返回。

由前序遍历和中序遍历结果重构二叉树，并把重构出来的二叉树分别采用以上的四种遍历方式进行输出。

c++代码实现如下：

#include <iostream>
    #include <vector>
    #include <deque>
    using namespace std;
     
     
    //Definition for binary tree
    struct TreeNode {
        int val;
        TreeNode *left;
        TreeNode *right;
        TreeNode(int x) : val(x), left(NULL), right(NULL) {}
    };
     
    class Solution {
    public:
    	TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    		if (pre.size() == 0 || vin.size() == 0)
    			return NULL;
    		vector<int>::iterator preStartIter = pre.begin();
    		vector<int>::iterator preEndIter = pre.end()-1;
    		vector<int>::iterator vinStartIter = vin.begin();
    		vector<int>::iterator vinEndIter = vin.end()-1;
    		return constructCore(preStartIter,preEndIter,vinStartIter,vinEndIter);
    	}
    	
    private:
    	TreeNode* constructCore(vector<int>::iterator preStartIter, 
    		vector<int>::iterator preEndIter,vector<int>::iterator vinStartIter,vector<int>::iterator vinEndIter){
    		int rootValue = *preStartIter;
    		TreeNode* root = new TreeNode(rootValue);
    		//如果只有一个根节点，那么返回根节点
    		if (preStartIter==preEndIter)
    		{
    			if (vinStartIter==vinEndIter && *preStartIter==*vinStartIter)
    			{
    				return root;
    			}
    			else
    			{
    				throw std::exception("invalid input!");
    			}
    		}
     
    		//在中序遍历结果中去查找根节点值，找到左右子树分割点位置
    		vector<int>::iterator rootInVin = vinStartIter;
    		while (rootInVin!=vinEndIter && *rootInVin!=rootValue)
    		{
    			++rootInVin;
    		}
    		//求左子树的长度
    		int leftLength = rootInVin - vinStartIter;
    		vector<int>::iterator preLeftEnd = preStartIter + leftLength;
    		if (leftLength>0)
    		{
    			//构建左子树
    			root->left=constructCore(preStartIter+1, preLeftEnd, vinStartIter, rootInVin-1);
    		}
    		if (leftLength<preEndIter-preStartIter) //如果存在右子树，则递归创建右子树
    		{
    			//构建右子树
    			root->right = constructCore(preLeftEnd + 1, preEndIter, rootInVin + 1, vinEndIter);
    		}
    		return root;
    	}
    };
     
    //前序遍历二叉树:根--左--右
    void preScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	cout << t->val <<" ";
    	preScanf(t->left);
    	preScanf(t->right);
    }
    //中序遍历二叉树：左---根---右
    void middleScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	middleScanf(t->left);
    	cout << t->val << " ";
    	middleScanf(t->right);
    }
    //后序遍历二叉树：左---右---根
    void backScanf(TreeNode* t)
    {
    	if (t == NULL)
    	{
    		return;
    	}
    	backScanf(t->left);
    	backScanf(t->right);
    	cout << t->val <<" ";
    }
    //层序遍历二叉树：从上到下，从左到右
    void fromTopToBottomScanf(TreeNode* t)
    {
    	if (t==NULL)
    	{
    		return;
    	}
    	deque<TreeNode*> dequeTreeNode;
    	dequeTreeNode.push_back(t);
     
    	while (dequeTreeNode.size())
    	{
    		TreeNode* pNode = dequeTreeNode.front(); //依次取出队列中的头部元素进行打印
    		dequeTreeNode.pop_front(); //
     
    		cout << pNode->val << " ";
    		if (pNode->left)
    		{
    			dequeTreeNode.push_back(pNode->left);
    		}
    		if (pNode->right)
    		{
    			dequeTreeNode.push_back(pNode->right);
    		}
    	}
    }
     
    int main()
    {
    	Solution s;
    	vector<int> pre = { 1, 2, 4, 7, 3, 5, 6, 8 };
    	vector<int> vin = { 4, 7, 2, 1, 5, 3, 8, 6 };
    	TreeNode *t;
    	t = s.reConstructBinaryTree(pre, vin);
    	cout << "前序遍历二叉树序列为：" << endl;
    	preScanf(t);
    	cout << endl<<"中序遍历二叉树序列为："<< endl;
    	middleScanf(t);
    	cout << endl<<"后序遍历二叉树序列为：" << endl;
    	backScanf(t);
    	cout << endl << "后序遍历二叉树序列为：" << endl;
    	fromTopToBottomScanf(t);
    	cout << endl;
    	return 0;
    }

程序的输出结果如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dhbmdqaWFuNTMw_size_16_color_FFFFFF_t_70]: /images/20220416/860853f6c0e14db19bddce8e4a63cb1e.png