平心在线:数据结构——树与二叉树的遍历

admin 4个月前 (07-05) 科技 58 0

目录

  1. 二叉树
  2. 二叉树的遍历
  3. 总结
  4. 参考资料

树是学习数据结构的时刻非常主要的一个数据结构,尤其是二叉树更为主要。像JavaHashMap
就使用了红黑树,而Mysql的索引就使用到了B+树。正好最近刷leetcode碰到了不少的有关
二叉树的问题,今天想着写个总结。

1. 树

1.1 树的观点

树(Tree)是n(n>=0)个优先数据元素的连系。当n=0时,这棵树称之为空树,在一棵非空树T中:

  1. 有一个特殊的元素被称之为根节点,根节点没有前驱节点
  2. 若n>=1,除根节点外,其余元素分为m(m>0)个互不相交的聚集T1、T2、.....、Tn,
    其中每一个聚集又是一棵树,而且称之为根的子树。

图(1-1)  一颗通俗的树

1.2 树的性子

  1. 树的根节点没有前驱节点,除根节点之外所有的节点有且只有一个前驱节点
  2. 树的所有节点可以有零个或者多个后继节点

1.3 其他术语

  • 节点的度:节点所拥有的子树的个数称为该节点的度。

图(1-2)  节点的度
  • 树的度:树中个节点的度的最大值称为该树的度。图1-2中树的度为3.
  • 叶节点:度为0的节点称之为叶节点
  • 分支节点:度不为0的节点称之为分支节点或者非终端节点。一棵树的节点除了叶节点之外,其余的全是分支节点。
  • 孩子、左孩子、右孩子、双亲、兄弟:树的一个节点的子树的根节点称之为这个节点的孩子。
    在二叉树中,左子树的根称之为左孩子,右子树的跟称之为右孩子。反过来这个节点称之为他孩子节点的父节点。
    具有统一个父节点的孩子互称为兄弟
  • 路径、路径长度:若是一棵树中的一串节点n1、n2、......、nk有如下关系:节点ni是节点n(i+1)的父节点,
    就把n1、n2、......、nk称之为一条从n1到nk的路径,这条路径的长度是k-1
  • 节点的层数:划定树的根节点的层数是1,其余节点的层数即是他的父节点的层数+1

图(1-3)  节点的层数 - 有序树和无序树,若是一颗树中各个子树从左到右是有顺序的,则称这棵树是有序的,反之称为无序树。 - 森林:有限棵不相交的树的聚集称之为森林。

2.二叉树

2.1 二叉树的界说

二叉树指书中节点的度不大于2的有序树,是一种最简朴且最主要的树。

递归界说:二叉树是一棵空树或者是一颗由一个根节点和两颗互不相交二叉树组成的非空树。

平心在线:数据结构——树与二叉树的遍历 第1张
图(2-1)  二叉树

特点:

  • 每个节点最多由两棵子树,以是二叉树中不存在度大于2的节点
  • 左子树和有子树是有顺序的,顺序不能随便颠倒
  • 纵然树中某节点只有一颗子树,也要区分他是左子树照样右子树

有关二叉树的一些观点

  • 二叉树的深度:树种节点的最大层数称之为树的深度。
  • 满二叉树:若是一个二叉树每一层的节点数都到达了最大,这颗二叉树就称作满二叉树。
    对于满二叉树,所有的分支节点都存在左子树和右子树,所有的叶结点都在统一层(最下面一层)。图(2-2)就是一颗满二叉树
平心在线:数据结构——树与二叉树的遍历 第2张
图(2-2)  满二叉树 - 完全二叉树:一颗深度为k的有谁人节点的二叉树,对其节点凭据从上至下,从左至右的顺序举行编号,若是编号i(1<=i<=n) 的节点与满二叉树种编号为i的节点在二叉树种的位置相同,则这棵二叉树称之为完全二叉树。完全二叉树的特点是:叶子节点只能出现在最下层 和次最下层,且下层的叶子节点集中在左侧。一棵慢二叉树一定是一颗完全二叉树,而完全二叉树未必是满二叉树。 平心在线:数据结构——树与二叉树的遍历 第3张
图(2-3)  完全二叉树

2.2 二叉树的性子

  • 二叉树的第i层上至多有2(i-1)(i≥1)个节点
  • 深度为h的二叉树中至多含有2的h次方-1个节点
  • 若随便一颗二叉树中右n0个叶子节点,右n2个度为2的节点,则必有n0=n2+1
  • 在完全二叉树中,具有n个节点的完全二叉树的深度为[log2n]+1,其中[log2n]是向下取整。
  • 若对含 n 个结点的完全二叉树从上到下且从左至右举行 1 至 n 的编号,则对完全二叉树中随便一个编号为 i 的结点有如下特征:
  1. 若 i=1,则该结点是二叉树的根,无双亲, 否则,编号为 [i/2] 的结点为其双亲结点;
  2. 若 2i>n,则该结点无左孩子, 否则,编号为 2i 的结点为其左孩子结点;
  3. 若 2i+1>n,则该结点无右孩子结点, 否则,编号为2i+1 的结点为其右孩子结点。

3 二叉树的遍历

二叉树的遍历是指从二叉树的根结点出发,凭据某种顺序一次接见二叉树中所有的节点,使得每个节点被接见且仅接见一次。

二叉树的接见顺序可以分为四种:

  • 前序遍历。接见顺序:父节点——>左子树——>右子树
  • 中序遍历。接见数序:左子树——>父节点——>右子树
  • 后序遍历。接见顺序:左子树——>右子树——>父节点
  • 层序遍历。接见顺序:仅仅需按条理遍历就可以。

节点界说:这里先将后续代码实例的节点举行界说,节点的结构如下:

public class TreeNode {
    public int val;

    public TreeNode left;

    public TreeNode right;

    public TreeNode(int x){
        this.val=x;
    }
}

前序遍历

凭据前面说的,接见顺序:父节点——>左子树——>右子树。那么对于图(2-2)所示的满二叉树
则有以下接见顺序:

平心在线:数据结构——树与二叉树的遍历 第4张
图(3-1)  前序遍历 接见效果为:10、5、3、7、15、12、17
  1. 使用递归举行遍历
public void preorderTraversal(TreeNode root){
    if(root==null) return;
    //先接见根节点
    System.out.println(root.val);
    //接见左子树
    preorderTraversal(root.left);
    //接见右子树
    preorderTraversal(root.left);
}
  1. 使用迭代的方式遍历
    使用迭代的方式需要借助栈来实现。

思量,本着一个节点接见一次的原则,则接见一个节点的时刻 除了将自身的值输出,还需要将两个子节点加入到栈中。
接见两个子树的时刻需先接见左子树,在接见有子树,因此应该先将右孩子入栈(若是有),再将左孩子入栈(若是有)。
然后再将节点出栈重复这个动作。直到栈为空。

public void preorderTraversal(TreeNode root){
    if(root==null) return;
    Stack<TreeNode> stack=new Stack<TreeNode>();
    stack.push(root);
    while (!stack.isEmpty()){
        TreeNode node=stack.pop();
        System.out.println(node.val);
        if(node.right!=null){
            stack.push(node.right);
        }
        if(node.left!=null){
            stack.push(node.left);
        }
    }
}

中序遍历

凭据前面说的,接见顺序:左子树——>父节点——>右子树。那么对于图(2-2)所示的满二叉树
则有以下接见顺序:

平心在线:数据结构——树与二叉树的遍历 第5张
图(3-2)  中序遍历 接见效果为:3、5、7、10、12、15、17
  1. 使用递归遍历
public void middleTraversal(TreeNode root){
    if(root==null) return;
    middleTraversal(root.left);
    System.out.println(root.val);
    System.out.println(root.right);
}
  1. 使用迭代的方式遍历
    使用迭代的方式需要借助栈来实现。

首先接见的顺序是左子树——>父节点——>右子树,我们有的线索就是一个根节点,需要先找到左子树的最左边的节点输出(图(3-2)中的3),
然后输出父节点,再输出右节点,若是沿着最左边的路径所有入栈,那么从栈中弹出的第一个元素就是我们的第一个元素,现在栈顶的元素就是输出的元素的父节点。
输出,父节点已经有了就可以获取到右子树,右子树的根节点入栈,重复这样的动作,代码如下:

public void middleTraversal(TreeNode root){
    if(root==null) return;
    Stack<TreeNode> stack=new Stack<>();
    TreeNode node=root;
    while (node!=null||!stack.isEmpty()){
        while (node!=null){
            stack.push(node);
            node=node.left;
        }
        node=stack.pop();
        System.out.println(node.val);
        node=node.right;
    }
}

后序遍历

凭据前面说的,接见顺序:左子树——>右子树——>父节点。那么对于图(2-2)所示的满二叉树
则有以下接见顺序:

平心在线:数据结构——树与二叉树的遍历 第6张
图(3-3)  中序遍历 接见效果为:3、7、5、12、17、15、10

1)使用递归遍历

public void postorderTraversal(TreeNode root){
    if (root==null) return;
    postorderTraversal(root.left);
    postorderTraversal(root.right);
    System.out.println(root.val);
}
  1. 使用迭代遍历
public List<Integer> postorderTraversalUseStack(TreeNode root){
    if (root==null) return new LinkedList<Integer>();
    Stack<TreeNode> stack=new Stack<>();
    //由于这种设施接见的效果是反序的
    //因此这里使用了一个链表,目的是在头部插入数据
    //这样获得的效果就是目的效果
    //也可以使用ArrayList,再循环反序。
    LinkedList<Integer> res=new LinkedList<>();
    stack.push(root);
    TreeNode node;
    while (!stack.isEmpty()){
        node=stack.pop();
        res.addFirst(node.val);
        //由于要获得的效果是左-右,压栈的时刻若是是正序是应该先右再左
        //然则接见的效果是反的,以是是先左后右
        if(node.left!=null){
            stack.push(node.left);
        }
        if(node.right!=null){
            stack.push(node.right);
        }
    }
    return res;
}

层序遍历

层序遍历会比简朴,只要使用一个行列,盘算每层的长度,便利的时刻凭据左孩子,右孩子的顺序入队即可

public void levelOrder(TreeNode root){
    if(root==null) return;
    Queue<TreeNode> queue=new LinkedList<TreeNode>();
    queue.add(root);
    TreeNode node;
    while (queue.size()!=0){
        int len=queue.size();
        for (int i=0;i<len;i++){
            node=queue.poll();
            System.out.println(node.val);
            if(node.left!=null){
                queue.add(node.left);
            }
            if (node.right!=null){
                queue.add(node.right);
            }
        }
    }
}

4. 总结

本文简朴先容了树的观点与性子,重点先容了二叉树的几种遍历方式,只管递归遍历很简答,然则手写照样会写错,而且一样平常会要求通过迭代来完成。
适才又看到了新的套路,jvm中的迭代的本质就是压栈和弹栈,然后可以把递归转化为迭代。后面另有许多种树的遍历方式。多多学习吧,希望自己能进个大厂喽。

5. 参考资料

  • 数据结构与算法Java版——罗文劼, 王苗, 张小莉编著
  • 深入学习二叉树(一) 二叉树基础
,

欧博亚洲网址

欢迎进入欧博亚洲网址(Allbet Game):www.aLLbetgame.us,欧博官网是欧博集团的官方网站。欧博官网开放Allbet注册、Allbe代理、Allbet电脑客户端、Allbet手机版下载等业务。

欧博开户声明:该文看法仅代表作者自己,与本平台无关。转载请注明:平心在线:数据结构——树与二叉树的遍历

网友评论

  • (*)

最新评论

文章归档

站点信息

  • 文章总数:441
  • 页面总数:0
  • 分类总数:8
  • 标签总数:929
  • 评论总数:127
  • 浏览总数:4557