> 文档中心 > 二叉树 详细讲解

二叉树 详细讲解


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

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

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

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

2、树示意图

二叉树 详细讲解

树的常用术语(结合示意图理解):

  1. 节点
  2. 根节点
  3. 父节点
  4. 子节点
  5. 叶子节点 (没有子节点的节点)
  6. 节点的权(节点值)
  7. 路径(从root节点找到该节点的路线)
  8. 子树
  9. 树的高度(最大层数)
  10. 森林 :多颗子树构成森林

3、二叉树的概念

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

4、二叉树遍历的说明

使用前序,中序和后序对下面的二叉树进行遍历.
二叉树 详细讲解

前序遍历: 先输出父节点,再遍历左子树和右子树
中序遍历: 先遍历左子树, 再输出父节点,再遍历右子树
后序遍历: 先遍历左子树,再遍历右子树,最后输出父节点
小结: 看输出父节点的顺序,就确定是前序,中序还是后序

4.1、前序遍历

  public void preOrder(){ System.out.println(this); //向左子树递归 if (this.left!=null){     this.left.preOrder(); } //向左子树递归 if (this.right!=null){     this.right.preOrder(); }    }

4.2、中序遍历

 public void midOrder(){ if (this.left!=null){     this.left.midOrder(); } System.out.println(this); if (this.right!=null){     this.right.midOrder(); }    }

4.3、后序遍历

 public void postOrder(){ if (this.left!=null){     this.left.postOrder(); } if (this.right!=null){     this.right.postOrder(); } System.out.println(this);    }

5、二叉树-查找指定节点

二叉树 详细讲解

要求
请编写前序查找,中序查找和后序查找的方法。
并分别使用三种查找方式,查找 heroNO = 5 的节点
并分析各种查找方式,分别比较了多少次

5.1、前序查找

 /**     * 前序查找(id)     */    public Hero preOrderSearch(int id){ System.out.println("前序查找~~~"); if (this.id==id){     return this; } //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.preOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.preOrderSearch(id);     if (hero!=null){     if (hero.id==id){  result=hero;     }     } } return result;    }

5.2、中序查找

  /**     * 中序查找(id)     */    public Hero midOrderSearch(int id){ //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.midOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } System.out.println("中序查找~~~"); if (this.id==id){     return this; } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.midOrderSearch(id);     if (hero!=null){  if (hero.id==id){      result=hero;  }     } } return result;    }

5.3、后序查找

  /**     * 后序查找(id)     */    public Hero postOrderSearch(int id){ //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.postOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.postOrderSearch(id);     if (hero!=null){  if (hero.id==id){      result=hero;  }     } } if (this.id==id){     return this; } System.out.println("后序查找~~~"); return result;    }

6、二叉树-删除节点

二叉树 详细讲解
要求
如果删除的节点是叶子节点,则删除该节点
如果删除的节点是非叶子节点,则删除该子树.
测试,删除掉 5号叶子节点 和 3号子树.

6.1、删除节点思路分析

二叉树 详细讲解

 * 1.如果删除的节点是叶子节点,则删除该节点 * 2.如果删除的节点是非叶子节点,则删除该子树 *1.因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点. *2.如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left=null,并且就返回 * (结束递归删除) * 3.如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right=null;并且就返回 * (结束递归删除) * 4.如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除 * 5.如果第4步也没有删除结点,则应当向右子树进行递归删除 *
 public void deleteNo(int id){ if (this.left!=null&&this.left.id==id){     this.left=null; } if (this.right!=null&&this.right.id==id){     this.right=null; } if (this.left!=null){     this.left.deleteNo(id); } if (this.right!=null){     this.right.deleteNo(id); }    }

7、代码实现

package com.qf;public class BinaryTreeDemo {    public static void main(String[] args) { Hero hero1=new Hero(1,"宋江"); Hero hero2=new Hero(2,"吴用"); Hero hero3=new Hero(3,"卢俊义"); Hero hero4=new Hero(4,"林冲"); Hero hero5=new Hero(5,"豹子头"); Hero hero6=new Hero(6,"武松"); hero1.setLeft(hero2); hero2.setRight(hero5); hero1.setRight(hero3); hero3.setRight(hero4); hero3.setLeft(hero6); BinaryTree binaryTree=new BinaryTree(); binaryTree.setRoot(hero1); binaryTree.delete(6); binaryTree.postOrder();      /*  Hero hero = binaryTree.postOrderSearch(4); if (hero==null){     System.out.println("未找到该英雄"); }else{     System.out.println("找到了该英雄");     System.out.println(hero); }*/    }}class BinaryTree{    private Hero root;    public Hero getRoot() { return root;    }    public void setRoot(Hero root) { this.root = root;    }    public void preOrder(){ if (this.root!=null){     root.preOrder(); }else {     System.out.println("树为空"); }    }    public void midOrder(){ if (this.root!=null){     root.midOrder(); }else {     System.out.println("树为空"); }    }    public void postOrder(){ if (this.root!=null){     root.postOrder(); }else {     System.out.println("树为空"); }    }    public Hero preOrderSearch(int id){ if (this.root!=null){     Hero hero = root.preOrderSearch(id);     return hero; }else {     return null; }    }    public Hero midOrderSearch(int id){ if (this.root!=null){     Hero hero = root.midOrderSearch(id);     return hero; }else {     return null; }    }    public Hero postOrderSearch(int id){ if (this.root!=null){     Hero hero = root.postOrderSearch(id);     return hero; }else {     return null; }    }    public void delete(int id){ if (root!=null){     if (root.getId()==id){  root=null;     }else{  root.deleteNo(id);     } }else{     System.out.println("空树无法删除~"); }    }}class Hero{    private int id;    private String name;    private Hero left;    private Hero right;    public Hero(int id, String name) { this.id = id; this.name = name;    }    public int getId() { return id;    }    public void setId(int id) { this.id = id;    }    public String getName() { return name;    }    public void setName(String name) { this.name = name;    }    public Hero getLeft() { return left;    }    public void setLeft(Hero left) { this.left = left;    }    public Hero getRight() { return right;    }    public void setRight(Hero right) { this.right = right;    }    @Override    public String toString() { return "Hero{" +  "id=" + id +  ", name='" + name + '\'' +  '}';    }    public void preOrder(){ System.out.println(this); //向左子树递归 if (this.left!=null){     this.left.preOrder(); } //向左子树递归 if (this.right!=null){     this.right.preOrder(); }    }    public void midOrder(){ if (this.left!=null){     this.left.midOrder(); } System.out.println(this); if (this.right!=null){     this.right.midOrder(); }    }    public void postOrder(){ if (this.left!=null){     this.left.postOrder(); } if (this.right!=null){     this.right.postOrder(); } System.out.println(this);    }    /**     * 前序查找(id)     */    public Hero preOrderSearch(int id){ System.out.println("前序查找~~~"); if (this.id==id){     return this; } //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.preOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.preOrderSearch(id);     if (hero!=null){     if (hero.id==id){  result=hero;     }     } } return result;    }    /**     * 中序查找(id)     */    public Hero midOrderSearch(int id){ //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.midOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } System.out.println("中序查找~~~"); if (this.id==id){     return this; } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.midOrderSearch(id);     if (hero!=null){  if (hero.id==id){      result=hero;  }     } } return result;    }    /**     * 后序查找(id)     */    public Hero postOrderSearch(int id){ //向左子节点遍历 Hero result=null; if (this.left!=null){     Hero hero = this.left.postOrderSearch(id);     if (hero!=null){  if (hero.id==id){      return hero;  }     } } //向右子节点遍历 if (this.right!=null){     Hero hero = this.right.postOrderSearch(id);     if (hero!=null){  if (hero.id==id){      result=hero;  }     } } if (this.id==id){     return this; } System.out.println("后序查找~~~"); return result;    }    /**     * 1.如果删除的节点是叶子节点,则删除该节点     * 2.如果删除的节点是非叶子节点,则删除该子树     *1.因为我们的二叉树是单向的,所以我们是判断当前结点的子结点是否需要删除结点,而不能去判断当前这个结点是不是需要删除结点.     *2.如果当前结点的左子结点不为空,并且左子结点就是要删除结点,就将this.left=null,并且就返回     * (结束递归删除)     * 3.如果当前结点的右子结点不为空,并且右子结点就是要删除结点,就将this.right=null;并且就返回     * (结束递归删除)     * 4.如果第2和第3步没有删除结点,那么我们就需要向左子树进行递归删除     * 5.如果第4步也没有删除结点,则应当向右子树进行递归删除     */    public void deleteNo(int id){ if (this.left!=null&&this.left.id==id){     this.left=null; } if (this.right!=null&&this.right.id==id){     this.right=null; } if (this.left!=null){     this.left.deleteNo(id); } if (this.right!=null){     this.right.deleteNo(id); }    }}

KTV音响网