二叉树三种遍历（递归与非递归）C++实现

ゝ一世哀愁。 2021-12-03 23:21 303阅读 0赞

### 文章目录 ###

*  遍历类型
 *  一个二叉树
 *  递归实现
 *  非递归实现
 *   *  先序遍历
     *  中序遍历
     *  后序遍历
 *  完整代码
 *  结果图

# 遍历类型 #

众所周知，二叉树的遍历有三种：前序遍历、中序遍历和后序遍历。三者不同之处是访问节点的先后次序（注意该先后次序是指节点、节点左子树、节点右子树，这三部分的顺序而非每一个节点的顺序，这三部分内部的遍历顺序与外部保持一致）。三种遍历的实现依靠递归或者非递归两种。

所以，前中后三种遍历是指节点相对于其左孩子和右孩子的位置。

# 一个二叉树 #

如下图一个满的完全二叉树

# 递归实现 #

遍历时，遇空则返回上一级，使用下图更直接些。

null

因为4/5/6/7四个节点的左右孩子为空，所以到达空节点后会返回节点，拿节点4为例：

先遍历其左孩子发现为null,返回到4的位置

然后遍历其右孩子发现还为null返回4

4的树遍历完后返回到2的位置，开始进行2的右孩子的遍历。其他节点同理。  
遍历的实际过程为：124442555213666377731  
神奇的事情发生了！

1.  先序遍历实际就是打印数值第一次出现时间，即1245367
2.  中序遍历实际为打印数值第二次出现时间，即4251637
3.  后序遍历实际为打印数值第三次出现时间，即4526731

观察代码你会发现，三种遍历方法的不同之处就是打印操作出现的时间！  
4. 先序遍历（中左右）：打印放前 → \\rightarrow →递归左子树 → \\rightarrow →递归右子树  
5. 中序遍历（左中右）：递归左子树 → \\rightarrow →打印放中 → \\rightarrow →递归右子树  
6. 后序遍历（左右中）：递归左子树 → \\rightarrow →递归右子树 → \\rightarrow →打印放后  
所以，递归对于二叉树是好用的，他可以实访问一个节点三次。

# 非递归实现 #

用非递归实现二叉树时，要借用堆（stack）这个数据结构。因为递归的实质就是系统压栈出栈的过程，不使用递归则要申请一个额外的空间使用栈来实现二叉树的遍历（用队列好像也可以）。**强烈建议自己动手画一遍过程！！！**

## 先序遍历 ##

使用一个栈stack。  
**先将头结点压入，再在栈不为空的前提下循环：**  
1.弹出栈顶元素  
2.判断该节点右孩子不为空，压入该右孩子  
3.判断该节点左孩子不为空，压入该左孩子（此时该值为栈顶元素），循环1的操作  
故，第一步把头结点弹出，然后先压右再压左，弹出的顺序便是先弹左再弹右，符合中左右的顺序。

## 中序遍历 ##

使用一个栈。  
**在该节点不为空或栈不为空的前提下循环：**  
1.节点不为空，将**该节点与其左边界**（左孩子的左孩子的左…）**全部顺次压入栈中，直至为空**。  
2.节点为空，则将栈顶元素（左边界值）弹出（此时栈顶是其父节点），移至右孩子，判空后执行响应操作。

## 后序遍历 ##

使用两个栈。（也可以使用一个栈）  
一个栈temp用来临时存放，另一个栈用来弹出遍历结果。  
**先将头结点压入temp中：**  
1.栈temp不空，则把栈顶元素弹出当做当前节点，并压入另一个栈中，若该节点左右节点为空，则一直进行栈顶元素的弹出和压入,否则**先压其左孩子再压其右孩子**，直至栈空为止。  
2.当要弹出遍历结果的栈不空时，一次弹出栈顶元素即为遍历结果。  
一开始就把头结点压入了栈中，在temp中先压左再压右的目的就是弹出给stackpull中是以先右后左的顺序。这样就做到了弹出时按照左右中的顺序。

# 完整代码 #

#include<iostream>
    #include<stack>
    using namespace std;
    struct Node
    {
        
    	int data;
    	Node *left;
    	Node *right;
    	Node(int data)
    	{
        
    		this->data = data;
    		this->left = NULL;
    		this->right = NULL;
    	}
    };
    class BinTree
    {
        
    public:
    	Node *root;
    	Node *CreateTree();
    	void Preorder(Node *root);
    	void Inorder(Node *root);
    	void Postorder(Node *root);
    	void Preorder2(Node *root);
    	void Inorder2(Node *root);
    	void Postorder2(Node *root);
    };
    Node* BinTree::CreateTree()
    {
        
    	Node *p1 = new Node(1);
    	Node *p2 = new Node(2);
    	Node *p3 = new Node(3);
    	Node *p4 = new Node(4);
    	Node *p5 = new Node(5);
    	Node *p6 = new Node(6);
    	Node *p7 = new Node(7);
    	p1->left = p2; p1->right = p3;
    	p2->left = p4; p2->right = p5;
    	p3->left = p6; p3->right = p7;
    	root = p1;
    	return root;
    }
    /*二叉树递归遍历*/
    void BinTree::Preorder(Node *root)
    {
        
    	if (root == NULL) return;
    	else 
    	{
        
    		cout << root->data << "";
    		Preorder(root->left);
    		Preorder(root->right);
    	}
    }
    void BinTree::Inorder(Node *root)
    {
        
    	if (root == NULL) return;
    	else
    	{
        
    		Inorder(root->left);
    		cout << root->data << "";
    		Inorder(root->right);
    	}
    }
    void BinTree::Postorder(Node *root)
    {
        
    	if (root == NULL) return;
    	else
    	{
        	
    		Postorder(root->left);
    		Postorder(root->right);
    		cout << root->data << "";
    	}
    }
    /*二叉树非递归遍历*/
    void BinTree::Preorder2(Node *root)
    {
        
    	if (root == NULL) return;
    	else
    	{
        
    		stack<Node*> stack;
    		stack.push(root);
    		while (!stack.empty())
    		{
        
    			root = stack.top();
    			cout << root->data << "";
    			stack.pop();//stack.top()可以给root而stack.pop()却不能？？
    			if (root->right != NULL)
    				stack.push(root->right);
    			if (root->left != NULL)
    				stack.push(root->left);
    		}
    	}
    	cout << endl;
    }
    void BinTree::Inorder2(Node *root)
    {
        
    	if (root == NULL) return;
    	else
    	{
        
    		stack<Node*> stack;		
    		while (!stack.empty() || root != NULL)
    		{
        
    			if (root != NULL)
    			{
        
    				stack.push(root);
    				root = root->left;
    			}
    			else
    			{
        
    				root = stack.top();
    				cout << root->data << "";
    				stack.pop();
    				root = root->right;
    			}
    		}
    	}
    	cout << endl;
    }
    void BinTree::Postorder2(Node *root)
    {
        
    	if (root == NULL) return;
    	else
    	{
        
    		stack<Node*> stacktemp;
    		stack<Node*> stackpull;
    		stacktemp.push(root);
    		while (!stacktemp.empty())
    		{
        
    			root = stacktemp.top();
    			stacktemp.pop();
    			stackpull.push(root);
    			if (root->left != NULL)
    				stacktemp.push(root->left);
    			if (root->right != NULL)
    				stacktemp.push(root->right);
    		}
    		while (!stackpull.empty())
    		{
        
    			root = stackpull.top();
    			cout << root->data << "";
    			stackpull.pop();
    		}
    	}
    	cout << endl;
    }
    int main()
    {
        
    	BinTree tree;
    	tree.CreateTree();
    	cout << "********二叉树递归遍历********";
    	cout << endl;
    	cout << "先序递归结果：";
    	tree.Preorder(tree.root);	
    	cout << endl;
    	cout << "中序递归结果：";
    	tree.Inorder(tree.root);	
    	cout << endl;
    	cout << "后序递归结果：";	
    	tree.Postorder(tree.root); 
    	cout << endl;
    	cout << "********二叉树非递归遍历********";
    	cout << endl;
    	cout << "先序非递归结果：";
    	tree.Preorder2(tree.root);
    	cout << "中序非递归结果：";
    	tree.Inorder2(tree.root);
    	cout << "后序非递归结果：";
    	tree.Postorder2(tree.root);
    	return 0;
    }

# 结果图 #

![遍历结果图][20190718222636562.png]

[20190718222636562.png]: /images/20211203/cd1aa1edb69541cea555c583e2cbc9dc.png