精华内容
下载资源
问答
  • 文章目录如何遍历一棵树1.宽度优先搜索(BFS)2.深度优先搜索(DFS)3.Python编程实现 如何遍历一棵树 有两种通用的遍历树的策略: 1.宽度优先搜索(BFS) 我们按照高度顺序一层一层的访问整棵树,高层次的节点将会...

    如何遍历一棵树

    有两种通用的遍历树的策略:

    1.宽度优先搜索(BFS)/广度优先遍历

    我们按照高度顺序一层一层的访问整棵树,高层次的节点将会比低层次的节点先被访问到。
    BFS 需要借助队列来实现 树的广度优先遍历 而不需要迭代
    相关代码:
    Leetcode:面试题32 - I. 从上到下打印二叉树
    面试题32 - II. 从上到下打印二叉树 II
    面试题32 - III. 从上到下打印二叉树 III

    2.深度优先搜索(DFS)

    在这个策略中,我们采用深度作为优先级,以便从跟开始一直到达某个确定的叶子,然后再返回根到达另一个分支。

    从根开始计算,到找到位于某个节点的解,**回溯法(深度优先搜索)**作为最基本的搜索算法,其采用了一种“**一只向下走,走不通就掉头”**的思想(体会“回溯”二字),相当于采用了先根遍历的方法来构造搜索树。

    深度优先搜索策略又可以根据根节点、左子树和右子树的相对顺序被细分为前序遍历中序遍历后序遍历

    (1)前序遍历序列:[根节点,左子树,右子树]

    (2)中序遍历序列:[左子树,根节点,右子树]

    == 拿个铅垂线从左到右依次划过==

    (3)后序遍历序列:[左子树,右子树,根节点]

    下图中的顶点按照访问的顺序编号,按照 1-2-3-4-5 的顺序来比较不同的策略。
    在这里插入图片描述

    3.Python编程实现

    LeetCode中相关题目的Python编程实现:
    (1)105. 从前序与中序遍历序列构造二叉树 \ 面试题07. 重建二叉树
    (2)基于Python实现的链式二叉树结构

    前序遍历/先序遍历

    通过调用树的preorder函数,生成一个关于树的前序迭代器。(yield函数)

    def preorder(self):
        """生成树的前序遍历序列"""
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):  # 开始迭代
                yield p
    
    def _subtree_preorder(self,p):
        yield p                              # 生成根节点
        for c in self.children(p):           # 对每个根节点的左右子树都进行迭代 直至节点为叶节点
            for other in self._subtree_preorder(c):
                yield other
        
    

    后序遍历

    前序遍历和后续遍历的区别在于递归查到子树之后,再生成根节点

    def postorder(self):
        """生成树的后序遍历序列"""
        if not self.is_empty():
            for p in self._subtree_preorder(self.root()):  # 开始迭代
                yield p
    
    def _subtree_preorder(self,p):
        for c in self.children(p):           # 对每个根节点的左右子树都进行迭代 直至节点为叶节点
            for other in self._subtree_preorder(c):
                yield other
        yield p                              # 生成根节点
    

    广度优先遍历

    BFS不是递归,其借助于队列来管理递归。

    from collections import deque
    def bfs(self):
    	if not self.is_empty():
    		a=deque()               # 创建一个空队列
    		a.append(self.root())   # 从根节点开始
    		while not a.is_empty(): # 循环截止条件是队列pop为空
    			p=a.popleft()		# 弹出根节点
    			yield p
    			for c in self.children(p): # 放入每个根节点的子节点 
    				a.append(c)
    
    

    中序遍历

    前三中方法可以用于树的任何结构中,而中序遍历,只能用于二叉树中。
    过程和前序、后序遍历类似,更改根节点和左右子树遍历的位置即可

    def inorder(self):
    	if not self.is_empty():
    		for p in self._subtree_inorder(self.root()):
    			yield p
    
    def _subtree_inorder(self,p):
    	if self.left(p) is not None:          # 遍历左子树
    		for other in self._suntree_inorder(self.left(p)):
    			yield other
    	yield p										# 遍历根节点																		
    	if self.right(p) is not None:				# 遍历右子树
    		for other in self._suntree_inorder(self.right(p)):
    			yield other
    	
    
    展开全文
  • 以前大学学数据结果的时候,我们就知道,根据一棵树的先序遍历和中序遍历,或者后序遍历和中序遍历序列,都可以唯一地确定一棵树
  • ![图片说明](https://img-ask.csdn.net/upload/201911/14/1573731005_872950.png)
  • 一棵树的后序遍历和这棵树对应的二叉树的()相同。 A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 嗯 就这么道题 拆分下题目就是 一棵树的后序遍历 == 这棵树拆成二叉树的中序遍历 下面来解题 文章目录 1.解题 ...

    一棵树的后序遍历和这棵树对应的二叉树的()相同。
    A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历

    嗯 就这么道题

    拆分下题目就是
    一棵树的后序遍历 == 这棵树拆成二叉树的中序遍历
    下面来解题

    1.解题

    来解题
    这题
    其实用试的是很快的~
    还是用这个例子

    【1】普通树的后序遍历

    在这里插入图片描述

    后序遍历 左右中(左后 右后 根)—— 翻译得详细些就是——

    最开始 遍历到(还有左子树的)最深处的节点

    【1】先访问该节点的左子树

    2

    【2】然后访问其余子树(以同样规则访问其余子树—先左后其他)

    56 3 - 4

    【3】最后访问根

    1

    得到结果 2 5634 1

    【2】二叉树的中序遍历

    在这里插入图片描述

    最开始 遍历到(还有左子树的)最深处的节点

    【1】先访问该节点的左子树

    2

    【2】访问该左子树的右子树

    56 3 4

    【3】最后访问根
    1

    同样得到结果 2 5634 1

    一棵树的后序遍历和这棵树对应的二叉树的(B)相同。
    A.先序遍历 B.中序遍历 C.后序遍历 > D.层次遍历

    好的我得到答案了(逃)

    2.更省空间的二叉树表示法

    下面来看看为啥二叉树更节省空间~

    一天一个小知识:二叉树表示法(即左孩子右兄弟表示法)更加节省空间
    (下面解释了 为啥这个表示法叫“左孩子右兄弟表示法~”)
    为啥?
    三叉树中每个节点都存储3个指针域(因为是三叉树嘛 时刻准备着连三个孩子)
    造成有效指针域(指向明确节点的)非常少!
    在这里插入图片描述
    像这个三叉树就有6*3个指针域 但是有效指针域只有5个 浪费13个。

    做个转换
    二叉树
    在这里插入图片描述
    是的 普通树到二叉树的转换就是那么简单
    保留所有左子树的结构 之前是兄弟的 变成右儿子就好了
    咳咳接下来来看看二叉树的效率
    6*2个指针域 同样是5个的有效指针域 浪费了7个指针域。
    很明显 比多叉树要香嘛!!

    其中k元n叉树中的k和n越大 转换成二叉树越省空间!
    n元k叉树浪费的空间——kn -(n-1)
    n元2叉树浪费的空间——2n - (n-1)

    展开全文
  • 不需要使用两个队列来分别存储当前层的节点和下一层的节点,因为在开始遍历一层的节点时,当前队列中的节点数就是当前层的节点数,只要控制遍历这么多节点数,就能保证这次遍历的都是当前层的节点。 [LeetCode] ...

    层次遍历

    使用 BFS 进行层次遍历。不需要使用两个队列来分别存储当前层的节点和下一层的节点,因为在开始遍历一层的节点时,当前队列中的节点数就是当前层的节点数,只要控制遍历这么多节点数,就能保证这次遍历的都是当前层的节点。

    [LeetCode] Average of Levels in Binary Tree 二叉树的层平均值

     

    Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

    Example 1:

    Input:
        3
       / \
      9  20
        /  \
       15   7
    Output: [3, 14.5, 11]
    Explanation:
    The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].
    

     

    Note:

    1. The range of node's value is in the range of 32-bit signed integer.

     

    这道题让我们求一个二叉树每层的平均值,那么一看就是要进行层序遍历了,直接上queue啊,如果熟悉层序遍历的方法,那么这题就没有什么难度了,直接将每层的值累计加起来,除以该层的结点个数,存入结果res中即可,参见代码如下:

    class Solution {
        public List<Double> averageOfLevels(TreeNode root) {
            List<Double> list = new ArrayList<>();
            Queue<TreeNode> queue = new LinkedList<>();
            queue.add(root);
            while(!queue.isEmpty()){
                int size = queue.size();
                double sum = 0;
                for(int i = 0; i < size; i++){
                    TreeNode node = queue.poll();
                    sum += node.val;
                    if(node.left != null)
                        queue.add(node.left);
                    if(node.right != null)
                        queue.add(node.right);
                }
                list.add(sum / size);
            }
            return list;
        }
    }

    展开全文
  • 已知一棵树: 先序遍历(根、左、右): 0137849256 中序遍历(左、根、右): 7381940526 后序遍历(左、右、根): 7839415620 反推 现在根据之前的先序、中序、后序中的两个组合推出原先的二叉树的结构(两两的组合必须...

    本文章的所有代码和相关文章, 仅用于经验技术交流分享,禁止将相关技术应用到不正当途径,滥用技术产生的风险与本人无关。
    本文章是自己学习的一些记录。

    开始

    首先回顾一下,利用已知的一棵二叉树,写出它的先、中、后层次的遍历
    已知一棵树:
    在这里插入图片描述
    先序遍历(根、左、右):
    0137849256

    中序遍历(左、根、右):
    7381940526

    后序遍历(左、右、根):
    7839415620

    反推

    现在根据之前的先序、中序、后序中的两个组合推出原先的二叉树的结构(两两的组合必须包含中序)。

    例如:

    假定有一颗树的先序遍历为:0137849256 中序遍历为:7381940526
    思路:
    1、首先根据先序遍历确定根,根为0,所以根据根是0可以划分为两部分:
    0 和137849256
    2、接下来根据中序遍历的信息(因为知道根是0了),所以可以划分为:
    738194 0 526
    3、再根据先序遍历的137849256 确定为1为左子树的根,所以根据中序的738194就可以划分为:
    738 1 94
    4、又因为中序的738按照左、根、右的思路所以3为根
    5、根据以上的思路分析(可以自己在纸上面画出来),就可以把这棵树画出来了

    在这里插入图片描述

    再例如:

    假定有一颗树的后序遍历为:7839415620 中序遍历为:7381940526
    思路:
    1、根据后序(左、右、根)的顺序,确定根为0,所以后序分为:
    783941562和0
    2、中序(左、根、右)根据后序的信息可以划分为738194 0 526
    所以根据中序738194 0 526的划分,后序的排分的话为783941 562 和0
    所以1为783941子树的根,2为562的根
    3、因为1为根,所以中序的738194 可以划分为738 1 94 ,所以3为738的根,4为94的根

    所以根据上面的思路画出这棵树:
    在这里插入图片描述
    参考资料:传智播客数据结构

    展开全文
  • 根据一棵树的前序遍历与中序遍历构造二叉树
  • java 遍历树的四种方式

    千次阅读 2015-11-18 11:23:28
    java 遍历树的四种方式 最近做个玫瑰图报表,数据源为TreeJson(树状json),在网上搜集下资料,和大家分享。: 先序遍历 中序遍历结 后序遍历结 层次遍历结 package com.wd.fw.crmdocapi.util; import ...
  • 如何遍历一棵二叉树?

    千次阅读 2019-06-13 11:29:14
    package ; import java.util.ArrayList; import java.util.List; public class Tree { private Node root; private List list=new ArrayList(); public Tree(){ init(); } //的初始化:先从叶节点开始,...
  • java 的各种遍历

    千次阅读 2020-07-04 21:42:25
    想了解更多数据结构以及算法题,可以关注微信公众号“数据结构和算法”,...甚至堆我们也可以把它看成是一棵树,树的这么多种类中,我们最常见的应该是二叉树了,下面我们来看一下他的结构。 定义: 1,结点的度: 一个
  • 根据上面的特性,我们可以从后序遍历的最后个数来确定这棵树的根节点,由这个数将中序遍历分割开来,分成 6 2 1 为左子树,3 9为右子树,然后后序遍历也可以由此分成 2 1 6 为左子树,9 3 为右子树,然后2 1 6,6 ...
  • 如何遍历一棵二叉树?

    千次阅读 2018-10-11 15:31:29
    前序遍历:按照“根左右”,先遍历根节点,再遍历左子树 ,再遍历右子 中序遍历:按照“左根右“,先遍历左子树,再遍历根节点,最后遍历右子 后续遍历:按照“左右根”,先遍历左子树,再遍历右子,最后遍历...
  • 有通常三种遍历方法:前序遍历,中序遍历,后序遍历,还有一种层序遍历...对于二叉树来说,如果确定了中序遍历或者层序遍历以后,给出任意一种其他的遍历序列,都可以得到唯一的一棵二叉树。在只给出前序遍历和后...
  • java递归遍历树形list

    千次阅读 2020-06-09 15:02:37
    是遍历树形List,不是生成。当然,因为子节点个数的不确定性,所以,不论是...网上查了一圈,基本都是生成,不是遍历一棵树形List。而且CSDN有些都是错误的。 比如; java递归遍历树结构目录 坑啊。 自己写一个了: ...
  • 假设我们有这样的一棵树: 我们要用不同的方式去遍历。那么我们首先要做的就是,先建立一个个节点,然后再进行连接成树。代码如下: #include iostream> #include string> #include "Queue.h" using ...
  • 根据先序遍历的结果创建一棵树 根据先序遍历的结果还原一棵树 则该树是不确定的 例如 先序遍历的结果ABC 有两种形式 如果要还原一棵树,除了要知道先序遍历的结果,还需要知道树的位置。 如果用#表示空树,...
  • public class Test { public class Tree{ public String data; public Tree left; public Tree right; } public Tree buildTree(String a,String b) { Tree root = new Tree();... ...
  • 1.题目: 根据一棵树的前序遍历与中序遍历构造二叉树。 注意:你可以假设树中没有重复的元素 2.示例: 例如给出: 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下二叉树: 3.分析 1...
  • 中序遍历二叉树
  • 根据一棵树的中序遍历与后序遍历构造二叉树 根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如,给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] ...
  • 三叉多叉树遍历

    2015-04-21 17:50:14
    三叉多叉树遍历 c# 2.0

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 125,111
精华内容 50,044
关键字:

遍历一棵树