精华内容
下载资源
问答
  • 二叉树中序遍历非递归Java

    问题来源与描述

    问题来源:LeetCode 94,二叉树的中序遍历

    思路

    二叉树的中序遍历顺序是左,根,右。
    使用递归比较简单:

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            inorder(res, root);
            return res;
        }
        public void inorder(List<Integer> res, TreeNode root) {
            if (root == null) return;
            inorder(res, root.left);
            res.add(root.val);
            inorder(res, root.right);
        }
    }
    

    非递归的思路是用一个栈,两个while循环,节点非空则入栈,并将其左孩子,左孩子的左孩子,左孩子的左孩子的左孩子。。。入栈,出栈时,记录下当前节点的值,如果有右孩子,则指针指向右孩子,循环,同上,将左孩子入栈。

    class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new LinkedList<>();
            Deque<TreeNode> stack = new LinkedList<>();
            TreeNode temp = root;
            while (temp != null || !stack.isEmpty()) {
                while (temp != null) {
                    stack.push(temp);
                    temp = temp.left;
                }
                temp = stack.pop();
                res.add(temp.val);
                temp = temp.right;
            }
            return res;
        }
    }
    
    展开全文
  • 之前了解过了二叉树的先序遍历的递归以及非递归的过程,在此基础上再来认识下二叉树中序遍历的递归以及非递归的过程。    二叉树中序遍历的递归过程很简单,在非空二叉树中,首先中序遍历左子树,然后访问...

    @author Zero Sharp on 2019/08/16
    数据结构学习分享

      之前了解过了二叉树的先序遍历的递归以及非递归的过程,在此基础上再来认识下二叉树中序遍历的递归以及非递归的过程。

       二叉树中序遍历的递归过程很简单,在非空二叉树中,首先中序遍历左子树,然后访问根节点,然后再中序遍历右子树。用 C++ 表述如下:

    void inOrderTraversal(Node * root)
    {
        if(root != NULL)
        {
            inOrderTraversal(Node * root->left);   //递归遍历根结点左子树
            cout << root->data << endl;            //访问根结点
            inOrderTraversal(Node * root->right);  //递归遍历根结点右子树
        }
    }
    

      那如何非递归遍历呢?其实这个个先序遍历类似,都是模拟堆栈的操作。已知当前结点为 pNode。其大致思路如下:

    中序的非递归实现过程如下:

    1. 把 pNode 放入栈中
    2. 遍历当 pNode 的左子树。
    3. 左子树遍历完后,pNode 出栈并被访问。
    4. 遍历 pNode 的右子树。

    同样举个例子来了解下这个过程。
    现有如下二叉树:
    二叉树示例

    非递归遍历过程如下(详细到每一步):

    一、指针指向A,A入栈

    此时栈中元素为 A ,当前结点为 A 。(从左往右依次从栈顶到栈底)

    二、指针指向A 的左孩子 B,且A 的左孩子 B 入栈。

    此时栈中元素为 BA ,当前结点为 B

    三、B的左孩子为 NULL,指针指向 NULL,不进行入栈操作。

    此时栈中元素为 BA ,当前结点为 NULL

    四、指针指向 NULL,因此弹出栈顶 B,指针指向 B 并访问 B。

    此时栈中元素为 A ,当前结点为 B

    五、B 的右孩子为 NULL,指针指向 NULL,不入栈,故弹出栈顶 A,指针指向 A 并访问 A。

    此时栈已空 ,当前结点为 A

    六、指针指向 A 的右孩子 C,且 C 入栈。

    此时栈中元素为 C ,当前结点为 C

    七、指针指向 C 的左孩子 D,且 D 入栈

    此时栈中元素为 DC ,当前结点为 D

    八、D 的左孩子为 NULL,指针指向 NULL,不进行插入操作。

    此时栈中元素为 DC ,当前结点为 NULL

    九、指针指向 NULL,因此弹出栈顶 D,指针指向 D 并访问 D。

    此时栈中元素为 C ,当前结点为 D

    十、D 的右孩子为 NULL,指针指向 NULL,不入栈,故弹出栈顶 C,指针指向 C 并访问 C。

    此时栈已空,当前结点为 C

    十一、指针指向 C 的右孩子 E ,且 E 入栈。

    此时栈中元素为 E ,当前结点为 E

    十二、E 的左孩子为 NULL,指针指向 NULL,不进行插入操作。

    此时栈中元素为 E ,当前结点为 NULL

    十三、指针指向 NULL,因此弹出栈顶 E,指针指向 E 并访问 E

    此时栈已空,当前结点为 E

    十四、D 的右孩子为 NULL,指针指向 NULL

    此时栈已空,当前结点为 NULL,遍历结束 。

    下面给出这个算法的流程图:

    中序非递归遍历算法流程图

    下面是这个算法的 C++ 描述:

    #include <iostream>
    #include <stack>
    #include <string>
    using namespace std;
    
    typedef struct TreeNode Node;
    struct TreeNode
    {
        Node* left;
        Node* right;
        string data;
    };
    
    void inOrderTraversal(Node * root)
    {
        stack<Node *> s;
        Node * pNode = root;
        while(pNode != NULL || !stack.empty())
        {
            if(pNode != NULL)
            {
                s.push(pNode);              //当前结点入栈
                pNode = pNode->left;	    //转向左子树
            }
            else
            { 
                pNode = s.top();   
                cout << s.data << endl;     //读取栈顶数据
                s.pop();                    //栈顶弹出
                pNode = pNode->right;       //转向右子树
            }
        }
    }
    

    这个 非递归的中序遍历算法,个人感觉上面这样写比较高效,如果有错误的地方,还请大家指正,谢谢!

    展开全文
  • 二叉树中序遍历非递归算法 目标遍历的二叉树: 1 / \ 2 4 / \ 3 5 待输出结果为3,2,5,1,4 1.首先得用上面定义的结构体把这颗树表示出来 2.表示出这颗树后在调用二叉树中序遍历非递归算法 */...
    /*
    	二叉树的中序遍历非递归算法
    	目标遍历的二叉树:
    		 1
    		/ \
    	   2   4
    	  / \
    	 3   5	
    	待输出结果为3,2,5,1,4
    	1.首先得用上面定义的结构体把这颗树表示出来
    	2.表示出这颗树后在调用二叉树的中序遍历非递归算法
    */
    

    在这里插入图片描述

    #include <iostream>
    using namespace std;
    # define maxSize 10
    //树结点的结构体,存储的是int整型的数据
    typedef struct BTNode{
    	int data;
    	struct BTNode *lchild;
    	struct BTNode *rchild;
    }BTNode;
    
    /*
    	二叉树的中序遍历非递归算法
    	目标遍历的二叉树:
    		 1
    		/ \
    	   2   4
    	  / \
    	 3   5	
    	待输出结果为3,2,5,1,4
    	1.首先得用上面定义的结构体把这颗树表示出来
    	2.表示出这颗树后在调用二叉树的中序遍历非递归算法
    */
    
    void createBTree(BTNode *&p)
    {	
    	/*
    		生成这颗树,这里就是直接按照二叉树的样子来逐一生成
    		p做为根结点(root)
    	*/
    	p = (BTNode*)malloc(sizeof(BTNode));
    	p->data = 1;
    	BTNode *n2, *n3, *n4, *n5 ;//分别对应存储元素2,3,4,5的4个结点
    	n2 = (BTNode*)malloc(sizeof(BTNode));
    	n3 = (BTNode*)malloc(sizeof(BTNode));
    	n4 = (BTNode*)malloc(sizeof(BTNode));
    	n5 = (BTNode*)malloc(sizeof(BTNode));
    	n2->data = 2;
    	n3->data = 4;
    	n4->data = 3;
    	n5->data = 5;
    	p->lchild = n2;
    	p->rchild = n3;
    	n2->lchild = n4;
    	n2->rchild = n5;
    	n3->lchild = n3->rchild = NULL;
    	n4->lchild = n4->rchild = NULL;
    	n5->lchild = n5->rchild = NULL;
    }
    void inorderNonrecursion(BTNode *p){
    	
    	if (p != NULL){
    		BTNode *q;
    		BTNode *stack[maxSize];			//定义一个栈
    		int top = -1;					//初始栈
    		
    		q = p;
    		while (top != -1 || q != NULL)
    		{
    			while (q != NULL)
    			{
    				stack[++top] = q;
    				q = q->lchild;
    			}
    			
    			if (top != -1)
    			{
    				q = stack[top--];
    				cout << q->data << endl;
    				q = q->rchild;
    			}
    		}
    
    	}
    }
    
    int main()
    {
        BTNode *p;
    	createBTree(p);
    	inorderNonrecursion(p);
        return 0;
    }
    
    
    展开全文
  • * 二叉树中序遍历非递归算法。 * 主要思路: * 用一个栈维护所有有左孩子的节点。 * 1、当一个节点有左孩子时,就把这个节点进栈。 * 2、然后检查这个节点的左孩子节点是不是有左孩子,如果有,则这个左...

    课后习题:

    /**
    	 * 二叉树中序遍历非递归算法。
    	 * 主要思路:
    	 * 用一个栈维护所有有左孩子的节点。
    	 * 1、当一个节点有左孩子时,就把这个节点进栈。
    	 * 2、然后检查这个节点的左孩子节点是不是有左孩子,如果有,则这个左孩子入栈,然后循环,
    	 * 3、如果没有,则输出此左孩子的值,然后判断此左孩子有无右孩子,
    	 * 4、有则将这右孩子做第1步。
    	 * 5、没有,则让栈顶的元素出栈,输出此节点的值
    	 * 6、然后判断此节点有无右孩子,有,则让这个右孩子做第1步检查。
    	 * 7、如果没有,则用第6步检查此时栈顶的元素节点。
    	 * 8、当栈为空时则所有节点遍历完毕。
    	 * @param root 二叉树根节点
    	 */
    	public void inBTreeN(BTreeNode root) {
    		if(root == null) return;
    		//用栈存储所有有左孩子的节点
    		SequenceStack ss = new SequenceStack();
    		BTreeNode tNode = root;
    		//用于区别此次循环是检查左孩子还是检查右孩子
    		int k = 1;
    		//tNode != null用于处理根元素没有左节点的情况,此时一次循环后,栈还是为空
    		while(tNode != null){
    			if(k == 1 && tNode.left != null) {
    				//有左孩子,且此节点没有被遍历检查,则入栈
    				ss.push(tNode);
    				tNode = tNode.left;
    				//下一个检查的还是左孩子
    				k = 1;
    			}else{
    				//如果没有左孩子,则输出此节点的值
    				System.out.print(tNode.value + ",");
    				//如果右孩子不为null,则检查右孩子,但右孩子不入栈
    				if (tNode.right != null) {
    					tNode = tNode.right;
    					//下一步检查右孩子的左孩子
    					k = 1;
    				} else {
    					//如果栈为空,遍历完成
    					if (ss.isEmpty()) {
    						break;
    					}
    					//没有右孩子,则栈出栈
    					tNode = (BTreeNode)ss.pop();
    					//输出出栈元素的节点值
    					System.out.print(tNode.value + ",");
    					//判断有无右孩子,确定下一次循环的节点
    					if (tNode.right == null) {
    						//如果栈空,则遍历完成
    						if (ss.isEmpty()) {
    							break;
    						}
    						//没有右孩子,则再出一个栈,即检查前一步出栈的节点的父节点
    						tNode = (BTreeNode)ss.pop();
    						//设置只检查右孩子,因为所有栈里的节点的左孩子都已经遍历
    						k = 2;
    					} else {
    						//如果有右孩子,则检查此右孩子
    						tNode = tNode.right;
    						//设置检查左孩子,每检查一个新元素,都先检查其左孩子
    						k = 1;
    					}
    				}
    			}
    			
    		}
    	}


    
    
    package tree;
    
    public class BTreeNode {
    	public Object value;
    	public BTreeNode left;
    	public BTreeNode right;
    	public BTreeNode(Object obj){
    		this.value = obj;
    	}
    	public BTreeNode(Object o, BTreeNode l, BTreeNode r){
    		this.value = o;
    		this.left = l;
    		this.right = r;
    	}
    }


    展开全文
  • 二叉树中序遍历非递归实现   近日在刷Leetcode中有一道题,让你用非递归的方法实现二叉树的先序和中序遍历,先序遍历好说,根左右的顺序,维护一个栈,每次pop栈顶元素,访问,然后将其右节点,左节点依次压入...
  • 二叉树中序遍历非递归算法详解

    千次阅读 2013-04-25 14:36:04
    二叉树中序遍历非递归详解 1. 首先给出一颗二叉树,如下图所示: 图1 一颗简单的二叉树 根据二叉树的中序遍历的特性,该二叉树中序遍历顺序为:DBGEACHFI; 2. 一般遍历一颗二叉树,先序中序或者后序,...
  • 根据中序遍历的顺序,对于任一结点,优先访问其左孩子,而左孩子结点又可以看做一根结点,然后继续访问其左孩子结点,直到遇到左孩子结点为空的结点才进行访问,然后按相同的规则访问其右子树。因此其处理过程如下。...
  • 1.二叉树中序遍历 首先看一下递归方式的实现方式: class TreeNode: left = None right = None var = 0 def __init__(self, var): self.var = var def inOrder(root): if root == None: ...
  • VC6 0 链式二叉树的中序创建 递归中序遍历 非递归堆栈中序遍历 中序销毁 求树的深度
  • 本文主要将前序遍历、中序遍历、后序遍历的非递归方法。 递归方法和层序遍历请看 递归前序遍历、递归中序遍历、递归后序遍历、层序遍历和判断一棵树是否为完全二叉树 非递归前序遍历二叉树 第一种方法: 利用栈实现 ...
  • 二叉树具有一些特定的性质,如 n0 = n2+1,在一些应用中,常常要求在树中查找具有某些特征的节点,或者对树中节点进行处理,即遍历二叉树的问题,其递归算法非常容易实现,非递归算法也有两种思路,本文将在程序中...
  • 二叉树中序遍历的非递归算法同样可以使用栈来实现,从根结点开始,将根结点的最左结点全部压栈,当...二叉树中序遍历非递归算法如下: struct TreeNode { int val; TreeNode *left; TreeNode * right; ...
  • 二叉树中序遍历(非递归实现)

    万次阅读 多人点赞 2018-01-04 20:37:39
    一、递归实现前序,序,后序遍历;对于二叉树,前面已经采用...下面,以实现中序遍历二叉树为主题展开:二、非递归实现 中序遍历:1,结构: 首先,对于中序遍历,我们知道,原则是先走到的结点后访问,后走到的结点
  • 二叉树中序遍历(非递归)算法实现--C语言

    千次阅读 多人点赞 2018-12-14 10:50:25
    昨天写了一遍二叉树的先序遍历(非递归)算法,今天写一下二叉树二叉树中序遍历非递归)算法。中序遍历非递归算法有两种,但是个人觉得只要掌握一种就可以了,只要自己的逻辑清晰,会哪一种又有什么关系呢~ ...
  • 二叉树先序遍历、中序遍历、后序遍历的非递归解法中序遍历 非递归先序遍历 非递归后序遍历 非递归 这里总结了非递归的不同解法 中序遍历 非递归 //中序遍历 非递归 void inorderTraservel(TreeNode root){ TreeNode...
  • 二叉树中序遍历的非递归算法同样可以使用栈来实现,从根结点开始,将根结点的最左结点全部... 二叉树中序遍历非递归算法实现如下: #include <stdlib.h> #include <stdio.h> #define MAXSIZE 1...
  • python 二叉树中序遍历非递归方法

    千次阅读 2018-09-27 15:50:00
    # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution94(object): ######二叉树中序遍历非递归方法,用栈 ...
  • 二叉树的前序遍历 中序遍历 后序遍历 层次遍历的递归与非递归实现
  • 二叉树中序遍历 上篇我简单的给大家介绍了一下二叉树的先序遍历,那么这次我就给大家介绍一下二叉树的中序遍历 请看大屏幕 。。。。 上图是一棵二叉树,中序遍历结果:4 2 5 1 3 6 同理,我想你可能会问什么...
  • 用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
  • 利用栈的基本操作实现二叉树中序遍历非递归算法。
  • C语言实现二叉树中序遍历非递归),本人亲自写的!
  • 二叉树中序遍历(递归+非递归)Java

    千次阅读 2019-10-24 14:39:09
    中序遍历非递归)代码图解新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants...
  • 详细图解二叉树中序遍历非递归)二叉树中序递归含义LeetCode题目94详细图解源代码运行结果 二叉树中序递归含义 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树。若二叉树为空则结束返回,否则: (1)...
  • 用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
  • 1.1传统的非递归前序遍历 1.2根据递归改来的 2.中序遍历 3.后序遍历 1.前序遍历 LeetCode《二叉树的前序遍历》 前序遍历有两种常见的,一种是传统的,类似于中序遍历 1.1传统的非递归前序遍历 /** * ...
  • 中序遍历的特点“左-根-右”,访问完一个节点之后,立刻转到其右子节点递归处理。 特别注意外层while循环的条件。 /* 二叉树节点结构 */ struct BinaryTreeNode { int data; BinaryTreeNode* lchild; ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 33,421
精华内容 13,368
关键字:

二叉树中序遍历非递归