二叉树的遍历

本是古典何须时尚 2022-03-10 08:00 129阅读 0赞

# 一、前序遍历 #

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

//结点结构体
    struct Node{
    	//int value;
    	int data;
    	Node *left;//左子树指针
    	Node *right;//右子树指针
    	int lvisited, rvisited;//左、右孩子是否访问过，1表示已访问（此项只在后序非递归算法中需要）
    	Node():lvisited(0), rvisited(0){}
    };

### 递归版本： ###

//前序遍历递归算法
    void preordert(Node* root) {
    	if (root != NULL) {
    		cout << "结点数据：" << root->data << endl;
    		preordert(root->left);//递归左子树
    		preordert(root->right);//递归右子树
    	}
    }

### 非递归版本一： ###

//前序遍历非递归算法--用栈实现
    void preordernonrec(Node* root) {
    	Node *p = NULL;
        stack<Node*> st;
    	if (root != NULL) {
            st.push(root);
    		while (!st.empty()) {
                p = st.top();
                st.pop();
    			cout << p->data << " ";
    			if (p->right != NULL) {//右子树入栈
    				 st.push(p->right);
    			}
    			if (p->left != NULL) {//左子树入栈
    				st.push(p->left);
    			}
    		}
    		cout << endl;
    	}
    }

### 非递归版本二： ###

//非递归前序遍历
    void preorderTraversal(Node *root, vector<int> &path)
    {
    	stack<Node*> s;
    	Node *p = root;
    	while(p != NULL || !s.empty())
    	{
    		while(p != NULL)
    		{
    			path.push_back(p->data);
    			s.push(p);
    			p = p->left;
    		}
    		if(!s.empty())
    		{
    			p = s.top();
    			s.pop();
    			p = p->right;
    		}
    	}
    }

# 二、中序遍历 #

###         中序遍历规则是若二叉树为空，则空操作返回，否则从根结点开始（并不是访问根结点），中序遍历根结点的左子树，然后是访问根结点，再中序遍历右子树。 ###

### 递归版本： ###

//中序遍历递归算法
    void ineordert(Node *root) {
    	if (root != NULL) {
    		ineordert(root->left);
    		cout << "结点数据：" << root->data << endl;
    		ineordert(root->right);
    	}
    }

### 非递归版本一： ###

//中序遍历非递归算法--用栈实现
    void ineordernonrec(Node* root) {
        stack<Node*> st;
    	Node *p = NULL;
    	if (root != NULL) {
    		p = root;
    		while (!st.empty() || p != NULL) {//当栈不为空或root存在的时候，开始遍历左孩子
    			if (p != NULL)//将root进栈，并将指针向左孩子方向移动，直到移动至叶子
    			{
    				st.push(p);
    				p = p->left;
    			}//左孩子部分已遍历完
    			else
    			{
    				p = st.top();//将左孩子放入栈中并准备输出
    				st.pop();
    				cout << p->data << " ";
    				p = p->right;//将指针移动到具有相同父节点的右孩子上
    			}
    		}
    		cout << endl;
    	}
    
    }

### 非递归版本二： ###

//非递归中序遍历
    void inorderTraversal(Node *root, vector<int> &path)
    {
    	stack<Node *> s;
    	Node *p = root;
    	while(p != NULL || !s.empty())
    	{
    		while(p != NULL)
    		{
    			s.push(p);
    			p = p->left;
    		}
    		if(!s.empty())
    		{
    			p = s.top();
    			path.push_back(p->val);
    			s.pop();
    			p = p->right;
    		}
    	}
    }

# 三、后序遍历 #

### 后序遍历规则是若二叉树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后访问根结点。 ###

### 递归版本： ###

//后序遍历递归算法
    void posordert(Node *root) {
    	if (root != NULL) {
    		posordert(root->left);
    		posordert(root->right);
    		cout << "结点数据：" << root->data << endl;
    	}
    }

### 非递归版本一： ###

//后序遍历非递归算法--用栈实现
    //后序非递归遍历思路：因为后序非递归遍历二叉树的顺序是先访问左子树，再访问右子树，最后
    //访问根结点。当用堆栈来存储结点，必须分清返回根结点时，是从左子树返回的，还是从右子树
    //返回的。所以，使用辅助指针r，其指向最近访问过的结点。
    
    void posordernonrec(Node* root) {
    	Node *p = NULL,*r=NULL;
        stack<Node*> st;
    	p = root;
        while (p!=NULL || !st.empty()){
    	    if (p){                             //走到最左边
    			st.push(p);
    		    p = p->left;
          }
    	   else                             //向右
    	  {
    		   p = st.top();//取栈顶结点
    	       if (p->right && p->right != r)//如果右子树存在，且未被访问过
    	       {
    	             p = p->right;
    				 st.push(p);
    			     p = p->left;             //再走到最左
    		   }
    		   else                         //否则，访问栈顶结点并弹出
    		 {
    		        cout << p->data << " ";
    			    r = p;                     //记录该结点
    				st.pop();
    		        p = NULL;                     //结点访问完后，重置p指针
             }
          }
        }
    	cout << endl;
    }

### 非递归版本二： ###

//思路：在结点中增加标志域，记录是否已被访问。
    void posordernonrec(Node* root)//后序非递归遍历
    {
    	Node *p = NULL;
        stack<Node*> st;
    	p = root;
    	while (p != NULL || !st.empty()){
    		  if (p!=NULL && p->lvisited == 0)                     //左走，且左子树未被访问
    		  {
    			      p->lvisited = 1;
    				  st.push(p);
    			      p = p->left;
    		   }
    		  else{
    			      p = st.top();
    			      if (p->right != NULL && p->rvisited == 0)//右子树未被访问，右走一步
    				  {
    				                 p->rvisited = 1;
    				                 p = p->right;
    				   }
    			      else                                 //访问栈顶元素并弹栈
    				  {
    				       cout << p->data << " ";
    					   st.pop();
    				       if (!st.empty())
    					          p = st.top();
    				       else                             //当最后一个元素弹栈出去后，结束
    					          return;
    			      }
    		  }
        }
    	cout << endl;
     }

# 四、层序遍历 #

### 层序遍历规则是若二叉树为空，则空操作返回，否则从树的第一层，也就是根结点开始访问，从上而下逐层遍历，在同一层中，按从左到右的顺序对结点逐个访问。 ###

代码实现：

//层序遍历（广度优先周游）二叉树算法实现（借助队列实现）
    void levelorder(Node* root) {
        queue<Node*> st;
        Node *q;
    	if (root == NULL) return;               //当二叉树判空时，直接返回
        else {
    		st.push(root);                 //根节点存入队列
    		while (front != rear)
    		{
    			q = st.front();
                st.pop();
                cout << q->data << " ";
    			if (q->left != NULL)
    				st.push(q->left); //将左孩子存储至队列尾
    			if (q->right != NULL)
    				st.push(q->right);//将右孩子存储至队列尾
    		}
    	}
    	cout << endl;
    }