数据结构与算法(十九)二叉树基本操作

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

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

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

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

二叉树的概念

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

二叉树的遍历

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

二叉树-删除节点

  • 如果删除的节点是叶子节点,则删除该节点
  • 如果删除的节点是非叶子节点,则删除该子树.

代码实现

树节点
/**
 * 树节点
 */
class Node{

    private int no;

    private String name;

    private Node leftNode;

    private Node rightNode;

    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }

    /**
     * 前序遍历
     */
    public void preOrder(){
        System.out.println(this);
        if (this.leftNode!=null){
            this.leftNode.preOrder();
        }
        if (this.rightNode!=null){
           this.rightNode.preOrder();
        }
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if (this.leftNode!=null){
            this.leftNode.infixOrder();
        }
        System.out.println(this);

        if (this.rightNode!=null){
            this.rightNode.infixOrder();
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder(){
        if (this.leftNode!=null){
            this.leftNode.postOrder();
        }
        if (this.rightNode!=null){
            this.rightNode.postOrder();
        }
        System.out.println(this);
    }



    /**
     * 前序遍历 查询
     */
    public Node preOrderSearch(int no){
        if (this.no == no){
            return this;
        }
        Node resNode=null;
        if (this.leftNode!=null){
            resNode = this.leftNode.preOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }

        if (this.rightNode!=null){
            resNode=this.rightNode.preOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 中序遍历查询
     */
    public Node infixOrderSearch(int no){
        Node resNode=null;
        if (this.leftNode!=null){
            resNode = this.leftNode.infixOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.no == no){
            return this;
        }
        if (this.rightNode!=null){
            resNode=this.rightNode.infixOrderSearch(no);
        }
        return resNode;
    }

    /**
     * 后续遍历 查询
     */
    public Node postOrderSearch(int no){
        Node resNode=null;
        if (this.leftNode!=null){
            resNode = this.leftNode.postOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.rightNode!=null){
            resNode=this.rightNode.postOrderSearch(no);
        }
        if (resNode!=null){
            return resNode;
        }
        if (this.no == no){
            return this;
        }
        return resNode;
    }


    /**
     * 删除节点
     * @param no
     */
    public void delNode(int no){
        if (this.leftNode!=null&&this.leftNode.no==no){
            this.leftNode=null;
            return;
        }

        if (this.rightNode!=null&&this.rightNode.no==no){
            this.rightNode=null;
            return;
        }
        if (this.leftNode!=null){
            this.leftNode.delNode(no);
        }
        if (this.rightNode!=null){
            this.rightNode.delNode(no);
        }

    }




    public void setNo(int no) {
        this.no = no;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setLeftNode(Node leftNode) {
        this.leftNode = leftNode;
    }

    public void setRightNode(Node rightNode) {
        this.rightNode = rightNode;
    }

    public int getNo() {
        return no;
    }

    public String getName() {
        return name;
    }

    public Node getLeftNode() {
        return leftNode;
    }

    public Node getRightNode() {
        return rightNode;
    }

    @Override
    public String toString() {
        return "Node{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }
}
二叉树

/**
 * 二叉树
 */
public class BinaryTree {

    /**
     * 根节点
     */
    private Node root;

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

    /**
     * 前序遍历 查询
     */
    public Node preOrderSearch(int no){
        if (root!=null){
            return  root.preOrderSearch(no);
        }
        return null;

    }

    /**
     * 中序遍历 查询
     */
    public Node  infixOrderSearch(int no){
        if (root!=null){
            return  root.infixOrderSearch(no);
        }
        return null;
    }

    /**
     * 后续遍历 查询
     */
    public Node postOrderSearch(int no){
        if (root!=null){
            return  root.postOrderSearch(no);
        }
        return null;
    }





    /**
     * 前序遍历
     */
    public void preOrder(){
        if (root!=null){
            root.preOrder();
        }else {
            System.out.println("没有数据");
        }
    }

    /**
     * 中序遍历
     */
    public void  infixOrder(){
        if (root!=null){
            root.infixOrder();
        }else {
            System.out.println("没有数据");
        }
    }

    /**
     * 后续遍历
     */
    public void postOrder(){
        if (root!=null){
            root.postOrder();
        }else {
            System.out.println("没有数据");
        }
    }

    /**
     * 删除节点
     * @param no
     */
    public void delNode(int no){
        if (root!=null){
            root.delNode(no);
        }

    }

    public static void main(String[] args) {
        Node node1 = new Node(1, "a");
        Node node2= new Node(2, "b");
        Node node3 = new Node(3, "c");
        Node node4 = new Node(4, "d");
        Node node5 = new Node(5, "e");
        node1.setLeftNode(node2);
        node1.setRightNode(node3);

        node3.setLeftNode(node5);

        node3.setRightNode(node4);
        BinaryTree binaryTree = new BinaryTree(node1);
        //binaryTree.preOrder();
    //binaryTree.infixOrder();

        //binaryTree.postOrder();

        //Node node = binaryTree.postOrderSearch(5);
        //System.out.println(node);

        binaryTree.preOrder();
        binaryTree.delNode(5);
        binaryTree.preOrder();

    }


}

Copyright: 采用 知识共享署名4.0 国际许可协议进行许可

Links: https://www.fengpt.cn/archives/数据结构与算法十九二叉树