C++高级数据结构算法#二叉树的遍历算法(递归与非递归)

浅浅的花香味﹌ 2022-01-14 15:35 310阅读 0赞

### 文章目录 ###

*   *   *  二叉树的结构定义
         *  二叉树的遍历算法
         *   *  前序遍历(VLR)
             *   *  非递归版本
                 *  递归版本
             *  中序遍历(LVR)
             *   *  非递归版本
                 *  递归版本
             *  后序遍历(LRV)
             *   *  非递归版本
                 *  递归版本
             *  层序遍历(广度优先遍历)
             *   *  非递归版本
                 *  递归版本

### 二叉树的结构定义 ###

template<typename T>
    class BSTree
    {
        
    public:
    	BSTree():_root(nullptr){
        }
    private:
    	// 定义BST树节点的类型
    	struct BSTNode
    	{
        
    		BSTNode(T data=T())
    			:_data(data)     //数据
    			,_left(nullptr)  //左孩子
    			,_right(nullptr) //右孩子
    		{
        }
    		T _data;
    		BSTNode *_left;
    		BSTNode *_right;
    	};
    	BSTNode *_root; // 指向树的根节点
    };

### 二叉树的遍历算法 ###

在介绍遍历算法之前 , 先给大家看一段代码

void func(BSTNode *node)	
    	{
        
    		if (node != nullptr)
    		{
        
    			func(node->_left);
    			func(node->_right);
    		}
    	}

**这段代码是什么作用呢 , 就是用来实现递归调用遍历树中的每个节点 .** 这段代码在BST树中各种遍历的问题中都会使用到 .

#### 前序遍历(VLR) ####

**定义 : 又称为先根遍历 . 其访问规则是如果二叉树为空则进行空操作 , 否则首先访问根节点 , 然后前序遍历左子树 , 最后前序遍历右子树 .**

**注 : V是根节点 , L是左子树 , R是右子树**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70]

**流程 :**

*  前序遍历根节点A , 打印A
 *  前序遍历A的左子树,即以B为根节点的子树
 *  前序遍历根节点B , 打印AB
 *  前序遍历B的左子树 , 即以D为根节点的子树
 *  前序遍历根节点D , 打印ABD
 *  前序遍历D的左子树 , 为空 , 进行空操作
 *  前序遍历D的右子树 , 为空 , 进行空操作
 *  回退到以B为根的子树
 *  前序遍历B的右子树 , 即以E为根节点的子树
 *  前序遍历根节点E , 打印ABDE
 *  前序遍历E的左子树 , 为空 , 进行空操作
 *  前序遍历E的右子树 , 为空 , 进行空操作
 *  (至此B节点的VLR都查找完毕 , 回退到A)
 *  前序遍历A的右子树 , 即以C为根结点的子树
 *  前序遍历根节点C , 打印ABDEC
 *  前序遍历C的左子树 , 即以F为根节点的子树
 *  前序遍历根节点F , 打印ABDECF
 *  由于F没有子树 , 所以进行空操作 , 并回退到以C为根节点的子树
 *  前序遍历C的右子树 , 即以G为根节点的子树
 *  前序遍历根节点G , 打印ABDECFG
 *  至此 , 二叉树的前序遍历完成 , 最终的遍历结果是 : ABDECFG

##### 非递归版本 #####

//非递归实现BST的前序遍历 VLR
    	/*
    	深度是用栈 , 广度是用队列
    	因为是先序遍历是先左后右 , 入栈的之后要反着来(先右后左) , 在弹出时才能满足先左后右
    
    	流程: 
    	现将根节点入栈 
    	以栈是否为空作为条件进行循环 
    	出栈顶元素 , 打印
    	将该节点的右孩子和左孩子依次压栈(因为出的时候要先左后右)
    	周而复始
    	*/
    	void nonpreOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		BSTNode* node = _root;
    		stack<BSTNode*> st;
    		st.push(_root);
    		cout<<"非递归实现 , 前序遍历 : ";
    		while(!st.empty())
    		{
        
    			BSTNode* tmp = st.top();
    			st.pop();
    			cout<<tmp->_data<<" ";
    			if(tmp->_right != nullptr)
    			{
        
    				st.push(tmp->_right);
    			}
    			if(tmp->_left != nullptr)
    			{
        
    				st.push(tmp->_left);
    			}
    		}
    		cout<<endl;
    	}

##### 递归版本 #####

//递归实现 , 前序遍历
    	void Pre_out()
    	{
        
    		cout<<"递归实现 , 前序遍历 : ";
    		Pre_out(_root);
    		cout << endl;
    	}

//递归实现 , 先序遍历   VLR
    	void Pre_out(BSTNode *node)	//前序遍历
    	{
        
    		if (node != nullptr)
    		{
        
    			cout << node->_data << " ";
    			Pre_out(node->_left);
    			Pre_out(node->_right);
    		}
    	}

#### 中序遍历(LVR) ####

**定义 : 又称为中根遍历 , 其访问规则是如果二叉树为空则进行空操作 , 否则首先中序遍历左子树 , 然后访问根节点 , 最后中序遍历右子树 .**  
**注 : 中序遍历所打印出来的结果只按照从小到大的结果打印 .**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 1]

流程 :

*  中序遍历从根节点A开始 , 但是并没有直接访问
 *  中序遍历A的左子树B , 遇到以B为根节点的子树后也没有直接访问B
 *  中序遍历B的左子树D , 即以D为根节点的子树
 *  中序遍历D的左子树 , 为空 , 进行空操作
 *  中序遍历根节点D , 打印D
 *  中序遍历D的右子树 , 为空 , 进行空操作 , 回退到以B为根结点的子树
 *  中序遍历根节点B , 打印DB
 *  中序遍历B的右子树 , 即以E为根节点的子树
 *  中序遍历E的左子树 , 为空 , 进行空操作
 *  中序遍历根节点E , 打印DBE
 *  中序遍历E的右子树 , 为空 , 进行空操作
 *  回退到以A为根结点的子树中
 *  中序遍历根节点A , 打印DBEA
 *  中序遍历A的右子树 , 即以C为根节点的子树
 *  中序遍历C的左子树 , 即以F为根节点的子树
 *  中序遍历F的左子树 , 为空
 *  中序遍历根节点F , 打印DBEAF
 *  中序遍历F的右子树 , 为空 , 回退到以C为根结点的子树
 *  中序遍历根节点C , 打印DBEAFC
 *  中序遍历C的右子树 , 即以G为根节点的子树
 *  中序遍历G的左子树 , 为空
 *  中序遍历根节点G , 打印DBEAFCG
 *  中序遍历G的右子树 , 为空
 *  至此 , 二叉树的中序遍历完成 , 最终的遍历结果是 : DBEAFCG

##### 非递归版本 #####

//非递归实现BST的中序遍历 LVR , 是按照从小到大排列的
    	/*
    	流程:
    	中序遍历左子树
    	当遍历到最后的叶子节点时 
    	弹出栈顶元素 , 打印
    	然后将该节点的右孩子进行压栈
    	周而复始
    	*/
    	void noninOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		stack<BSTNode*> st;
    		BSTNode* tmp = _root;
    		cout<<"非递归实现 , 中序遍历 : ";
    
    		while(!st.empty() || tmp != nullptr)
    		{
        
    			if(tmp != nullptr)
    			{
        
    				st.push(tmp);
    				tmp = tmp->_left;
    			}
    			else
    			{
        
    				BSTNode* top = st.top();
    				st.pop();
    				cout<<top->_data<<" ";
    				tmp = top->_right;
    			}
    		}
    		cout<<endl;
    	}

##### 递归版本 #####

//递归实现 , 中序遍历
    	void Mid_out()
    	{
        
    		cout<<"递归实现 , 中序遍历 : ";
    		Mid_out(_root);
    		cout << endl;
    	}

//递归实现 , 中序遍历   LVR
    	void Mid_out(BSTNode *node)	
    	{
        
    		if (node != nullptr)
    		{
        
    			Mid_out(node->_left);
    			cout << node->_data << " ";
    			Mid_out(node->_right);
    		}
    	}

#### 后序遍历(LRV) ####

**定义 : 又称为后根遍历 , 其访问规则是如果二叉树为空则进行空操作 , 否则首先后序遍历左子树 , 然后后序遍历右子树 , 最后访问根节点 .**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 2]

流程 :

*  后序遍历从根节点A开始 , 但不直接访问A
 *  后序遍历A的左子树 , 即以B为根节点的子树
 *  后序遍历B的左子树 , 即以D为根节点的子树
 *  后序遍历D的左子树 , 为空 , 进行空操作
 *  后序遍历D的右子树 , 为空 , 进行空操作
 *  后序遍历根节点D , 打印D
 *  回退到以B为根节点的子树
 *  后序遍历B的右子树 , 即以E为根节点的子树
 *  后序遍历E的左子树 , 为空
 *  后序遍历E的右子树 , 为空
 *  后序遍历根节点E , 打印DE
 *  回退到以B为根节点的子树
 *  后序遍历根节点B , 打印DEB
 *  回退到以A为根节点的子树
 *  后序遍历A的右子树 , 即以C为根节点的子树
 *  后序遍历C的左子树 , 即以F为根节点的子树
 *  后序遍历F的左子树 , 为空
 *  后序遍历F的右子树 , 为空
 *  后序遍历根节点F , 打印DEBF
 *  回退到以C为根节点的子树
 *  后序遍历C的右子树 , 即以G为根节点的子树
 *  后序遍历G的左子树 , 为空
 *  后序遍历G的右子树 , 为空
 *  后序遍历根节点G , 打印DEBFG
 *  回退到以C为根节点的子树
 *  后序遍历根节点C , 打印DEBFGC
 *  回退到以A为根节点的子树
 *  后序遍历根节点A , 打印DEBFGCA
 *  至此 , 二叉树的后序遍历完成 , 最终的遍历结果是 : DEBFGCA

##### 非递归版本 #####

//非递归实现BST的后序遍历 LRV
    	/*
    	后序遍历 , 使用一个栈实现是很困难的
    	要牵扯到回退的问题 , 代码层面实现起来有一定的难度
    	那么, 就得使用两个栈 
    
    	先将根节点放入栈1中 
    	以栈不为空作为循环条件
    	将栈1元素弹出
    	并将弹出的元素压入栈2
    	然后按照后续遍历的顺序 , 将该节点的左孩子和右孩子依次入栈
    	周而复始
    	等到栈1全部为空  , 退出循环之后
    	将栈2的元素依次弹出打印
    	*/
    	void nonpostOrder()
    	{
        
    		if(_root == nullptr)
    			return ;
    		stack<BSTNode*>  st1;
    		stack<BSTNode*>  st2;
    		BSTNode* node = _root;
    		st1.push(node);
    		while(!st1.empty())
    		{
        
    			BSTNode* tmp = st1.top();
    			st1.pop();
    			st2.push(tmp);
    			if(tmp->_left != nullptr)
    				st1.push(tmp->_left);
    			if(tmp->_right != nullptr)
    				st1.push(tmp->_right);
    		}
    		cout<<"非递归实现 , 后序遍历 : ";
    		while(!st2.empty())
    		{
        
    			BSTNode* node = st2.top();
    			cout<<node->_data<<" ";
    			st2.pop();
    		}
    		cout<<endl;
    	}

##### 递归版本 #####

//递归实现 , 后序遍历
    	void Last_out()
    	{
        
    		cout<<"递归实现 , 后序遍历 : ";
    		Last_out(_root);
    		cout << endl;

//递归实现 , 后序遍历   LRV
    	void Last_out(BSTNode *node)	
    	{
        
    		if (node != nullptr)
    		{
        
    			Last_out(node->_left);
    			Last_out(node->_right);
    			cout << node->_data << " ";
    		}
    	}

#### 层序遍历(广度优先遍历) ####

**定义 : 遵循的是分层访问原则 . 遍历首先访问树中深度为 0 的那一层中的节点 , 然后再访问深度为 1 的那一层的节点 …  
在访问每一层节点的时候 , 遵循的原则是从左向右 . 直到树中的所有节点都被访问过 .**

##### 非递归版本 #####

// 非递归实现层序遍历(从根节点开始，一层一层按从左向右的顺序打印BST树节点的值)
    	/*
    	广度遍历需要用到队列来完成 , 通过队列的先进先出 , 来实现层序遍历
    	流程 : 
    	1.如果_root为空，直接返回
    	2._root -> queue
    	3.循环判断队列是否为空， 不为空取出队头元素，分别判断左右孩子是否为nullptr，不为空
    	  就要依次入队，然后打印队头元素，继续判断下一个队头元素
    	*/
    	void nonlevelOrder()
    	{
        
    		// 1.如果_root为空，直接返回
    		if(_root == nullptr)
    			return;
    		// 2._root -> queue
    		queue<BSTNode*> que;
    		que.push(_root);
    
    		// 3.循环判断队列是否为空， 不为空取出队头元素，分别判断左右孩子是否为nullptr，不为空
    		// 就要依次入队，然后打印队头元素，继续判断下一个队头元素
    		while(!que.empty())
    		{
        
    			BSTNode *front = que.front();
    			cout<<front->_data<<" ";
    			que.pop();
    			if(front->_left != nullptr)
    			{
        
    				que.push(front->_left);
    			}
    			if(front->_right != nullptr)
    			{
        
    				que.push(front->_right);
    			}
    		}
    	}

##### 递归版本 #####

//递归实现层序遍历
    	/*
    	根据传递的层数进行打印 , 不到指定层不打印
    	*/
    	void levelOrder()
    	{
        
    		cout<<"递归实现层序遍历 : ";
    		int l = level(_root);
    		for(int i = 0; i < l ;++i)
    		{
        
    			levelOrder(_root , i);
    		}
    		cout<<endl;
    	}

//打印一Node为节点的树的层序遍历
    	void levelOrder(BSTNode* node , int n)
    	{
        
    		if(node == nullptr)
    			return;
    		if(n == 0)
    		{
        
    			cout<<node->_data<<" ";
    			return;
    		}
    		levelOrder(node->_left,n-1);
    		levelOrder(node->_right , n-1);
    		
    	}

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70]: /images/20220114/6d72a72f24d74389a7fe5b9b1ce29a8f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 1]: /images/20220114/07ccf3811b5145ab847a7ea9916a3e03.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L05vbnBjMTIz_size_16_color_FFFFFF_t_70 2]: /images/20220114/2527c3fe1b0e4c489758247f3fe0b66f.png