数据结构——二叉树学习

一:树

我们思维中的”树“就是一种枝繁叶茂的形象,那么数据结构中的”树“该是怎么样呢?对的,他是一种现实中倒立的树。

这里写图片描述
1:术语

 其实树中有很多术语的,这个是我们学习树形结构必须掌握的。

 <1>  父节点,子节点,兄弟节点

              这个就比较简单了,B和C的父节点就是A,反过来说就是B和C是A的子节点。B和C就是兄弟节点。

 <2>  结点的度

             其实”度“就是”分支数“,比如A的分支数有两个“B和C",那么A的度为2。

 <3> 树的度

            看似比较莫名其妙吧,他和”结点的度“的区别就是,树的度讲究大局观,乃树中最大的结点度,其实也就是2。

 <4> 叶结点,分支结点

            叶结点就是既没有左孩子也没有右孩子结点,也就是结点度为0。分支节点也就是if的else的条件咯。

<5> 结点的层数

           这个很简单,也就是树有几层。

<6> 有序树,无序树

           有序树我们先前也用过,比如“堆”和“二叉排序树”,说明这种树是按照一定的规则进行排序的,else条件就是无序树。

<7> 森林

           现实中,很多的树形成了森林,那在数据结构中,我们把上图的“A”节点砍掉,那么B,C子树合一起就是森林咯。

2: 树的表示

 树这个结构的表示其实有很多种,常用的也就是“括号”表示法。

 比如上面的树就可以表示为:(A(B(D),(E)),(C(F),(G)))

二: 二叉树

     在我们项目开发中,很多地方都会用到树,但是多叉树的处理还是比较纠结的,所以俺们本着“大事化小,小事化了“的原则

  把”多叉树“转化为”二叉树“,那么问题就简化了很多。

1: ”二叉树“和”树“有什么差异呢?

     第一点:  树的度没有限制,而“二叉树”最多只能有两个,不然也就不叫二叉树了,哈哈。

     第二点:树中的子树没有左右划分,很简单啊,找不到参照点,二叉树就有参照物咯。

2: 二叉树的类型

   二叉树中有两种比较完美的类型,“完全二叉树”和“满二叉树”。

      <1>  满二叉树    

                   除叶子节点外,所有节点的度都为2,文章开头处的树就是这里的“满二叉树”。

      <2>  完全二叉树

                  必须要满足两个条件就即可:  干掉最后一层,二叉树变为“满二叉树”。

                                                          最后一层的叶节点必须是“从左到右”依次排开。

                 我们干掉文章开头处的节点“F和”G",此时还是“完全二叉树”,但已经不是“满二叉树”了,你懂的。

3: 二叉树的性质

     二叉树中有5点性质非常重要,也是俺们必须要记住的。

 <1>  二叉树中,第i层的节点最多有2(i-1)个。

 <2>  深度为k的二叉树最多有2k-1个节点。

 <3>  二叉树中,叶子节点树为N1个,度为2的节点有N2个,那么N1=N2+1。

 <4>  具有N个结点的二叉树深度为(Log2 N)+1层。

 <5>  N个结点的完全二叉树如何用顺序存储,对于其中的一个结点i,存在以下关系,

          2*i是结点i的父结点。

          i/2是结点i的左孩子。

          (i/2)+1是结点i的右孩子。

4: 二叉树的顺序存储

  同样的存储方式也有两种,“顺序存储”和“链式存储”。

   <1> 顺序存储

             说实话,树的存储用顺序结构比较少,因为从性质定理中我们都可以看出只限定为“完全二叉树”,那么如果二叉树不是

          “完全二叉树”,那我们就麻烦了,必须将其转化为“完全二叉树”,将空的节点可以用“#”代替,图中也可看出,为了维护

          性质定理5的要求,我们牺牲了两个”资源“的空间。

这里写图片描述
<2> 链式存储

           上面也说了,顺序存储会造成资源的浪费,所以嘛,我们开发中用的比较多的还是“链式存储”,同样“链式存储”

        也非常的形象,非常的合理。

           一个结点存放着一个“左指针”和一个“右指针”,这就是二叉链表。

           如何方便的查找到该结点的父结点,可以采用三叉链表。
package com.tree;

public class BinaryTree {
    private int data;//数据节点
    private BinaryTree left;
    private BinaryTree right;

    public BinaryTree(int data){
        this.data = data;
        this.left = null;
        this.right = null;
    }
    /*
     * 创建二叉树,返回根节点
     * @param input
     * @return
     */
    public static BinaryTree createTree(int[] input){
        BinaryTree root = null;
        BinaryTree temp = null;
        for(int i = 0; i < input.length;i++){
            //创建根节点
            if(root == null){
                root = temp = new BinaryTree(input[i]);
            }else{
                temp = root;
                //添加节点
                while(temp.data != input[i]){
                    if(input[i] <= temp.data){
                        if(temp.left != null){
                            temp = temp.left;
                        }else{
                            temp.left = new BinaryTree(input[i]);
                        }
                    }else{
                        if(temp.right != null){
                            temp = temp.right;
                        }else{
                            temp.right = new BinaryTree(input[i]);
                        }
                    }
                }
            }

        }
        return root;    
    }
    /*
     * 前序遍历
     * @param tree
     */
    public static void preOrder(BinaryTree tree){
        if(tree != null){
            System.out.println(tree.data);
            preOrder(tree.left);
            preOrder(tree.right);
        }
    }
    /*
     * 中序遍历
     * @param tree
     */
    public static void midOrder(BinaryTree tree){
        if(tree != null){
            midOrder(tree.left);
            System.out.println(tree.data);
            midOrder(tree.right);
        }
    }
    /*
     * 后序遍历
     * @param tree
     */
    public static void posOrder(BinaryTree tree){
        if(tree != null){
            posOrder(tree.left);
            posOrder(tree.right);
            System.out.println(tree.data);
        }
    }
    /*
     * 求二叉树的深度
     * 
     * @param tree
     */
    public static int length(BinaryTree tree){
        int leftLen;
        int rightLen;
        if(tree == null){
            return 0;
        }else{
            leftLen = length(tree.left);
            rightLen = length(tree.right);
            if(leftLen > rightLen){
                return leftLen+1;
            }else{
                return rightLen+1;
            }
        }

    }
    /*
     * 测试main函数
     * 
     * @param args
     */
    public static void main(String[] args){
        int[] input = {4,2,6,1,3,5,7,8,10};
        BinaryTree btree = createTree(input);
        System.out.println("前序遍历:");
        preOrder(btree);
        System.out.println("中序遍历:");
        midOrder(btree);
        System.out.println("后序遍历:");
        posOrder(btree);
        System.out.println("树的深度:"+length(btree));

    }
}
import java.util.LinkedList;

public class LevelOrder
{
  public void levelIterator(BiTree root)
  {
      if(root == null)
      {
          return ;
      }
      LinkedList<BiTree> queue = new LinkedList<BiTree>();
      BiTree current = null;
      queue.offer(root);//将根节点入队
      while(!queue.isEmpty())
      {
          current = queue.poll();//出队队头元素并访问
          System.out.print(current.val +"-->");
          if(current.left != null)//如果当前节点的左节点不为空入队
          {
              queue.offer(current.left);
          }
          if(current.right != null)//如果当前节点的右节点不为空,把右节点入队
          {
              queue.offer(current.right);
          }
      }

  }

}
版权声明:本文为u012961566原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/u012961566/article/details/72627339

智能推荐

ActiveMQ学习4-ActiveMQ的安全机制和集群模式

ActiveMQ的安全机制和集群模式 20 ActiveMQ安全机制 20.1 Web 控制台安全 20.2 消息服务器Broker安全 21 ActiveMQ主从集群 21.1 使用集群的重要性 20.2 主从集群的方式 20.2.1 shared filesystem Master-Slave方式主从集群 20.2.2 shared database Master-Slave方式主从集群 20...

说说 Python Django 应用的基础目录结构

通过以下 django-admin 指令创建应用之后,就会生成应用的基础目录结构。 比如,我们建立了一个叫 ‘first’ 的应用,它的目录结构是这样的: 目录或文件 说明 最外层的 first/ 这是新应用的根目录,所有与该应用相关的内容都放在这里。 manage.py 用于管理 Django 项目的命令行工具。 里面一层的 first/ 目录 是一个...

Springboot整合rabbitMQ

依赖: 配置文件application.yml RabbitConfig 消息生产者RabbitProducer 消息消费者RabbitCustomer 通过Controller进行调用 启动项目后调用接口: 结果:...

Thread.join()方法的使用

如果一个线程A执行了thread.join()语句,代表当前线程A等待thread线程终止后才从thread.join()方法返回 并且这个方法具有超时特性,可以添加参数设置 输出结果: jdk中Thread.join()方法的源码(进行了部门调整)   每个线程终止的条件是前驱线程的终止,每个线程等待前驱线程终止后,才从join()方法返回,  当线程终止时,会调用自身的no...

linux服务器部署jenkins笔记

安装jenkins参考文档:https://blog.csdn.net/tomatocc/article/details/83930714 1. 打开jenkins官网:https://jenkins.io/download/ 将war包下载到本地 **ps:**这里要注意的是要下载左边下方的war包,不要下载右边下面的war包。左边是稳定版本,右边是最新版本,建议大家使用稳定版本(我刚开始下载的...

猜你喜欢

k8s部署elasticsearch集群

百度营销大学     环境准备 我们使用的k8s和ceph环境见: https://blog.51cto.com/leejia/2495558 https://blog.51cto.com/leejia/2499684 ECK简介 Elastic Cloud on Kubernetes,这是一款基于 Kubernetes Operator 模式的新型编排产品,用户可使用该产品在...

saas-export项目-AdminLTE介绍与入门

AdminLTE介绍 (1)AdminLTE是什么? AdminLTE是一款建立在bootstrap和jquery之上的开源的模板主题工具 (2)AdminLTE有什么特点? 提供一系列响应的、可重复使用的组件, 并内置了多个模板页面 自适应多种屏幕分辨率,兼容PC和移动端 快速的创建一个响应式的Html5网站 AdminLTE 不但美观, 而且可以免去写很大CSS与JS的工作量 AdminLTE...

MyBatis中ResultMap结果集映射

用于解决属性名和字段名不一致的情况: resultMap 元素是 MyBatis 中最重要最强大的元素。...

编写一个shell

编写shell的过程: 1.从标准输入中读入一个字符串。 2.解析字符串 3.创建一个子进程的执行程序。 4.子进程程序替换。 5.父进程等待子进程退出。...

WEB自动化测试中Xpath定位方法

前言: Xpath是在XML文档中查找信息的一种语言,使用路径表达式来选取XML文档中的节点或节点集,由于XML与HTML结构类似(前者用于传输数据,后者用于显示数据),所以Xpath也常用于查找HTML文档中的节点或节点集。 一  路径表达式: 路径以“/”开始     表示找到满足该绝对路径的元素; 路径以//”开始  ...