betway必威-betway必威官方网站
做最好的网站

二叉树遍历,数据结构分析之二叉树

二叉树定义这里不再赘述。

概述

在分析树形结构之前,先看一下树形结构在整个数据结构中的位置

图片 1

数据结构

当然,没有图,现在还没有足够的水平去分析图这种太复杂的数据结构,表数据结构包含线性表跟链表,也就是经常说的数组,栈,队列等,在前面的Java容器类框架中已经分析过了,上面任意一种数据结构在java中都有对应的实现,比如说ArrayList对应数组,LinkedList对应双向链表,HashMap对应了散列表,JDK1.8之后的HashMap采用的是红黑树实现,下面单独把二叉树抽取出来:

图片 2

二叉树

由于树的基本概念基本上大家都有所了解,现在重点介绍一下二叉树

图片 3

我这里有个二叉树:

正文

前言

是数据结构中的重中之重,尤其以各类二叉树为学习的难点。一直以来,对于树的掌握都是模棱两可的状态,现在希望通过写一个关于二叉树的专题系列。在学习与总结的同时更加深入的了解掌握二叉树。本系列文章将着重介绍一般二叉树、完全二叉树、满二叉树、线索二叉树、霍夫曼树、二叉排序树、平衡二叉树、红黑树、B树。希望各位读者能够关注专题,并给出相应意见,通过系列的学习做到心中有“树”。

var tree = {
    "id": 0,
    "name": "root",
    "left": {
        "id": 1,
        "name": "Simon",
        "left": {
            "id": 3,
            "name": "Carl",
            "left": {
                "id": 7,
                "name": "Lee",
                "left": {
                    "id": 11,
                    "name": "Fate"
                }
            },
            "right": {
                "id": 8,
                "name": "Annie",
                "left": {
                    "id": 12,
                    "name": "Saber"
                }
            }
        },
        "right": {
            "id": 4,
            "name": "Tony",
            "left": {
                "id": 9,
                "name": "Candy"
            }
        }
    },
    "right": {
        "id": 2,
        "name": "right",
        "left": {
            "id": 5,
            "name": "Carl",
        },
        "right": {
            "id": 6,
            "name": "Carl",
            "right": {
                "id": 10,
                "name": "Kai"
            }
        }
    }
};

二叉树

二叉树(binary tree)是一棵树,其中每个节点都不能有多于两个的儿子。

图片 4

二叉树

1 重点概念

结点是数据结构中的基础,是构成复杂数据结构的基本组成单位。

本系列文章中提及的结点专指树的结点。例如:结点A在图中表示为:

图片 5

1.使用前序遍历,并将所有name输出。

分类

  • 满二叉树:若设二叉树的高度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第h层有叶子结点,并且叶子结点都是从左到右依次排布,这就是完全二叉树。
  • 完全二叉树:除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
  • 平衡二叉树:称为AVL树(区别于AVL算法),它是一棵二叉排序树,且具有以下性质:它是一棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树。

对于完全二叉树,若某个节点数为i,左子节点位2i 1,右子节点为2i 2。

2 树

是n个结点的有限集。n=0时称为空树。在任意一颗非空树中:1)有且仅有一个特定的称为根的结点;2)当n>1时,其余结点可分为m个互不相交的有限集T1、T2、......、Tn,其中每一个集合本身又是一棵树,并且称为根的子树。

此外,树的定义还需要强调以下两点:1)n>0时根结点是唯一的,不可能存在多个根结点,数据结构中的树只能有一个根结点。2)m>0时,子树的个数没有限制,但它们一定是互不相交的。示例树:图2.1为一棵普通的树:

图片 6图2.1 普通树

由树的定义可以看出,树的定义使用了递归的方式。递归在树的学习过程中起着重要作用,如果对于递归不是十分了解,建议先看看递归算法

结点拥有的子树数目称为结点的。图2.2中标注了图2.1所示树的各个结点的度。

图片 7图2.2 度示意图

function getListWithDLR(node) {
    if(node){
        console.log(node.name);
        getListWithDLR(node.left);
        getListWithDLR(node.right);
    }
}
getListWithDLR(tree); //调用函数,并把二叉树传进去。

实现

下面用代码实现一个二叉树

public class BinaryNode {
    Object data;
    BinaryNode left;
    BinaryNode right;
}
2.3 结点关系

结点子树的根结点为该结点的孩子结点。相应该结点称为孩子结点的双亲结点。图2.2中,A为B的双亲结点,B为A的孩子结点。同一个双亲结点的孩子结点之间互称兄弟结点。图2.2中,结点B与结点C互为兄弟结点。

2.使用中序遍历,并将所有name输出。

遍历

二叉树的遍历有两种:按照节点遍历与层次遍历

2.4 结点层次

从根开始定义起,根为第一层,根的孩子为第二层,以此类推。图2.3表示了图2.1所示树的层次关系

图片 8图2.3 层示意图

function getListWithLDR(node) {
    if(node){
        getListWithLDR(node.left);
        console.log(node.name);
        getListWithLDR(node.right);
    }
}
getListWithLDR(tree);
节点遍历
  • 前序遍历:遍历到一个节点后,即刻输出该节点的值,并继续遍历其左右子树(根左右)。
  • 中序遍历:遍历一个节点后,将其暂存,遍历完左子树后,再输出该节点的值,然后遍历右子树(左根右)。
  • 后序遍历:遍历到一个节点后,将其暂存,遍历完左右子树后,再输出该节点的值(左右根)。

构造完全二叉树

图片 9

enter image description here

就以上图的二叉树为例,首先用代码构造一棵完全二叉树
节点类TreeNode

public class TreeNode {
    private int value;
    private TreeNode leftChild;
    private TreeNode rightChild;

    public TreeNode(int value) {
        super();
        this.value = value;
    }

    public int getValue() {
        return value;
    }

    public void setValue(int value) {
        this.value = value;
    }

    public TreeNode getLeftChild() {
        return leftChild;
    }

    public void setLeftChild(TreeNode leftChild) {
        this.leftChild = leftChild;
    }

    public TreeNode getRightChild() {
        return rightChild;
    }

    public void setRightChild(TreeNode rightChild) {
        this.rightChild = rightChild;
    }

}

生成完全二叉树

 //数组
 private int[] saveValue = {0,1, 2, 3, 4, 5, 6};
  private ArrayList<TreeNode> list = new ArrayList<>();
   public TreeNode createTree() {
   //将所有的节点保存进一个List集合里面
        for (int i = 0; i < saveValue.length; i  ) {
            TreeNode treeNode = new TreeNode(saveValue[i]);
            list.add(treeNode);
        }
    //根据完全二叉树的性质,i节点的左子树是2*i 1,右节点字数是2*i 2
         for (int i = 0; i < list.size() / 2; i  ) {
            TreeNode treeNode = list.get(i);
            //判断左子树是否越界
            if (i * 2   1 < list.size()) {
                TreeNode leftTreeNode = list.get(i * 2   1);
                treeNode.setLeftChild(leftTreeNode);
            }
            //判断右子树是否越界
            if (i * 2   2 < list.size()) {
                TreeNode rightTreeNode = list.get(i * 2   2);
                treeNode.setRightChild(rightTreeNode);
            }
        }
        return list.get(0);
    }

前序遍历

   //前序遍历
    public static void preOrder(TreeNode root) {
        if (root == null)
            return;
        System.out.print(root.value   " ");
        preOrder(root.left);
        preOrder(root.right);
    }

遍历结果: 0 1 3 4 2 5 6

中序遍历

   //中序遍历
    public static void midOrder(TreeNode root) {
        if (root == null)
            return;
        midOrder(root.left);
        System.out.print(root.value   " ");
        midOrder(root.right);
    }

遍历结果:3 1 4 0 5 2 6

后序遍历

  //后序遍历
    public static void postOrder(TreeNode root) {
        if (root == null)
            return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.value   " ");
    }

遍历结果:3 4 1 5 6 2 0
上述三种方式都是采用递归的方式进行遍历的,当然也可以迭代,感觉迭代比较麻烦,递归代码比较简洁,仔细观察可以发现,实际上三种遍历方式都是一样的,知识打印value的顺序不一样而已,是一种比较巧妙的方式。

2.5 树的深度

树中结点的最大层次数称为树的深度或高度。图2.1所示树的深度为4。

3.使用后序遍历,并将所有name输出。

层次遍历

二叉树的层次遍历可以分为深度优先遍历跟广度优先遍历

  • 深度优先遍历:实际上就是上面的前序、中序和后序遍历,也就是尽可能去遍历二叉树的深度。
  • 广度优先遍历:实际上就是一层一层的遍历,按照层次输出二叉树的各个节点。

深度优先遍历

由于上面的前序、中序和后续遍历都是采用的递归的方式进行遍历,下面就以前序遍历为例,采用非递归的方式进行遍历

步骤

  • 若二叉树为空,返回:
  • 用一个stack来保存二叉树
  • 然后遍历节点的时候先让右子树入栈,再让左子树入栈,这样右子树就会比左子树后出栈,从而实现先序遍历
//2.前序遍历(迭代)
   public static void preorderTraversal(TreeNode root) {  
       if(root == null){  
           return;  
       }  
       Stack<TreeNode> stack = new Stack<TreeNode>();  
       stack.push(root);  
       while( !stack.isEmpty() ){  
           TreeNode cur = stack.pop();     // 出栈栈顶元素  
           System.out.print(cur.data   " ");  
           //先压右子树入栈
           if(cur.right != null){  
               stack.push(cur.right);  
           }  
           //再压左子树入栈
           if(cur.left != null){  
               stack.push(cur.left);  
           }  
       }  
   }  

遍历结果:0 1 3 4 2 5 6

广度优先遍历

所谓广度优先遍历就是一层一层的遍历,所以只需要按照每层的左右顺序拿到二叉树的节点,再依次输出就OK了

步骤

  • 用一个LinkedList保留所有的根节点
  • 依次输出即可
  //分层遍历
    public static void levelOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.push(root);
        while (!queue.isEmpty()) {
            //打印linkedList的第一次元素
            TreeNode cur = queue.removeFirst();
            System.out.print(cur.value   " ");
            //依次添加每个节点的左节点
            if (cur.left != null) {
                queue.add(cur.left);
            }
            //依次添加每个节点的右节点
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

遍历结果:0 1 2 3 4 5 6

3 二叉树

二叉树是n个结点的有限集合,该集合或者为空集,或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。图3.1展示了一棵普通二叉树:

图片 10图3.1 二叉树

由二叉树定义以及图示分析得出二叉树有以下特点:1)每个结点最多有两颗子树,所以二叉树中不存在度大于2的结点。2)左子树和右子树是有顺序的,次序不能任意颠倒。3)即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。

1)在二叉树的第i层上最多有2i-1 个节点 。2)二叉树中如果深度为k,那么最多有2k-1个节点。3)n0=n2 1 n0表示度数为0的节点数,n2表示度数为2的节点数。4)在完全二叉树中,具有n个节点的完全二叉树的深度为[log2n] 1,其中[log2n]是向下取整。5)若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号,则对完全二叉树中任意一个编号为 i 的结点有如下特性:

若 i=1,则该结点是二叉树的根,无双亲, 否则,编号为 [i/2] 的结点为其双亲结点; 若 2i>n,则该结点无左孩子, 否则,编号为 2i 的结点为其左孩子结点; 若 2i 1>n,则该结点无右孩子结点, 否则,编号为2i 1 的结点为其右孩子结点。

斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

图片 11图3.2 左斜树图片 12图3.3 右斜树

满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。满二叉树的特点有:1)叶子只能出现在最下一层。出现在其它层就不可能达成平衡。2)非叶子结点的度一定是2。3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

图片 13图3.4 满二叉树

完全二叉树:对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。图3.5展示一棵完全二叉树

图片 14图3.5 完全二叉树特点:1)叶子结点只能出现在最下层和次下层。2)最下层的叶子结点集中在树的左部。3)倒数第二层若存在叶子结点,一定在右部连续位置。4)如果结点度为1,则该结点只有左孩子,即没有右子树。5)同样结点数目的二叉树,完全二叉树深度最小。:满二叉树一定是完全二叉树,但反过来不一定成立。

本文由betway必威发布于网页设计,转载请注明出处:二叉树遍历,数据结构分析之二叉树

Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。