【二叉树详解】二叉树的创建、遍历、查找以及删除等-数据结构05

定义： 每一个结点的子节点数量不超过 2

二叉树的结点分为：左节点、右节点

满二叉树： 每个结点都有两个子结点的二叉树（除了叶子结点外）

完全二叉树： 除去最后一层，是一个满二叉树，并且最后一层结点左连续

(从左到右，从上到下，依次编号1,2,3,4…，这样的编号和满二叉树一一对应的二叉树叫完全二叉树)

思路： 首先必须有一个BinaryTree 二叉树的类-用于设置根节点(也可以是一颗空树)

​ 其次需要结点 TreeNode 来构建二叉树

​ 结点包含：value结点值、leftNode左节点、rightNode右节点 以及设置/获取左右节点的方法

创建一个如下图的二叉树

具体化以后：

代码：

//二叉树
public class BinaryTree {
    //根节点
    TreeNode root;
    //设置根节点、获取根节点
    public TreeNode getRoot() {
        return root;
    }
    public void setRoot(TreeNode root) {
        this.root = root;
    }
}

//树的结点
public class TreeNode {
    //结点的值
    int value;
    //左节点
    TreeNode leftNode;
    //右节点
    TreeNode rightNode;
    //初始化值
    public TreeNode(int value){
        this.value=value;
    }
    //设置左节点
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }
    //设置右节点
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }
}

测试类：

public class TestBinaryTree {
    public static void main(String[] args) {
        //创建一颗空二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建根结点
        TreeNode root=new TreeNode(1);
        binaryTree.setRoot(root);
        //创建根结点的左节点和右节点
        TreeNode leftNode = new TreeNode(2);
        TreeNode RightNode = new TreeNode(3);
        //将左右结点连接在根结点后
        root.setLeftNode(leftNode);
        root.setRightNode(RightNode);
    }
}

三种遍历方式： 前序遍历、中序遍历、后续遍历

(这里的前中后，都是对于当前结点而言)

前序遍历-当前结点在左右结点的前面：简记为 “根左右”

中序遍历-当前结点在左右结点的中间-“左根右”

后序遍历-当前结点在左右结点的后面-“左右根”

举个栗子：

前序遍历：1 2 4 5 3 6 7

中序遍历：4 2 5 1 6 3 7

后序遍历：4 5 2 6 7 3 1

代码实现：

TreeNode.java 中 (代码没有前部写出，前面已经写过的代码略)

    //前序遍历
    public void frontShow(){
        //遍历当前节点
        System.out.print(value+" ");
        //遍历左节点
        if(leftNode!=null){
            leftNode.frontShow();
        }
        //遍历右节点
        if(rightNode!=null){
            rightNode.frontShow();
        }
    }
    //中序遍历
    public void midShow(){
        //遍历左子节点
        if(leftNode!=null){
            leftNode.midShow();
        }
        //遍历当前节点
        System.out.print(value+" ");
        //遍历右子节点
        if(rightNode!=null){
            rightNode.midShow();
        }
    }
    //后序遍历
    public void afterShow(){
        //遍历左子节点
        if(leftNode!=null){
            leftNode.afterShow();
        }
        //遍历右子节点
        if(rightNode!=null){
            rightNode.afterShow();
        }
        //遍历当前节点
        System.out.print(value+" ");
    }

BinaryTree中实现封装：

//前中后序遍历
    public void frontShow(){
        root.frontShow();
    }
    public void midShow(){
        root.midShow();
    }
    public void afterShow(){
        root.afterShow();
    }

测试：

public class TestBinaryTree {
    public static void main(String[] args) {
        //创建一颗空二叉树
        BinaryTree binaryTree = new BinaryTree();
        //创建根结点
        TreeNode root=new TreeNode(1);
        binaryTree.setRoot(root);
        //创建根结点的左节点和右节点
        TreeNode leftNode = new TreeNode(2);
        TreeNode rightNode = new TreeNode(3);
        //将左右结点连接在根结点后
        root.setLeftNode(leftNode);
        root.setRightNode(rightNode);
        //增加四个节点 4、5、6、7方便遍历
        leftNode.setLeftNode(new TreeNode(4));
        leftNode.setRightNode(new TreeNode(5));
        rightNode.setLeftNode(new TreeNode(6));
        rightNode.setRightNode(new TreeNode(7));
        //前序、中序、后序遍历
        System.out.print("前序遍历：");
        binaryTree.frontShow();
        System.out.print("n中序遍历：");
        binaryTree.midShow();
        System.out.print("n后序遍历：");
        binaryTree.afterShow();
        System.out.println();
    }
}

结果：

前序遍历：1 2 4 5 3 6 7 
中序遍历：4 2 5 1 6 3 7 
后序遍历：4 5 2 6 7 3 1 

可以看到和我们上面分析的结果一模一样

三种查找方式：前序、中序、后序查找
和遍历差不多，不同的是传入一个要查找的值，并且返回目标结点

三种查找实现差不多，只是查找顺序不同

代码：

    //前序查找
    public TreeNode frontSearch(int value){
        //目标节点
        TreeNode target=null;
        //先查找当前结点，如果值相同直接返回
        if(this.value==value){
            return this;
        }
        //查找左子节点
        if(leftNode!=null){
            target = leftNode.frontSearch(value);
            //如果左子节点返回的值不为空，则找到，直接返回
            if(target!=null){
                return target;
            }
        }
        //查找右子节点
        if(rightNode!=null){
           target = rightNode.frontSearch(value);
        }
        //返回
        return target;
    }

    //中序查找
    public TreeNode midSearch(int value){
        //目标节点
        TreeNode target=null;
        //先查找左子节点
        if(leftNode!=null){
            target = leftNode.midSearch(value);
            //如果左子节点返回的值不为空，则找到，直接返回
            if(target!=null){
                return target;
            }
        }
        //再查找当前结点，如果值相同直接返回
        if(this.value==value){
            return this;
        }
        //最后查找右子节点
        if(rightNode!=null){
            target = rightNode.midSearch(value);
        }
        //返回
        return target;
    }

    //后序查找
    public TreeNode afterSearch(int value){
        //目标节点
        TreeNode target=null;
        //先查找左子节点
        if(leftNode!=null){
            target = leftNode.afterSearch(value);
            //如果左子节点返回的值不为空，则找到，直接返回
            if(target!=null){
                return target;
            }
        }

        //再查找右子节点
        if(rightNode!=null){
            target = rightNode.afterSearch(value);
            if(target!=null){
                return target;
            }
        }

        //最后查找当前结点，如果值相同直接返回
        if(this.value==value){
            target=this;
        }
        //返回
        return target;
    }

BinaryTree中实现封装：

//前中后序查找
    public TreeNode frontSearch(int value){
        return root.frontSearch(value);
    }
    public TreeNode midSearch(int value){
        return root.midSearch(value);
    }
    public TreeNode afterSearch(int value){
        return root.afterSearch(value);
    }

测试：

//查找
System.out.println(binaryTree.frontSearch(3)==rightNode);
System.out.println(binaryTree.midSearch(6));
System.out.println(binaryTree.afterSearch(7));

结果：

true
com.dong.DataStructrue.Day_06.TreeNode@1554909b
com.dong.DataStructrue.Day_06.TreeNode@6bf256fa

可以看到，无论用什么查找方式都可以找到树中有的结点

思路： 想删除一个结点，可以让其父节点指向它的TreeNode为null即可

​ 当删除的不是叶子节点，相当于删除子树

注意： 以下的删除方法只适用于 结点值不重复时

代码：

BinaryTree

//删除结点(子树)
    public void delete(int value){
        if(root!=null){
            //如果根节点是要删除的结点直接删除
            if(root.value==value){
                root=null;
            }else{
                //递归
                root.delete(value);
            }
        }else{
            System.out.println("当前是一颗空树，无法删除！");
        }
    }

TreeNode：

//删除结点(子树)
    public void delete(int value) {
        //存储父节点
        TreeNode parentNode=this;
        //判断左子节点
        if(parentNode.leftNode!=null&&parentNode.leftNode.value==value){
            //删除
            parentNode.leftNode=null;
            return;
        }
        //判断右节点
        if(parentNode.rightNode!=null&&parentNode.rightNode.value==value){
            //删除
            parentNode.rightNode=null;
            return;
        }
        //将左节点作为父节点，递归删除
        parentNode=leftNode;
        if(parentNode!=null){
            parentNode.delete(value);
        }
        //将右节点作为父节点，递归删除
        parentNode=rightNode;
        if(parentNode!=null){
            parentNode.delete(value);
        }
    }

测试：

//删除结点
System.out.print("删除前：");
binaryTree.frontShow();
System.out.println();
//这里4、7都是删除两个叶子结点
System.out.print("删除4：");
binaryTree.delete(4);
binaryTree.frontShow();
System.out.println();

System.out.print("删除7：");
binaryTree.delete(7);
binaryTree.frontShow();
System.out.println();
//这里相当于删除了子树
System.out.print("删除2：");
binaryTree.delete(2);
binaryTree.frontShow();

结果：

删除前： 1 2 4 5 3 6 7 
删除4： 1 2 5 3 6 7 
删除7： 1 2 5 3 6 
删除2： 1 3 6 

思路：使用数组来存储，通过数组下标关系来找到左节点和右节点以及父节点，从而实现顺序存储二叉树

代码：

public class ArrayBinaryTree {
    //存储数据
    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }
    //不传参数，默认从0开始遍历
    public void frontShow(){
        frontShow(0);
    }
    //前序遍历，传入参数-从哪个下标开始遍历
    public void frontShow(int index){
        //当数据为空时
        if(data.length==0||data==null){
            System.out.print("当前为空树");
            return;
        }
        System.out.print(data[index]+" ");
        //遍历左节点=index*2+1
        if(index*2+1 
测试：
 
public class TestArrayBinaryTree {
    public static void main(String[] args) {
        //创建数组，传入值
        int[] data=new int[]{1,2,3,4,5,6,7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(data);
        //前序遍历，从0开始
        System.out.print("前序遍历：");
        arrayBinaryTree.frontShow();
    }
}
 
结果：
 
前序遍历： 1 2 4 5 3 6 7