二叉树

二叉树

二叉树的概念

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. 对于遍历的方法而言，必须先判定是否为空，否则会出现空指针