• “两学一做”在山西——黄河新闻网 2019-07-13
  • 内地生报读香港高校本科人数持续下跌 2019-07-13
  • 【学习时刻】人民大学王义桅:金砖合作的“自信”与“自觉” 2019-07-12
  • 女子请“私家侦探”被骗3万 警方循线捣毁诈骗团伙 2019-07-11
  • 【学习时刻】北交大马院院长韩振峰:高校思想政治工作必须牢牢把握三大根本问题 2019-07-11
  • 全国“非遗”保护工作先进名单公布 2019-07-01
  • 紫光阁中共中央国家机关工作委员会 2019-06-25
  • 杭州控烟令修改草案拟允许室内设吸烟区,控烟专家:跌破眼镜 2019-06-25
  • 挪用近30万报纸征订款赌博 河南一报社聘用制干部获刑 2019-06-23
  • 2016年,有1145家上市公司大小非减持了3600亿元,还有210名上市公司高管减持了1400亿元。IPO已成了造就成千上万个十亿、百亿富豪的捷径, 2019-06-21
  • 专家“把脉”中国电影市场:提升品质方能逆袭 2019-06-21
  • “善款资助副局长儿子留学”真相须尽快落地 2019-06-19
  • 21岁女护士失联2天后确认遇害 嫌疑人为其前男友 2019-06-19
  • 中国地质公园名录旅行地中国国家地理网 2019-06-13
  • 玄关运用有四大原则 用的好才能财旺挡煞聚财 ——凤凰网房产 2019-06-10
  • 数据结构与算法---树结构(Tree structure)

    为什么需要树这种数据结构

    数组存储方式的分析

    • 优点:通过下标方式访问元素,速度快。对于有序数组,还可使用二分查找提高检索速度。
    • 缺点:如果要检索具体某个值,或者插入值(按一定顺序)会整体移动,效率较低。

    广东十一选5一定牛 www.aavbg.com

    链式存储方式的分析

    • 优点:在一定程度上对数组存储方式有优化(比如:插入一个数值节点,只需要将插入节点,链接到链表中即可, 删除效率也很好)。
    • 缺点:在进行检索时,效率仍然较低,比如(检索某个值,需要从头节点开始遍历) 

    树存储方式的分析

     能提高数据存储,读取的效率,  比如利用 二叉排序树(Binary Sort Tree),既可以保证数据的检索速度,同时也可以保证数据的插入,删除,修改的速度。

     

    树结构示意图

     

    二叉树的概念

    1. 树有很多种,每个节点最多只能有两个子节点的一种形式称为二叉树。
    2. 二叉树的子节点分为左节点右节点。 
    3. 如果该二叉树的所有叶子节点都在最后一层,并且结点总数= 2^n -1 , n 为层数,则我们称为满二叉树。
    4. 如果该二叉树的所有叶子节点都在最后一层或者倒数第二层,而且最后一层的叶子节点在左边连续,倒数第二层的叶子节点在右边连续,我们称为完全二叉树。

     

    二叉树遍历的说明

    前序遍历: 先输出父节点,再遍历左子树和右子树

    中序遍历: 先遍历左子树,再输出父节点,再遍历右子树

    后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点

    小结: 看输出父节点的顺序,就确定是前序,中序还是后序

     示例:

    将下列二叉树 前序、中序、后序输出

      1 package com.tree;
      2 
      3 /**
      4  * Created by wanbf on 2019/7/9.
      5  */
      6 
      7 public class BinaryTreeDemo {
      8 
      9     public static void main(String[] args) {
     10         //先需要创建一颗二叉树
     11         BinaryTree binaryTree = new BinaryTree();
     12         //创建需要的结点
     13         HeroNode root = new HeroNode(1, "宋江");
     14         HeroNode node2 = new HeroNode(2, "吴用");
     15         HeroNode node3 = new HeroNode(3, "卢俊义");
     16         HeroNode node4 = new HeroNode(4, "林冲");
     17         //HeroNode node5 = new HeroNode(5, "关胜");
     18 
     19         //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
     20         root.setLeft(node2);
     21         root.setRight(node3);
     22         node3.setRight(node4);
     23         //node3.setLeft(node5);
     24         binaryTree.setRoot(root);
     25 
     26         //测试
     27         System.out.println("前序遍历"); // 1,2,3,4
     28         binaryTree.preOrder();
     29 
     30         //测试
     31         System.out.println("中序遍历");
     32         binaryTree.infixOrder(); // 2,1,3,4
     33 
     34         System.out.println("后序遍历");
     35         binaryTree.postOrder(); // 2,4,3,1
     36 
     37     }
     38 
     39 }
     40 
     41 
     42 
     43 
     44 //定义BinaryTree 二叉树
     45 class BinaryTree {
     46     private HeroNode root;
     47 
     48     public void setRoot(HeroNode root) {
     49         this.root = root;
     50     }
     51     //前序遍历
     52     public void preOrder() {
     53         if(this.root != null) {
     54             this.root.preOrder();
     55         }else {
     56             System.out.println("二叉树为空,无法遍历");
     57         }
     58     }
     59 
     60     //中序遍历
     61     public void infixOrder() {
     62         if(this.root != null) {
     63             this.root.infixOrder();
     64         }else {
     65             System.out.println("二叉树为空,无法遍历");
     66         }
     67     }
     68     //后序遍历
     69     public void postOrder() {
     70         if(this.root != null) {
     71             this.root.postOrder();
     72         }else {
     73             System.out.println("二叉树为空,无法遍历");
     74         }
     75     }
     76 }
     77 
     78 
     79 //先创建HeroNode 结点
     80 class HeroNode {
     81     private int no;
     82     private String name;
     83     private HeroNode left; //默认null
     84     private HeroNode right; //默认null
     85     public HeroNode(int no, String name) {
     86         this.no = no;
     87         this.name = name;
     88     }
     89     public int getNo() {
     90         return no;
     91     }
     92     public void setNo(int no) {
     93         this.no = no;
     94     }
     95     public String getName() {
     96         return name;
     97     }
     98     public void setName(String name) {
     99         this.name = name;
    100     }
    101     public HeroNode getLeft() {
    102         return left;
    103     }
    104     public void setLeft(HeroNode left) {
    105         this.left = left;
    106     }
    107     public HeroNode getRight() {
    108         return right;
    109     }
    110     public void setRight(HeroNode right) {
    111         this.right = right;
    112     }
    113     @Override
    114     public String toString() {
    115         return "HeroNode [no=" + no + ", name=" + name + "]";
    116     }
    117 
    118     //编写前序遍历的方法
    119     public void preOrder() {
    120         System.out.println(this); //先输出父结点
    121         //递归向左子树前序遍历
    122         if(this.left != null) {
    123             this.left.preOrder();
    124         }
    125         //递归向右子树前序遍历
    126         if(this.right != null) {
    127             this.right.preOrder();
    128         }
    129     }
    130     //中序遍历
    131     public void infixOrder() {
    132 
    133         //递归向左子树中序遍历
    134         if(this.left != null) {
    135             this.left.infixOrder();
    136         }
    137         //输出父结点
    138         System.out.println(this);
    139         //递归向右子树中序遍历
    140         if(this.right != null) {
    141             this.right.infixOrder();
    142         }
    143     }
    144     //后序遍历
    145     public void postOrder() {
    146         if(this.left != null) {
    147             this.left.postOrder();
    148         }
    149         if(this.right != null) {
    150             this.right.postOrder();
    151         }
    152         System.out.println(this);
    153     }
    154 }
    代码
     1 前序遍历
     2 HeroNode [no=1, name=宋江]
     3 HeroNode [no=2, name=吴用]
     4 HeroNode [no=3, name=卢俊义]
     5 HeroNode [no=4, name=林冲]
     6 中序遍历
     7 HeroNode [no=2, name=吴用]
     8 HeroNode [no=1, name=宋江]
     9 HeroNode [no=3, name=卢俊义]
    10 HeroNode [no=4, name=林冲]
    11 后序遍历
    12 HeroNode [no=2, name=吴用]
    13 HeroNode [no=4, name=林冲]
    14 HeroNode [no=3, name=卢俊义]
    15 HeroNode [no=1, name=宋江]
    输出

    前上图的 3号节点 "卢俊" , 增加一个左子节点 [5, 关胜]

    使用前序,中序,后序遍历,请写出各自输出的顺序是什么?

     

     1 public static void main(String[] args) {
     2         //先需要创建一颗二叉树
     3         BinaryTree binaryTree = new BinaryTree();
     4         //创建需要的结点
     5         HeroNode root = new HeroNode(1, "宋江");
     6         HeroNode node2 = new HeroNode(2, "吴用");
     7         HeroNode node3 = new HeroNode(3, "卢俊义");
     8         HeroNode node4 = new HeroNode(4, "林冲");
     9         HeroNode node5 = new HeroNode(5, "关胜");
    10 
    11         //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
    12         root.setLeft(node2);
    13         root.setRight(node3);
    14         node3.setRight(node4);
    15         node3.setLeft(node5);
    16         binaryTree.setRoot(root);
    17 
    18         //测试
    19         System.out.println("前序遍历"); // 1,2,3,5,4
    20         binaryTree.preOrder();
    21 
    22         //测试
    23         System.out.println("中序遍历");
    24         binaryTree.infixOrder(); // 2,1,5,3,4
    25 
    26         System.out.println("后序遍历");
    27         binaryTree.postOrder(); // 2,5,4,3,1
    28 
    29     }
    代码
     1 前序遍历
     2 HeroNode [no=1, name=宋江]
     3 HeroNode [no=2, name=吴用]
     4 HeroNode [no=3, name=卢俊义]
     5 HeroNode [no=5, name=关胜]
     6 HeroNode [no=4, name=林冲]
     7 中序遍历
     8 HeroNode [no=2, name=吴用]
     9 HeroNode [no=1, name=宋江]
    10 HeroNode [no=5, name=关胜]
    11 HeroNode [no=3, name=卢俊义]
    12 HeroNode [no=4, name=林冲]
    13 后序遍历
    14 HeroNode [no=2, name=吴用]
    15 HeroNode [no=5, name=关胜]
    16 HeroNode [no=4, name=林冲]
    17 HeroNode [no=3, name=卢俊义]
    18 HeroNode [no=1, name=宋江]
    输出

     二叉树-查找指定节点

    1.编写前序查找,中序查找和后序查找的方法。

    2.并分别使用三种查找方式,查找 heroNO = 5 的节点

    3.并分析各种查找方式,分别比较了多少次

    思路分析

     

      1 /**
      2  * Created by wanbf on 2019/7/9.
      3  */
      4 public class BinaryTreeDemo {
      5 
      6     public static void main(String[] args) {
      7         //先需要创建一颗二叉树
      8         BinaryTree binaryTree = new BinaryTree();
      9         //创建需要的结点
     10         HeroNode root = new HeroNode(1, "宋江");
     11         HeroNode node2 = new HeroNode(2, "吴用");
     12         HeroNode node3 = new HeroNode(3, "卢俊义");
     13         HeroNode node4 = new HeroNode(4, "林冲");
     14         HeroNode node5 = new HeroNode(5, "关胜");
     15 
     16         //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
     17         root.setLeft(node2);
     18         root.setRight(node3);
     19         node3.setRight(node4);
     20         node3.setLeft(node5);
     21         binaryTree.setRoot(root);
     22 
     23         //前序遍历
     24         //前序遍历的次数 :4
     25         System.out.println("前序遍历方式~~~");
     26         HeroNode resNode = binaryTree.preOrderSearch(5);
     27         if (resNode != null) {
     28             System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
     29         } else {
     30             System.out.printf("没有找到 no = %d 的英雄", 5);
     31         }
     32 
     33         //中序遍历查找
     34         //中序遍历3次
     35         System.out.println("中序遍历方式~~~");
     36         HeroNode resNode = binaryTree.infixOrderSearch(5);
     37         if (resNode != null) {
     38             System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
     39         } else {
     40             System.out.printf("没有找到 no = %d 的英雄", 5);
     41         }
     42 
     43         //后序遍历查找
     44         //后序遍历查找的次数  2次
     45         System.out.println("后序遍历方式~~~");
     46         HeroNode resNode = binaryTree.postOrderSearch(5);
     47         if (resNode != null) {
     48             System.out.printf("找到了,信息为 no=%d name=%s", resNode.getNo(), resNode.getName());
     49         } else {
     50             System.out.printf("没有找到 no = %d 的英雄", 5);
     51         }
     52     }
     53 
     54 }
     55 
     56 //定义BinaryTree 二叉树
     57 class BinaryTree {
     58     private HeroNode root;
     59 
     60     public void setRoot(HeroNode root) {
     61         this.root = root;
     62     }
     63     //前序遍历查找
     64     public HeroNode preOrderSearch(int no) {
     65         if(root != null) {
     66             return root.preOrderSearch(no);
     67         } else {
     68             return null;
     69         }
     70     }
     71     //中序遍历查找
     72     public HeroNode infixOrderSearch(int no) {
     73         if(root != null) {
     74             return root.infixOrderSearch(no);
     75         }else {
     76             return null;
     77         }
     78     }
     79     //后序遍历查找
     80     public HeroNode postOrderSearch(int no) {
     81         if(root != null) {
     82             return this.root.postOrderSearch(no);
     83         }else {
     84             return null;
     85         }
     86     }
     87 }
     88 
     89 //先创建HeroNode 结点
     90 class HeroNode {
     91     private int no;
     92     private String name;
     93     private HeroNode left; //默认null
     94     private HeroNode right; //默认null
     95     public HeroNode(int no, String name) {
     96         this.no = no;
     97         this.name = name;
     98     }
     99     public int getNo() {
    100         return no;
    101     }
    102     public void setNo(int no) {
    103         this.no = no;
    104     }
    105     public String getName() {
    106         return name;
    107     }
    108     public void setName(String name) {
    109         this.name = name;
    110     }
    111     public HeroNode getLeft() {
    112         return left;
    113     }
    114     public void setLeft(HeroNode left) {
    115         this.left = left;
    116     }
    117     public HeroNode getRight() {
    118         return right;
    119     }
    120     public void setRight(HeroNode right) {
    121         this.right = right;
    122     }
    123     @Override
    124     public String toString() {
    125         return "HeroNode [no=" + no + ", name=" + name + "]";
    126     }
    127     //前序遍历查找
    128     /**
    129      *
    130      * @param no 查找no
    131      * @return 如果找到就返回该Node ,如果没有找到返回 null
    132      */
    133     public HeroNode preOrderSearch(int no) {
    134         System.out.println("进入前序遍历");
    135         //比较当前结点是不是
    136         if(this.no == no) {
    137             return this;
    138         }
    139         //1.则判断当前结点的左子节点是否为空,如果不为空,则递归前序查找
    140         //2.如果左递归前序查找,找到结点,则返回
    141         HeroNode resNode = null;
    142         if(this.left != null) {
    143             resNode = this.left.preOrderSearch(no);
    144         }
    145         if(resNode != null) {//说明我们左子树找到
    146             return resNode;
    147         }
    148         //1.左递归前序查找,找到结点,则返回,否继续判断,
    149         //2.当前的结点的右子节点是否为空,如果不空,则继续向右递归前序查找
    150         if(this.right != null) {
    151             resNode = this.right.preOrderSearch(no);
    152         }
    153         return resNode;
    154     }
    155 
    156     //中序遍历查找
    157     public HeroNode infixOrderSearch(int no) {
    158         //判断当前结点的左子节点是否为空,如果不为空,则递归中序查找
    159         HeroNode resNode = null;
    160         if(this.left != null) {
    161             resNode = this.left.infixOrderSearch(no);
    162         }
    163         if(resNode != null) {
    164             return resNode;
    165         }
    166         System.out.println("进入中序查找");
    167         //如果找到,则返回,如果没有找到,就和当前结点比较,如果是则返回当前结点
    168         if(this.no == no) {
    169             return this;
    170         }
    171         //否则继续进行右递归的中序查找
    172         if(this.right != null) {
    173             resNode = this.right.infixOrderSearch(no);
    174         }
    175         return resNode;
    176 
    177     }
    178 
    179     //后序遍历查找
    180     public HeroNode postOrderSearch(int no) {
    181 
    182         //判断当前结点的左子节点是否为空,如果不为空,则递归后序查找
    183         HeroNode resNode = null;
    184         if(this.left != null) {
    185             resNode = this.left.postOrderSearch(no);
    186         }
    187         if(resNode != null) {//说明在左子树找到
    188             return resNode;
    189         }
    190 
    191         //如果左子树没有找到,则向右子树递归进行后序遍历查找
    192         if(this.right != null) {
    193             resNode = this.right.postOrderSearch(no);
    194         }
    195         if(resNode != null) {
    196             return resNode;
    197         }
    198         System.out.println("进入后序查找");
    199         //如果左右子树都没有找到,就比较当前结点是不是
    200         if(this.no == no) {
    201             return this;
    202         }
    203         return resNode;
    204     }
    205 
    206 }
    代码
     1 前序遍历方式~~~
     2 进入前序遍历
     3 进入前序遍历
     4 进入前序遍历
     5 进入前序遍历
     6 找到了,信息为 no=5 name=关胜中序遍历方式~~~
     7 进入中序查找
     8 进入中序查找
     9 进入中序查找
    10 找到了,信息为 no=5 name=关胜后序遍历方式~~~
    11 进入后序查找
    12 进入后序查找
    13 找到了,信息为 no=5 name=关胜
    输出

     二叉树-删除节点

    定义:

    1. 如果删除的节点是叶子节点,则删除该节点
    2. 如果删除的节点是非叶子节点,则删除该子树.

    思路分析:

    实现删除代码:

     1 //定义BinaryTree 二叉树
     2 class BinaryTree {
     3     private HeroNode root;
     4 
     5     public void setRoot(HeroNode root) {
     6         this.root = root;
     7     }
     8     
     9     //删除结点
    10     public void delNode(int no) {
    11         if(root != null) {
    12             //如果只有一个root结点, 这里立即判断root是不是就是要删除结点
    13             if(root.getNo() == no) {
    14                 root = null;
    15             } else {
    16                 //递归删除
    17                 root.delNode(no);
    18             }
    19         }else{
    20             System.out.println("空树,不能删除~");
    21         }
    22     }
    23 }
    24 class HeroNode {
    25         private int no;
    26     private String name;
    27     private HeroNode left; //默认null
    28     private HeroNode right; //默认null
    29     public HeroNode(int no, String name) {
    30         this.no = no;
    31         this.name = name;
    32     }
    33     public int getNo() {
    34         return no;
    35     }
    36     public void setNo(int no) {
    37         this.no = no;
    38     }
    39     public String getName() {
    40         return name;
    41     }
    42     public void setName(String name) {
    43         this.name = name;
    44     }
    45     public HeroNode getLeft() {
    46         return left;
    47     }
    48     public void setLeft(HeroNode left) {
    49         this.left = left;
    50     }
    51     public HeroNode getRight() {
    52         return right;
    53     }
    54     public void setRight(HeroNode right) {
    55         this.right = right;
    56     }
    57     @Override
    58     public String toString() {
    59         return "HeroNode [no=" + no + ", name=" + name + "]";
    60     }
    61         //递归删除结点
    62     //1.如果删除的节点是叶子节点,则删除该节点
    63     //2.如果删除的节点是非叶子节点,则删除该子树
    64     public void delNode(int no) {
    65         
    66         //思路
    67         /*
    68          *     1. 因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.
    69             2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
    70             3. 如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
    71             4. 如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除
    72             5.  如果第4步也没有删除结点,则应当向右子树进行递归删除.
    73 
    74          */
    75         //2. 如果当前结点的左子结点不为空,并且左子结点 就是要删除结点,就将this.left = null; 并且就返回(结束递归删除)
    76         if(this.left != null && this.left.no == no) {
    77             this.left = null;
    78             return;
    79         }
    80         //3.如果当前结点的右子结点不为空,并且右子结点 就是要删除结点,就将this.right= null ;并且就返回(结束递归删除)
    81         if(this.right != null && this.right.no == no) {
    82             this.right = null;
    83             return;
    84         }
    85         //4.我们就需要向左子树进行递归删除
    86         if(this.left != null) {
    87             this.left.delNode(no);
    88         }
    89         //5.则应当向右子树进行递归删除
    90         if(this.right != null) {
    91             this.right.delNode(no);
    92         }
    93     }
    94 }    
    代码

    测试:

     1 public static void main(String[] args) {
     2         //先需要创建一颗二叉树
     3         BinaryTree binaryTree = new BinaryTree();
     4         //创建需要的结点
     5         HeroNode root = new HeroNode(1, "宋江");
     6         HeroNode node2 = new HeroNode(2, "吴用");
     7         HeroNode node3 = new HeroNode(3, "卢俊义");
     8         HeroNode node4 = new HeroNode(4, "林冲");
     9         HeroNode node5 = new HeroNode(5, "关胜");
    10 
    11         //说明,我们先手动创建该二叉树,后面我们学习递归的方式创建二叉树
    12         root.setLeft(node2);
    13         root.setRight(node3);
    14         node3.setRight(node4);
    15         node3.setLeft(node5);
    16         binaryTree.setRoot(root);
    17         System.out.println("删除前,前序遍历");
    18         binaryTree.preOrder(); //  1,2,3,5,4
    19         binaryTree.delNode(5);
    20         //binaryTree.delNode(3);
    21         System.out.println("删除后,前序遍历");
    22         binaryTree.preOrder(); // 1,2,3,4    
    23 }
    24 输出:
    25 删除前,前序遍历
    26 HeroNode [no=1, name=宋江]
    27 HeroNode [no=2, name=吴用]
    28 HeroNode [no=3, name=卢俊义]
    29 HeroNode [no=5, name=关胜]
    30 HeroNode [no=4, name=林冲]
    31 删除后,前序遍历
    32 HeroNode [no=1, name=宋江]
    33 HeroNode [no=2, name=吴用]
    34 HeroNode [no=3, name=卢俊义]
    35 HeroNode [no=4, name=林冲]
    36 如果是删除binaryTree.delNode(3);
    37 则输出:
    38 删除前,前序遍历
    39 HeroNode [no=1, name=宋江]
    40 HeroNode [no=2, name=吴用]
    41 HeroNode [no=3, name=卢俊义]
    42 HeroNode [no=5, name=关胜]
    43 HeroNode [no=4, name=林冲]
    44 删除后,前序遍历
    45 HeroNode [no=1, name=宋江]
    46 HeroNode [no=2, name=吴用]
    代码

     拓展:

    上面我们定义了两个删除规则,那么我们考虑另外删除规则又怎么实现。‘

    如果要删除的节点是非叶子节点,现在我们不希望将该非叶子节点为根节点的子树删除,需要指定规则, 假如规定如下:

    1. 如果该非叶子节点A只有一个子节点B,则子节点B替代节点A
    2. 如果该非叶子节点A有左子节点B和右子节点C,则让左子节点B替代节点A。

     这个代码实现在后续讲二叉排序树时,在讲解具体的删除方法。

    顺序存储二叉树

    顺序存储二叉树的概念

    基本说明

    从数据存储来看,数组存储方式和树 的存储方式可以相互转换,即数组可 以转换成树,树也可以转换成数组, 看示意图。

    要求:

    1. 上图的二叉树的结点,要求以数组 的方式来存放 arr : [1, 2, 3, 4, 5, 6, 7]
    2. 要求在遍历数组 arr时,仍然可以以 前序遍历,中序遍历和后序遍历的 方式完成结点的遍历

    顺序存储二叉树的特点:

    1. 顺序二叉树通常只考虑完全二叉树
    2. 第n个元素的左子节点为  2 * n + 1
    3. 第n个元素的右子节点为  2 * n + 2
    4. 第n个元素的父节点为  (n-1) / 2
    5.  n : 表示二叉树中的第几个元素

    需求: 给你一个数组 {1,2,3,4,5,6,7},要求以二叉树前序遍历的方式进行遍历。 前序遍历的结果应当为 1,2,4,5,3,6,7

     1 public class ArrBinaryTreeDemo {
     2 
     3     public static void main(String[] args) {
     4         int[] arr = { 1, 2, 3, 4, 5, 6, 7 };
     5         //创建一个 ArrBinaryTree
     6         ArrBinaryTree arrBinaryTree = new ArrBinaryTree(arr);
     7         arrBinaryTree.preOrder(); // 1,2,4,5,3,6,7
     8     }
     9 
    10 }
    11 
    12 //编写一个ArrayBinaryTree, 实现顺序存储二叉树遍历
    13 
    14 class ArrBinaryTree {
    15     private int[] arr;//存储数据结点的数组
    16 
    17     public ArrBinaryTree(int[] arr) {
    18         this.arr = arr;
    19     }
    20 
    21     //重载preOrder
    22     public void preOrder() {
    23         this.preOrder(0);
    24     }
    25 
    26     //编写一个方法,完成顺序存储二叉树的前序遍历
    27     /**
    28      *
    29      * @param index 数组的下标
    30      */
    31     public void preOrder(int index) {
    32         //如果数组为空,或者 arr.length = 0
    33         if(arr == null || arr.length == 0) {
    34             System.out.println("数组为空,不能按照二叉树的前序遍历");
    35         }
    36         //输出当前这个元素
    37         System.out.println(arr[index]);
    38         //向左递归遍历
    39         if((index * 2 + 1) < arr.length) {
    40             preOrder(2 * index + 1 );
    41         }
    42         //向右递归遍历
    43         if((index * 2 + 2) < arr.length) {
    44             preOrder(2 * index + 2);
    45         }
    46     }
    47 
    48 }
    代码

    顺序存储二叉树应用实例

    八大排序算法中的堆排序,就会使用到顺序存储二叉树, 关于堆排序后续在讲。

     

    posted on 2019-07-10 23:37 wanbf 阅读(...) 评论(...) 编辑 收藏

  • “两学一做”在山西——黄河新闻网 2019-07-13
  • 内地生报读香港高校本科人数持续下跌 2019-07-13
  • 【学习时刻】人民大学王义桅:金砖合作的“自信”与“自觉” 2019-07-12
  • 女子请“私家侦探”被骗3万 警方循线捣毁诈骗团伙 2019-07-11
  • 【学习时刻】北交大马院院长韩振峰:高校思想政治工作必须牢牢把握三大根本问题 2019-07-11
  • 全国“非遗”保护工作先进名单公布 2019-07-01
  • 紫光阁中共中央国家机关工作委员会 2019-06-25
  • 杭州控烟令修改草案拟允许室内设吸烟区,控烟专家:跌破眼镜 2019-06-25
  • 挪用近30万报纸征订款赌博 河南一报社聘用制干部获刑 2019-06-23
  • 2016年,有1145家上市公司大小非减持了3600亿元,还有210名上市公司高管减持了1400亿元。IPO已成了造就成千上万个十亿、百亿富豪的捷径, 2019-06-21
  • 专家“把脉”中国电影市场:提升品质方能逆袭 2019-06-21
  • “善款资助副局长儿子留学”真相须尽快落地 2019-06-19
  • 21岁女护士失联2天后确认遇害 嫌疑人为其前男友 2019-06-19
  • 中国地质公园名录旅行地中国国家地理网 2019-06-13
  • 玄关运用有四大原则 用的好才能财旺挡煞聚财 ——凤凰网房产 2019-06-10
  • 体彩七星彩 七乐彩走势图200期 qq三张牌看牌精灵破解版 三肖中特期期准铁算盘 3d二胆六拖复式 中国足彩网彩票比分 3d杀号定胆 幸运农场小游戏 qq欢乐升级同花怎么打 广东十一选五开奖直播 亚盘足彩什么app可以买 王炸扑克 黑龙江36选7开奖电视 福彩36选7开奖结果 精准平特肖高手网