本文共 2880 字，大约阅读时间需要 9 分钟。

二叉树

二叉树的概念

1. 定义：每个节点最多只能有两个子节点的一种形式称之为二叉树
2. 二叉树的节点分为左节点和右节点
   图示：
   
3. 满二叉树：二叉树的所有叶子节点（无分叉的节点）都在最后一层，并且总结点数为2ⁿ- 1,n为层数
   图示：
   
4. 完全二叉树：所有的叶子节点都在最后一层或者是倒数第二层，并且最后一层左边连续，倒数第二层右边连续。连续就是都是这一层的。
   图示：
   

二叉树的遍历方式

基本概念

1. 前序遍历：先输出父节点，在遍历左子树和右子树
2. 中序遍历：先遍历左子树，在输出父节点，在遍历右子树
3. 后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
   ** 父节点的输出先后决定其实遍历的顺序**

思路分析

1. 创建一个二叉树
2. 遍历：

• 前序遍历：
  • 输出当前节点
  • 判断：如果左子节点不为空，那就继续前序遍历
  • 判断：如果右子节点不为空，那就继续前序遍历
• 中序遍历：
  • 如果当前节点的左子节点不为空，则递归中序遍历
  • 输出当前节点
  • 如果当前节点右子节点不为空，那就递归中序遍历
• 后序遍历:
  • 如果当前节点的左子节点不为空，那就递归左子节点
  • 如果当前节点的右子节点不为空，那就递归右子节点
  • 输出当前节点

代码实现：

class BinaryTree{
       //二叉树有必须有根节点    private HeroNode root;    public BinaryTree(HeroNode root) {
           this.root = root;    }    public BinaryTree() {
       }    //判定当前节点是否为空    public boolean isEmpty(){
           if (root == null){
               return false;        }else{
               return true;        }    }    //根节点为二叉树必需的元素，所以必须有根节点才能够创建    //和hashTab类似，头应该有总览调用各个方法，而不是由各个节点调用    public void preOrder(){
           if (isEmpty()){
               System.out.println("当前树为空，无法遍历");        }else{
               root.preOrder();        }    }    public void minOrder(){
           if (isEmpty()){
               System.out.println("当前树为空，无法遍历");        }else{
               root.midOrder();        }    }    public void postOrder(){
           if (isEmpty()){
               System.out.println("当前树为空，无法遍历");        }else{
               root.postOrder();        }    }}class HeroNode{
       private int heroNo;    private String heroName;    HeroNode left;    HeroNode right;    public HeroNode(int heroNo, String heroName) {
           this.heroNo = heroNo;        this.heroName = heroName;    }    public HeroNode getLeft() {
           return left;    }    public HeroNode getRight() {
           return right;    }    public void setLeft(HeroNode left) {
           this.left = left;    }    public void setRight(HeroNode right) {
           this.right = right;    }    @Override    public String toString() {
           return "HeroNode{" +                "heroNo=" + heroNo +                ", heroName='" + heroName + '\'' +                '}';    }    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);    }

分析与总结

1. 创建节点，必须有权值，同时还有指向左右两个子节点的索引，同时还有对应的增删改除的方法，但是真正调用方法的还是树结构
2. 创建一个树的类必须创建根节点，同时还有对于节点的操作方法，能够操作树的的各个节点
3. 对于遍历的方法而言，必须先判定是否为空，否则会出现空指针

转载地址：http://jqgpb.baihongyu.com/