二叉树----顺序二叉树、线索二叉树

1、顺序二叉树

1.1、 顺序二叉树的特点

特点

• 顺序二叉树通常只考虑完全二叉树

• 第 n个元素的左子节点为 2 × n + 1

• 第 n个元素的右子节点为 2 × n + 2

• 第 n个元素的父节点为(n-1) ÷2

  其中n 表示二叉树中的第几个元素(从0开始编号)

2.2、 顺序二叉树代码实现

注意点：和遍历二叉树类似、不同的地方，是递归的条件变成了2n + 1等，还要注意判断，防止在2n+1的时候，数组越界，所以要加上判断语句

class ArrBinaryTree {
   int[] arr;
   final int step = 2;
​
   public ArrBinaryTree(int[] arr) {
      this.arr = arr;
   }
​
   /**
    * 数组的前序遍历
    */
   public void preTraverse() {
      preTraverse(0);
   }
​
   /**
    * 数组的前序遍历
    * @param index 遍历到的数组元素下标
    */
   private void preTraverse(int index) {
      if(arr == null || arr.length == 0) {
         System.out.println("数组为空！");
         return;
      }
      System.out.print(arr[index] + " ");
      //向左递归
      if((index * step) + 1 < arr.length) {
         preTraverse((index * step) + 1);
      }
      //向右递归
      if((index * step) + 2 < arr.length) {
         preTraverse((index * step) + 2);
      }
   }
​
   public void midTraverse() {
      midTraverse(0);
   }
​
   private void midTraverse(int index) {
      if(arr == null || arr.length == 0) {
         System.out.println("数组为空!");
      }
​
      //左递归
      if((index * step) + 1 < arr.length) {
         midTraverse((index * step) + 1);
      }
      System.out.print(arr[index] + " ");
      //右递归
      if((index * step) + 2 < arr.length) {
         midTraverse((index * step) + 2);
      }
   }
​
   public void lastTraverse() {
      lastTraverse(0);
   }
​
   private void lastTraverse(int index) {
      if(arr == null || arr.length == 0) {
         System.out.println("数组为空!");
      }
      //左递归
      if((index * step) + 1 < arr.length) {
         lastTraverse((index * step) + 1);
      }
      //右递归
      if((index * step) + 2 < arr.length) {
         lastTraverse((index * step) + 2);
      }
      System.out.print(arr[index] + " ");
   }
}

2、线索化二叉树

2.1、线索化二叉树的来源

因为一般的二叉树，叶子节点的左右指针都为空，这样就会造成空间的浪费。为了减少浪费，便有了线索化二叉树

2.2、线索化二叉树的特点

• n个结点的二叉链表中含有 n+1 【公式 2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，存放指向该结点在某种遍历次序(前序、中序、后序)下的前驱和后继结点的指针

• 这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树

• 根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种

• 如果一个节点已经有了左右孩子节点，那么该节点就不能被线索化了，所以线索化二叉树后，节点的left和right有如下两种情况

  • left可能指向的是左孩子节点，也可能指向的是前驱节点

  • right可能指向的是右孩子节点，也可能指向的是后继节点

2.3、线索化二叉树的问题解决

因为left和right可能指向左右节点，也可能指向前驱、后继节点，所以为了区分，给节点加上标志位

2.3、线索化二叉树代码实现

class ThreadedBinaryTree {
  private Student root;
  /**
   * 指向当前节点的前一个节点
   */
  private Student pre;
​
  public void setRoot(Student root) {
    this.root = root;
  }
​
  /**
   * 中序线索化
   * @param node 当前节点
   */
  private void midThreaded(Student node) {
    if(node == null) {
      return;
    }
    //左线索化
    midThreaded(node.getLeft());
        
    //线索化当前节点
    //如果当前节点的左指针为空，就指向前驱节点，并改变左指针类型
    if(node.getLeft() == null) {
      node.setLeft(pre);
      node.setLeftType(1);
    }
    //通过前驱节点来将右指针的值令为后继节点
    if(pre != null && pre.getRight() == null) {
      pre.setRight(node);
      pre.setRightType(1);
    }
​
    //处理一个节点后，让当前节点变为下一个节点的前驱节点
    pre = node;
​
    //右线索化
    midThreaded(node.getRight());
  }
​
  public void midThreaded() {
    midThreaded(root);
  }
​
  /**
   * 遍历线索化后的二叉树
   */
  public void midThreadedTraverse() {
    //暂存遍历到的节点
    Student tempNode = root;
    //非递归的方法遍历，如果tempNode不为空就一直循环
    while(tempNode != null) {
      //一直访问二叉树的左子树，直到某个节点的左子树指向前驱节点
      while(tempNode.getLeftType() != 1) {
        tempNode = tempNode.getLeft();
      }
      //找到了第一个节点
      System.out.println(tempNode);
      //再访问该节点的右子树，看是否保存了后继节点
      //如果是，则打印该节点的后继节点信息
      while(tempNode.getRightType() == 1) {
        tempNode = tempNode.getRight();
        System.out.println(tempNode);
      }
​
      tempNode = tempNode.getRight();
    }
​
  }
}
​
@Data
class Student {
  private int id;
  private String name;
  private Student left;
  private Student right;
  /**
   * 左、右指针的类型，0-->指向的是左右孩子，1-->指向的是前驱、后续节点
   */
  private int leftType = 0;
  private int rightType = 0;
​
  public Student(int id, String name) {
    this.id = id;
    this.name = name;
  }
​
​
  @Override
  public String toString() {
    return "Student{" +
        "id=" + id +
        ", name='" + name + '\'' +
        '}';
  }
}