数据结构与算法之美——树分析

符号 阅读:207 2021-06-15 11:20:13 评论:0

一、树

                         

这三个概念的定义比较容易混淆,描述起来也比较空洞。我举个例子说明一下,你一看应该就能明白。

                         

        在我们的生活中,“高度”这个概念,其实就是从下往上度量,比如我们要度量第 10 层楼的高度、第 13 层楼的高度,起点都是地面。所以,树这种数据结构的高度也是一样,从最底层开始计数,并且计数的起点是 0。“深度”这个概念在生活中是从上往下度量的,比如水中鱼的深度,是从水平面开始度量的。所以,树这种数据结构的深度也是类似的,从根结点开始度量,并且计数起点也是 0。“层数”跟深度的计算类似,不过,计数起点是 1,也就是说根节点位于第 1 层。

一、二叉树

       二叉树是树的一种特殊形式。二叉,顾名思义,这种树的每个节点最多有2个孩子节点。这里是最多有2个,也可能只有1个或者没有孩子节点。二叉树还有两种特殊形式,一个叫做满二叉树。  另一个叫做完全二叉树

二、满二叉树

       一个二叉树的左右非叶子节点都存在左右孩子,并且所有叶子节点都在同一层级上,那么这个树就是满二叉树。

                                                    

如图2就是满二叉树。简单来说,满二叉树的每一个分支都是满的。

三、完全二叉树

       

四、存储

       数据结构分为物理结构和逻辑结构。二叉树属于逻辑结构,它可以通过多种物理结构来表达。

       1、链式存储结构

                                                    

        链式存储是二叉树最直观的存储方式。链表是一对一的存储方式,每一个链表节点拥有data变量和一个指向下一节点的next指针。二叉树则稍微复杂一些,一个节点最多可以指向左右两个孩子节点,所以二叉树每一个节点包含三部分。

       ①存储数据的data变量  ②指向左孩子的left指针。③指向右孩子的right指针。 

       2、数组

                                                  

      我们把根节点存储在下标 i = 1 的位置,那左子节点存储在下标 2 * i = 2 的位置,右子节点存储在 2 * i + 1 = 3 的位置。以此类推,B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置,右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

      我来总结一下,如果节点 X 存储在数组中下标为 i 的位置,下标为 2 * i 的位置存储的就是左子节点,下标为 2 * i + 1 的位置存储的就是右子节点。反过来,下标为 i/2 的位置存储就是它的父节点。通过这种方式,我们只要知道根节点存储的位置(一般情况下,为了方便计算子节点,根节点会存储在下标为 1 的位置),这样就可以通过下标计算,把整棵树都串起来。

      不过,我刚刚举的例子是一棵完全二叉树,所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树,其实会浪费比较多的数组存储空间。·

五、二叉树的应用

       二叉树包含许多特殊的形式,每一种形式都有自己的作用,但是其最主要的应用还是在于进行查找操作和维持相对顺序这两个方面。

       1、查找

        二叉树的树形结构使它很适合扮演索引的角色。

        这里我们介绍一种特殊的二叉树:二叉查找树(binary search tree)。顾名思义,这种二叉树的主要作用就是进行查找操作二叉查找树在二叉树的基础上增加了以下几个条件。

        ①如果左子树不为空,则左子树上所有节点的值均小于根节点的值。

        ②如果右子树不为空,则右子树上所有节点的值均大于根节点的值。

        ③左右子树也都是二叉查找树。

        2、维持相对顺序

        二叉查找树要求左子树小于父节点,右子树大于父节点,正是这样保证了二叉树的有序性。因此又叫二叉排序树(binary sort tree)。  

        二叉树的自平衡了。二叉树自平衡的方式有多种,如红黑树,AVL树,树堆

六、二叉树的遍历

        当我们介绍数组、链表时,为什么没有着重研究他们的遍历过程?二叉树的遍历又有什么特殊之处?在计算机程序中,遍历本身是一个线性操作。所以遍历同样具有线性结构的数组或者链表,是一件容易的事情。如

        数组 963852.遍历序列为:9,6,3,8,5,2

        链表 9→6→3→8→5→2遍历顺序为:9,6,3,8,5,2

        而二叉树,是典型的非线性数据,遍历时需要把非线性关联的结点转换成一个线性的序列,以不同的方式来遍历,遍历出的顺序也不同。

       从节点之间位置关系的角度来看,二叉树的遍历分为4种。

       1、前序遍历

       2、中序遍历  

       3、后序遍历

       4、层序遍历

       从更宏观的角度来看,二叉树的遍历归结为两大类。

       1、深度优先遍历(前序遍历、中序遍历、后序遍历)   

       2、广度优先遍历(层序遍历) 

七、深度优先遍历

                                                     

      1、前序遍历

       二叉树的前序遍历,输出顺序是根节点。左子树、右子树。

      2、中序遍历

      二叉树的中序遍历,输出顺序是左子树、根节点、右子树

      3、后序遍历

      二叉树的后序遍历,输出顺序是左子树、右子树、根节点。  

      实际上,二叉树的前、中、后序遍历就是一个递归的过程。比如,前序遍历,其实就是先打印根节点,然后再递归地打印左子树,最后递归地打印右子树。

public class BinaryTree { 
 
    /** 
     * 创建二叉树 
     * @param inputList 
     * @return 
     */ 
    public static TreeNode createBinaryTree(LinkedList<Integer> inputList) { 
        TreeNode node = null; 
        if (inputList == null || inputList.isEmpty()) { 
            return null; 
        } 
        Integer data = inputList.removeFirst(); 
        if (data != null) { 
            node = new TreeNode(data); 
            node.leftChild = createBinaryTree(inputList); 
            node.rightChild = createBinaryTree(inputList); 
        } 
        return node; 
    } 
 
    /** 
     * 二叉树前序遍历 
     * @param node 二叉树节点 
     */ 
 
    public static void preOrderTraveral(TreeNode node){ 
        if (node==null){ 
            return; 
        } 
        System.out.println(node.data); 
        preOrderTraveral(node.leftChild); 
        preOrderTraveral(node.rightChild); 
    } 
 
    /** 
     * 二叉树的中序遍历 
     * @param node 二叉树节点 
     */ 
    public static void inOrderTraveral(TreeNode node){ 
        if (node==null){ 
            return; 
        } 
        inOrderTraveral(node.leftChild); 
        System.out.println(node.data); 
        inOrderTraveral(node.rightChild); 
    } 
 
    /** 
     * 二叉树后序遍历 
     * @param node 二叉树节点 
     */ 
 
    public static void postOrderTraveral(TreeNode node){ 
        if (node==null){ 
            return; 
        } 
        postOrderTraveral(node.leftChild); 
        postOrderTraveral(node.rightChild); 
        System.out.println(node.data); 
    } 
 
    public static void main(String[] args) { 
        LinkedList<Integer> inputList = new LinkedList<Integer>( 
                Arrays.asList(new Integer[]{3,2,9,null,null,10,null,null,8,null,4}) 
        ); 
        TreeNode treeNode=createBinaryTree(inputList); 
        System.out.println("前序遍历:"); 
        preOrderTraveral(treeNode); 
        System.out.println("中序遍历:"); 
        inOrderTraveral(treeNode); 
        System.out.println("后序遍历:"); 
        postOrderTraveral(treeNode); 
    } 
 
    /** 
     * 二叉树节点 
     */ 
    private static class TreeNode { 
        int data; 
        TreeNode leftChild; 
        TreeNode rightChild; 
 
        TreeNode(int data) { 
            this.data = data; 
        } 
    } 
} 

        二叉树用递归方式来实现前序、中序、后序遍历,是最为自然的方式,因此代码也非常简单。

        这3种遍历方式的区别,仅仅是输出的执行位置不同:前序遍历的输出在前,中序遍历的输出在中间,后序遍历的输出在最后。

        代码中值得注意的一点是二叉树的构建。二叉树的构建方法有很多,这里把一个线性的链表转换成非线性的二叉树。链表节点的顺序恰恰是二叉树前序遍历的顺序。链表中的空值,代表二叉树节点的左孩子或右孩子为空的情况。

       在main函数中,通过{3,2,9,null,null,10,null,null,8,null,4}这样一个线性序列,构建的二叉树如下:

                                        ·

八、广度优先遍历

       二叉树的层序遍历,顾名思义,就是二叉树按照从根节点到叶子节点的层次关系,一层一层横向遍历各个节点。·上图二叉树的层序遍历结果为3,2,8,9,10,4。   可是,二叉树同一层次的节点之间是没有直接关联的,如何实现这种层序遍历呢?这个需要一个数据结构来辅助工作,这个数据结构就是队列

 public static void levelOrderTravelsal(TreeNode root) { 
        Queue<TreeNode> queue = new LinkedList<TreeNode>(); 
        queue.offer(root); 
        while (!queue.isEmpty()) { 
            TreeNode node = queue.poll(); 
            System.out.println(node.data); 
            if (node.leftChild != null) { 
                queue.offer(node.leftChild); 
            } 
            if (node.rightChild != null) { 
                queue.offer(node.rightChild); 
            } 
        } 
 
    }

   

            


标签:程序员
声明

1.本站遵循行业规范,任何转载的稿件都会明确标注作者和来源;2.本站的原创文章,请转载时务必注明文章作者和来源,不尊重原创的行为我们将追究责任;3.作者投稿可能会经我们编辑修改或补充。

发表评论
搜索
KIKK导航

KIKK导航

排行榜
关注我们

一个IT知识分享的公众号