非递归实现二叉树先序、中序、后序和层序遍历

清疚 2022-12-29 04:54 155阅读 0赞

### 文章目录 ###

*   *   *  用非递归的方式实现二叉树的先序遍历
         *  用非递归的方式实现二叉树的中序遍历：
         *  用非递归的方式实现二叉树的后序遍历：
         *  用非递归的方式实现二叉树的层次遍历：

> 用递归方式实现二叉树先序、中序和后序遍历很简单。  
> 用递归方法解决的问题都能用非递归的方法实现。递归就是利用函数栈来保存信息，如果用自己申请的数据结构来代替函数栈，也可以实现相同的功能。

全C++实现

### 用非递归的方式实现二叉树的先序遍历 ###

1、申请一个栈stack，然后将头节点压入stack中。

2、从stack中弹出栈顶节点，打印，再将其右孩子节点（不为空的话）先压入stack中，最后将其左孩子节点（不为空的话）压入stack中。

3、不断重复步骤2，直到stack为空，全部过程结束。

/**
     * 定义树节点
     * struct TreeNode {
     *     int data;
     *     TreeNode* left;
     *     TreeNode* right;
     * };
     */
    void prev_iterate(TreeNode* root) {
        
    	stack<TreeNode*> st;		//申请栈存放树节点的指针
    	if (root != NULL) {
        
    		st.push(root);
    		while (!st.empty()) {
        
    			TreeNode* now = st.top();
    			st.pop();
    			printf("%d ", now->data);  //打印树节点的数据,也可以用个数组把它存下来
    			if (now->right != NULL) {
        
    				st.push(now->right);
    			}
    			if (now->left != NULL) {
        
    				st.push(now->left);
    			}
    		}
    	}
    }

### 用非递归的方式实现二叉树的中序遍历： ###

1、申请一个栈stack，初始时令cur=root

2、先把cur压入栈中，依次把左边界压入栈中，即不停的令cur=cur->left，重复步骤2

3、不断重复2，直到为null，从stack中弹出一个节点，记为node，打印node的值，并令cur=node->right,重复步骤2

4、当stack为空且cur为空时，整个过程停止。

/**
     * 定义树节点
     * struct TreeNode {
     *     int data;
     *     TreeNode* left;
     *     TreeNode* right;
     * };
     */
     void  mid_itertor(TreeNode* root) {
        
    	stack<TreeNode*> st;		//申请栈存放树节点的指针
    	TreeNode* cur = root;
    	while (cur != NULL && !st.empty()) {
        
    		while(cur != NULL) {
        
    			st.push(cur);
    			cur = cur->left;
    		}
    		if (!st.empty()){
        
    			cur = st.top();
    			st.pop();
    			printf("%d ", cur->data);  //打印树节点的数据,也可以用个数组把它存下来
    			cur = cur->right;
    		}
    	}
    }

### 用非递归的方式实现二叉树的后序遍历： ###

用非递归的方式实现后序遍历有点麻烦。

1、申请一个栈s1，然后将头节点压入栈s1中。

2、从s1中弹出的节点记为cur，然后依次将cur的左孩子节点和右孩子节点压入s1中。

3、在整个过程中，每一个从s1中弹出的节点都放进s2中。

4、不断重复步骤2和步骤3，直到s1为空，过程停止。

5、从s2中依次弹出节点并打印，打印的顺序就是后序遍历的顺序。

/**
     * 定义树节点
     * struct TreeNode {
     *     int data;
     *     TreeNode* left;
     *     TreeNode* right;
     * };
     */
    void next_itertor(TreeNode* root) {
        
    	stack<TreeNode*> s1, s2;
    	TreeNode* cur = root;
    	if (root != NULL) {
        
    		s1.push(cur);
    		while (!s1.empty()) {
        
    			cur = s1.top();
    			s1.pop();
    			s2.push(cur);
    			if (cur->left != NULL) {
        
    				s1.push(cur->left);
    			}
    			if (cur->right != NULL) {
        
    				s1.push(cur->right);
    			}
    		}
    	}
    	while (!s2.empty()) {
        
    		printf("%d ", s2.top()->data);
    		s2.pop();
    	}
    	putchar(10);
    }

### 用非递归的方式实现二叉树的层次遍历： ###

从二叉树的第一层（根节点）开始，从上至下逐层遍历，在每一层中又按照从左到右的顺序对结点逐个遍历。我们可以看出如果某个结点比同一层的先遍历，其孩子也将比其同层的孩子结点先遍历，这种先进先出的方式，不就是队列这种数据结构吗？

/**
     * 定义树节点
     * struct TreeNode {
     *     int data;
     *     TreeNode* left;
     *     TreeNode* right;
     * };
     */
    void level_iterate(TreeNode* root){
        
    	queue<TreeNode*> que;
    	que.push(root);
    	while (!que.empty()) {
        
    		TreeNode* cur = que.front();
    		que.pop();
    		printf("%d ", cur->data);
    		if (cur->left != NULL) {
        
    			que.push(cur->left);
    		}
    		if (cur->right != NULL) {
        
    			que.push(cur->right);
    		}
    	}
    }