精华内容
下载资源
问答
  • 递归中序遍历二叉树递归中序遍历二叉树
  • 递归中序遍历二叉树
  • 小小学习,C语言数据结构,中序遍历二叉树递归算法
  • 中序遍历二叉树,非递归实现

    题目

    题目来源 : LeetCode
    中序遍历二叉树,非递归实现
    在这里插入图片描述

    实现

    vector<int> inorderTraversal(TreeNode* root) {
            stack<TreeNode*> s;
            vector<int> ret;
            if(root == NULL){
                return ret;
            }
            TreeNode* cur = root;
            while(s.empty() != 1 || cur){
                while(cur){
                    s.push(cur);
                    cur = cur->left;
                }
                TreeNode* des = s.top();
                ret.push_back(des->val);
                cur = des->right;
                s.pop();
            }
            return ret;
        }
    
    展开全文
  • VC6 0 链式二叉树的中序创建 递归中序遍历递归堆栈中序遍历 中序销毁 求树的深度
  • 二叉树中序遍历递归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;
        }
    }
    
    展开全文
  • 无栈非递归中序遍历二叉树,不用辅助栈,允许改变LLING和RLINK的值
  • 中序遍历二叉树

    2011-12-10 14:09:00
    数据结构实验(c++):中序遍历二叉树递归与非递归算法
  • 中序遍历递归算法在VC6.0环境下运行成功!
  • import java.util.Stack; /** ... * 二叉树递归中序遍历 * @param binaryTree 二叉树 */ public static void inOrder(BinaryTree binaryTree){ if(binaryTree != null){ //先遍历左节点 in.
    import java.util.Stack;
    
    /**
     * 二叉树的中序遍历
     */
    public class InOrder {
    
        /**
         * 二叉树的递归中序遍历
         * @param binaryTree 二叉树
         */
        public static void inOrder(BinaryTree binaryTree){
    
            if(binaryTree != null){
                //先遍历左节点
                inOrder(binaryTree.left);
                //再遍历中间节点
                System.out.println(binaryTree.value);
                //再遍历右节点
                inOrder(binaryTree.right);
            }
        }
    
        /**
         * 非递归中序遍历
         * @param binaryTree 二叉树
         */
        public static void inOrder02(BinaryTree binaryTree){
            BinaryTree node = binaryTree;
            Stack<BinaryTree> stack = new Stack<>();
            //终止条件
            while(!stack.isEmpty() || node != null){
                //循环的把左节点加入到栈中,直到二叉树的左节点为空
                while(node != null){
                    stack.push(node);
                    //当前节点等于它的左节点
                    node = node.left;
                }
                //栈不为空的情况下再遍历
                if(!stack.isEmpty()){
                    node = stack.pop();
                    System.out.println(node.value);
                    //右节点
                    node = node.right;
                }
            }
        }
    
        /**
         * 非递归中序遍历
         * @param binaryTree 二叉树
         */
        public static void inOrder03(BinaryTree binaryTree){
            BinaryTree node = binaryTree;
            Stack<BinaryTree> stack = new Stack<>();
            if(node == null){
                return;
            }
            //终止条件
            while(!stack.isEmpty() || node != null){
                if(node != null){
                    stack.push(node);
                    node = node.left;
                }
                //栈不为空的情况下再遍历
                else{
                    node = stack.pop();
                    System.out.println(node.value);
                    //右节点
                    node = node.right;
                }
            }
        }
    
        /**
         * 测试结果
         * @param args
         */
        public static void main(String[] args){
            //新建二叉树
            BinaryTree root = new BinaryTree(1);
            BinaryTree left = new BinaryTree(2);
            BinaryTree right = new BinaryTree(3);
            BinaryTree left02 = new BinaryTree(4);
            BinaryTree right02 = new BinaryTree(5);
            BinaryTree right03 = new BinaryTree(6);
            left.right = right02;
            left.left = left02;
            root.left = left;
            root.right = right;
            right02.left = right03;
    
            //中序遍历二叉树递归方式
            inOrder(root);
            System.out.println("-----------------");
            inOrder02(root);
    
        }
        /*测试结果
         *
         * 426513
         * -----------------
         * 426513
         */
    
    }
    
    //二叉树的类
    class BinaryTree{
        int value;
        BinaryTree left;
        BinaryTree right;
    
        public BinaryTree(int value){
            this.value = value;
        }
    }
    

     

    展开全文
  • 中序遍历二叉树 递归算法 def inorderTraversal(root): f = self.inorderTraversal return f(root.left)+[root.val]+f(root.right) if root else [] 非递归算法 def inorderTraversal(root): stack, res...

    中序遍历二叉树

    递归算法

    def inorderTraversal(root):
    	f = self.inorderTraversal
    	return f(root.left)+[root.val]+f(root.right) if root else []
    

    非递归算法

    def inorderTraversal(root):
    	stack, res = [(root, False)], []
    
    	while stack:
    		node, seen = stack.pop()
    		if node:
    			if seen:
    				res.append(node.val)
    			else:
    				stack.extend([(node.right, False), (node, True), (node.left, False)])
    	
    	return res
    

    参考文献:

    1. 94. Binary Tree Inorder Traversal - LeetCode
    2. 这是印象笔记中的笔记,如果是在CSDN手机APP上查看此博客,请在印象笔记手机APP中搜索该参考文献:https://app.yinxiang.com/shard/s44/nl/9329661/03e72aa2-2620-4448-a07d-37216fbb43ea。
    展开全文
  • 之前了解过了二叉树的先序遍历的递归以及非递归的过程,在此基础上再来认识下二叉树中序遍历递归以及非递归的过程。    二叉树中序遍历递归过程很简单,在非空二叉树中,首先中序遍历左子树,然后访问...
  • 中序遍历二叉树 题目链接:中序遍历二叉树 解法一: 递归遍历比较简单 public List&amp;lt;Integer&amp;gt; inorderTraversal(TreeNode root) { List&amp;lt;Integer&amp;gt; result = new ...
  • 二叉树中序遍历 上篇我简单的给大家介绍了一下二叉树的先序遍历,那么这次我就给大家介绍一下二叉树的中序遍历 请看大屏幕 。...首先让我们来看看如何递归的去中序遍历二叉树 注:在这里我特别强调一点...
  • 递归中序遍历二叉树算法详解

    万次阅读 多人点赞 2017-11-11 11:10:07
    我们如果不适用递归中序遍历二叉树即实现输出二叉树中的全部数据并且每个节点只访问一次的操作。那么在我们的算法中是通过单独开内存来保存节点数据,我们这个内存指的其实就是我们学过的栈数据结构S
  • 之前提到用递归的方法实现中序遍历二叉树,但是递归会浪费大量的空间与时间。这时候我们就在想用没有一种方式能够不依赖递归去实现遍历二叉树。我们之前学过一种数据结构可以实现这种方法,那就是链表。 话不多说,...
  • 在此之前,我们已经学习了中序遍历二叉树递归算法,相信大家已经将其牢牢掌握了. 除了使用递归思想作为求解问题的钥匙,还可以借助栈来以非递归方式实现该问题的求解. 首先,我们要讨论存储二叉树结点信息的栈...
  • 二叉树中序遍历递归+非递归)Java

    千次阅读 2019-10-24 14:39:09
    中序遍历(非递归)代码图解新的改变功能快捷键合理的创建标题,有助于目录的生成如何改变文本的样式插入链接与图片如何插入一段漂亮的代码片生成一个适合你的列表创建一个表格设定内容居中、居左、居右SmartyPants...
  • 百度面试题 手写中序遍历二叉树递归 和 链栈 百度面试题 手写中序遍历二叉树递归 和 链栈 百度面试题 手写中序遍历二叉树递归 和 链栈 百度面试题 手写中序遍历二叉树递归 和 链栈
  • 二叉树中序遍历递归算法 目标遍历的二叉树: 1 / \ 2 4 / \ 3 5 待输出结果为3,2,5,1,4 1.首先得用上面定义的结构体把这颗树表示出来 2.表示出这颗树后在调用二叉树中序遍历递归算法 */...
  • 二叉树中序遍历递归 #include <iostream> #include<stack> using namespace std; struct BiTree { int data; BiTree *lChild, *rChild; BiTree() { data = 0; lChild = NULL; rChild = NULL...
  • LeetCode #94 中序遍历二叉树 import java.util.ArrayList; import java.util.List; class Solution_94 { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ...
  • 利用栈的基本操作实现二叉树中序遍历递归算法。
  • 在此内容之上增加了中序遍历二叉树的非递归的两种实现、线序遍历统计二叉树的叶子数、二叉树的深度 //中序遍历二叉树递归  public void InOrderTraverse(BinaryNode node){  Stack stack=new Stack();  if...
  • 中序遍历二叉树的过程如下: 二叉树的存储结构: typedef struct node{ int data; struct node * lchild; //指向左孩子的结点 struct node * rchild; //指向右孩子的结点 }BTNode; 思路: 1.遍历左子树节点 2...
  • 中序遍历递归方法: ... 而在非递归调用中序遍历二叉树中,利用栈的LIFO的特点。因为中序遍历从二叉树最左的节点开始遍历,然后其父节点,最后父节点的右子树。因此算法为: 1.1.初始化当前指针cur指向

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 63,495
精华内容 25,398
关键字:

中序遍历二叉树的递归执行图