Day21二叉树快速入门学习（Java）

Day21二叉树快速入门学习（Java） 一、为什么要使用树这种数据结构

1)数组存储方式的分析

优点：通过下标方式访问元素，速度快。对于有序数组，还可使用二分查找提高检索速度。

缺点：如果要检索具体某个值，或者插入值(按一定顺序)会整体移动，效率较低 [示意图]

2)链式存储方式的分析

优点：在一定程度上对数组存储方式有优化(比如：插入一个数值节点，只需要将插入节点，链接到链表中即可， 删除效率也很好)。

缺点：在进行检索时，效率仍然较低，比如(检索某个值，需要从头节点开始遍历) 【示意图】

3)树存储方式的分析

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

【示意图,后面详讲】

案例: [7, 3, 10, 1, 5, 9, 12]

二、什么是二叉树

二叉树示意图

概念

三、二叉树前中后序遍历

遍历说明

前序遍历: 先输出父节点，再遍历左子树和右子树

中序遍历: 先遍历左子树，再输出父节点，再遍历右子树

后序遍历: 先遍历左子树，再遍历右子树，最后输出父节点

小结: 看输出父节点的顺序，就确定是前序，中序还是后序

遍历要求

代码实现

package com.fafa.tree;


public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 创建节点
        HeroNode root = new HeroNode(1, "宋江");
        HeroNode node2 = new HeroNode(2, "吴用");
        HeroNode node3 = new HeroNode(3, "卢俊义");
        HeroNode node4 = new HeroNode(4, "林冲");
        HeroNode node5 = new HeroNode(5, "吴胜");
        // 先手动生成二叉树（后面会用递归来生成，暂时先手动）
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        // 创建二叉树
        BinaryTree tree = new BinaryTree(root);
        // 测试前序遍历
        System.out.println("前序遍历");
        tree.preOrder();
        // 测试中序遍历
        System.out.println("中序遍历");
        tree.infixOrder();
        // 测试后序遍历
        System.out.println("后序遍历");
        tree.postOrder();

    }

}


class BinaryTree {

    HeroNode root = null;

    public BinaryTree(HeroNode root) {
        this.root = root;
    }

    
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("这是一颗空树");
        }
    }

    
    public void infixOrder() {
        if (this.root != null) {
            this.root.infixOrder();
        } else {
            System.out.println("这是一颗空树");
        }
    }

    
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("这是一颗空树");
        }
    }


}


class HeroNode {
    private int id;
    private String name;
    private HeroNode left;
    private HeroNode right;

    
    public HeroNode(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 HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
            "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 infixOrder() {
        if (this.left != null) {
            this.left.infixOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.infixOrder();
        }
    }

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

四、二叉树前中后序查找

需求

代码实现

添加到HeroNode类里

public HeroNode preOrderSearch(int no) {
    System.out.println("get into preSearch~");
    // 比较当前节点是不是
    if (this.getId() == no) {
        return this;
    }
    // 结果节点
    HeroNode resNode = null;
    // 比较左子节点
    // 和遍历的思路大同小异
    // 1、判断当前的做自己额点是否为空，如不为空则继续遍历查找（递归）
    // 2、如左子节点找到结果，则直接返回
    if (this.left != null) {
        resNode = this.left.preOrderSearch(no);
    }
    // 如果不为空，说明在左子树找到了
    if (resNode != null) {
        return resNode;
    }
    // 同上，只不过最后直接返回resNode即可，因为无论找到没，都是resNode
    if (this.right != null) {
        resNode = this.right.preOrderSearch(no);
    }
    return resNode;
}


public HeroNode infixOrderSearch(int no) {
    // 结果节点
    HeroNode resNode = null;
    // 比较左子节点
    // 和遍历的思路大同小异
    // 1、判断当前的做自己额点是否为空，如不为空则继续遍历查找（递归）
    // 2、如左子节点找到结果，则直接返回
    if (this.left != null) {
        resNode = this.left.infixOrderSearch(no);
    }
    // 如果不为空，说明在左子树找到了
    if (resNode != null) {
        return resNode;
    }
    // 要放在比较语句前面，不能单纯的写在最前面（因为统计的是比较次数）
    System.out.println("get into infixSearch~");
    // 比较当前节点是不是
    if (this.getId() == no) {
        return this;
    }
    // 同上，只不过最后直接返回resNode即可，因为无论找到没，都是resNode
    if (this.right != null) {
        resNode = this.right.infixOrderSearch(no);
    }
    return resNode;
}


public HeroNode postOrderSearch(int no) {

    // 结果节点
    HeroNode resNode = null;
    // 比较左子节点
    // 和遍历的思路大同小异
    // 1、判断当前的做自己额点是否为空，如不为空则继续遍历查找（递归）
    // 2、如左子节点找到结果，则直接返回
    if (this.left != null) {
        resNode = this.left.postOrderSearch(no);
    }
    // 如果不为空，说明在左子树找到了
    if (resNode != null) {
        return resNode;
    }
    // 同上，只不过最后直接返回resNode即可，因为无论找到没，都是resNode
    if (this.right != null) {
        resNode = this.right.postOrderSearch(no);
    }
    if (resNode != null) {
        return resNode;
    }
    // 要放在比较语句前面，不能单纯的写在最前面（因为统计的是比较次数）
    System.out.println("get into postSearch~");
    // 如果左右子树都没找到
    if (this.getId() == no) {
        return this;
    }
    return null;
}

五、二叉树删除节点

要求

代码实现

在HeroNode类里添加

public void delNode(int no) {
    //思路
    
    if (this.left != null && this.left.getId() == no) {
        // 置为空
        this.setLeft(null);
        return;
    }
    if (this.right != null && this.right.getId() == no) {
        this.setRight(null);
        return;
    }
    if (this.left != null) {
        this.left.delNode(no);
    }
    if (this.right != null) {
        this.right.delNode(no);
    }
}

在BinaryTree类里添加

public void delNode(int no) {
    if (root != null) {
        // 这要判断待删除节点是否为根节点
        if (root.getId() == no) {
            root = null;
        } else {
            root.delNode(no);
        }
    } else {
        System.out.println("空数，无法删除~");
    }
}

课后思考