0087 二叉树

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  

package Tree_;

/*
 * 数组存储方式
 * 优点：通过下标方式访问元素，速度较快，对于有序数组，可用二分查找提高速度
 * 缺点：要检索某个具体值或插入值会整体移动，效率低
 * 
 * 链式存储
 * 优点；插入与删除时效率较高，一定程度上优化了数组存储
 * 缺点：在进行检索时效率低，需要从头开始遍历
 * 
 * 树存储
 * 提高数据存储，读取的效率，如二叉排序树，既可以保证数据的检索速度，也可以保证数据的插入，删除，修改的速度
 * 
 * 树的常用术语
 * 1.节点
 * 2.根节点
 * 3.父节点
 * 4.子节点
 * 5.叶子节点
 * 6.节点的权（节点值）
 * 7.路径（从根节点找到该节点的路线）
 * 8.层
 * 9.子树
 * 10.树的高度（最大层数）
 * 11.森林：多颗子树构成森林
 * 
 * 二叉树
 * 1.每个节点最多只能有两个子节点的一种形式称为二叉树
 * 2.二叉树的子节点分为左节点和右节点
 * 3.如果该二叉树的所有叶子节点都在最后一层，且节点总数=2ⁿ-1，n为层数，则称为满二叉树
 * 4.如果该二叉树的所有叶子节点都在最后一层或倒数第二层，且最后一层的叶子节点在左边连续，倒数第二层的叶子节点在右边连续
 *   称为完全二叉树
 * 
 * 二叉树的遍历
 * 1.前序遍历：先输出父节点，再遍历左子树和右子树
 * 2.中序遍历：先遍历左子树，再输出父节点，再遍历右子树
 * 3.后序遍历：先遍历左子树，再遍历右子树，最后输出父节点
 * 即：看输出父节点的顺序，就确定是前序，中序还是后序
 * 
 * 遍历步骤
 * 创建二叉树
 * 1.前序遍历
 *         1.先输出当前节点（初始为根节点）
 *         2.如果左子节点不为空，则递归继续前序遍历
 *         3.如果右子节点不为空，则递归继续前序遍历
 * 2.中序遍历
 *         1.如果当前节点的左子节点不为空，则递归中序遍历
 *         2.输出当前节点
 *         3.如果当前节点的右子节点不为空，则递归中序遍历
 * 3.后序遍历
 *         1.如果当前节点的左子节点不为空，则递归后序遍历
 *         2.如果当前节点的右子节点不为空，则递归后序遍历
 *         3.输出当前节点
 * 
 * 查找
 * 1.前序查找
 *         1.判断 当前节点 是否等于要查找的，如果相等则返回
 *         2.如果不等，则判断 当前节点的左子节点 是否为空，如果不为空，则递归前序查找，找到则返回
 *         3.找不到则判断 当前节点的右子节点 是否为空，如果不为空，则递归前序查找
 * 2.中序查找
 *         1.判断 当前节点的左子节点 是否为空，如果不为空，则递归中序查找，如果找到则返回
 *         2.找不到则判断 当前节点 是否等于要查找的，如果相等则返回
 *         3.如果不等，则判断 当前节点的右子节点 是否为空，如果不为空，则递归中序查找
 * 3.后序查找
 *         1.判断 当前节点的左子节点 是否为空，如果不为空，则递归后序查找，如果找到则返回
 *         2.找不到则判断 当前节点的右子节点 是否为空，如果不为空，则递归后序查找
 *         3.否则和 当前节点 进行比较，是则返回
 * 
 * 删除（待删除结点是叶子节点，则删除，是非叶子节点，则删除该子树）
 * 1.判断当前节点的子节点是否是需要删除的节点，而不能去判断当前这个节点是否是删除的节点
 * 2.若当前节点的左子节点不为空，且左子节点就是要删除的，就 this.left = null，并且返回（结束递归）
 * 3.若当前节点的右子节点不为空，且右子节点就是要删除的，就 this.right = null，并且返回（结束递归）
 * 4.若第2，3步没有删除，就向左子树进行递归删除
 * 5.若第4步没有删除，就向右子树进行递归删除
 * 
 * 
 */
public class BinaryTree_ {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        //创建节点
        Node root = new Node(1, "宋江");
        Node node2 = new Node(2, "卢俊义");
        Node node3 = new Node(3, "吴用");
        Node node4 = new Node(4, "公孙胜");
        Node node5 = new Node(5, "关胜");
        
        //手动创建二叉树（后面学习递归方式创建）
        //宋江的左子节点为卢俊义，右子节点为吴用
        //吴用的左子节点为关胜，右子节点为公孙胜
        root.setLeft(node2);
        root.setRight(node3);
        node3.setRight(node4);
        node3.setLeft(node5);
        binaryTree.setRoot(root);
        
        
        //遍历
        System.out.println("前序遍历");//12354
        binaryTree.preOrder();
        System.out.println("中序遍历");//21543
        binaryTree.infixOrder();
        System.out.println("后序遍历");
        binaryTree.postOrder();//25431
        
        //查找
        System.out.println("前序查找：");
        System.out.println(binaryTree.preOrderSearch(5));//次数为4
        System.out.println("中序查找：");
        System.out.println(binaryTree.infixOrderSearch(5));//次数为3
        System.out.println("后序查找：");
        System.out.println(binaryTree.postOrderSearch(5));//次数为2
        
        //删除
        System.out.println("前序遍历删除前");
        binaryTree.preOrder();//12354
        binaryTree.delNode(5);
        System.out.println("前序遍历删除后");
        binaryTree.preOrder();//1234
    }
}
//定义二叉树
class BinaryTree{
    private Node root;
    
    public void setRoot(Node 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("二叉树为空，无法遍历");
        }
    }
    
    //前序查找
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }
    
    //中序查找
    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    
    //后序查找
    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
    
    //删除
    public void delNode(int no) {
        if (root != null) {
            if (root.getNo() == no) {
                root = null;
            }else {
                root.delNode(no);
            }
        }else {
            System.out.println("空树，无法删除");
        }
    }
}

//创建Node节点
class Node{
    private int no;
    private String name;
    private Node left;//默认为null
    private Node right;
    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    @Override
    public String toString() {
        return "Node [no=" + no + ", 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);
    }
    
    //前序查找
    //no为要查找的值，找到返回Node，找不到返回null
    public Node preOrderSearch(int no) {
        System.out.println("前序次数");
        //比较当前节点
        if (this.no == no) {
            return this;
        }
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {//说明找到了
            return resNode;
        }
        
        //右子节点
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    
    //中序查找
    public Node infixOrderSearch(int no) {
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("中序次数");
        //当前节点
        if (this.no == no) {
            return this;
        }
        //右子节点
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }
    
    //后序查找
    public Node postOrderSearch(int no) {
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右子节点
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序次数");
        //当前节点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }
    
    //删除
    public void delNode(int no) {
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return;
        }
        if (this.left != null) {
            this.left.delNode(no);
        }
        if (this.right != null) {
            this.right.delNode(no);
        }
    }
}

/*
 * 顺序存储二叉树
 * 从数据存储来看，数组存储方式和树的存储方式可以相互转换，即数组可以转换成树，树可以转换成数组
 * 
 * 特点
 * n表示二叉树中的第几个元素（从0开始）
 * 1.顺序二叉树通常只考虑完全二叉树
 * 2.第n个元素的左子节点为 2*n+1
 * 3.第n个元素的右子节点为 2*n+2
 * 4.第n个元素的父节点为 (n-1)/2
 * 
 * 需求
 * 给一个数组{1，2，3，4，5，6，7}，要求以二叉树前序遍历的方式进行遍历，前序遍历的结果应为1，2，4，5，3，6，7
 * 
 */
public class ArrayBinaryTree_ {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7};
        ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(arr);
        arrayBinaryTree.preOrder();//1245367
    }
}

//编写ArrayBinaryTree，实现顺序存储二叉树遍历
class ArrayBinaryTree{
    private int[] arr;//存储数据结点的数组
    
    public ArrayBinaryTree(int[] arr) {
        this.arr = arr;
    }
    
    //重载preOrder,代码简洁
    public void preOrder() {
        this.preOrder(0);
    }
    
    //编写一个方法，完成顺序存储二叉树的前序遍历
    //index:数组下标
    public void preOrder(int index) {
        //判断空
        if (arr == null || arr.length == 0) {
            System.out.println("数组为空，无法遍历");
        }
        //输出当前这个元素
        System.out.println(arr[index]);
        //向左递归遍历
        if ((index * 2 + 1) < arr.length) {
            preOrder(index * 2 + 1);
        }
        //向右递归
        if ((index *2 + 2) < arr.length) {
            preOrder(index * 2 + 2);
        }
    }
}

/*
 * 线索化二叉树
 * 1.n个结点的二叉链表中含有n+1【2n-(n-1)=n+1】个空指针域。利用二叉链表中的空指针域，
 *   存放指向该结点在某种遍历次序下的前驱和后继结点的指针（这种附加的指针称为线索）
 *   
 * 2.这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树（Thread BinaryTree）
 *   根据线索性质的不同，可分为前序线索二叉树、中序线索二叉树和后序线索二叉树
 *   
 * 3.一个结点的前一个结点称为前驱结点，一个结点的后一个结点称为后继结点
 * 
 * 当线索化二叉树后，Node节点的left和right，有如下情况
 * 1.left指向的是左子树，也可能是指向前驱节点
 * 2.right指向的是右子树，也可能是指向后继节点
 * 
 * 遍历线索化二叉树（当线索化二叉树后，原来的遍历方法不能再使用）
 * 1.各个节点可以通过线形方式遍历，无需使用递归方式，也提高了效率
 * 2.遍历次序应当和中序遍历保持一致
 * 
 */
public class ThreadBinaryTree_ {
    public static void main(String[] args) {
        Node root = new Node(1, "tom");
        Node node2 = new Node(3, "jack");
        Node node3 = new Node(6, "smith");
        Node node4 = new Node(8, "mary");
        Node node5 = new Node(10, "king");
        Node node6 = new Node(14, "john");
        
        //手动创建
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        
        //中序线索化
        ThreadBinaryTree threadBinaryTree = new ThreadBinaryTree();
        threadBinaryTree.setRoot(root);
        threadBinaryTree.threadNode();
        
        //测试node5节点是否中序线索化
        Node leftNode = node5.getLeft();
        System.out.println("node5的前驱节点=" + leftNode);
        Node rightNode = node5.getRight();
        System.out.println("node5的后继节点=" + rightNode);
        
        //线索化中序遍历
        threadBinaryTree.threadList();
    }
}

//线索化二叉树
class ThreadBinaryTree{
    private Node root;
    //为了实现线索化，需要创建一个指向当前节点的前驱节点的指针
    private Node pre = null;
    
    //重载线索化方法
    public void threadNode() {
        this.threadNode(root);
    }
    
    public void setRoot(Node root) {
        this.root = root;
    }
    
    //遍历线索化二叉树的方法
    public void threadList() {
        //定义一个变量，存储当前遍历的节点，从root开始
        Node node = root;
        while(node != null) {
            //循环找到leftType == 1 的节点，第一个找到的是8
            while(node.getLeftType() == 0) {
                node = node.getLeft();
            }
            //打印当前节点
            System.out.println(node);
            //当前节点的右指针指向的是后继节点，就一直输出
            while(node.getRightType() == 1) {
                //获取当前节点的后继节点
                node = node.getRight();
                System.out.println(node);
            }
            //替换这个遍历的节点
            node = node.getRight();
        }
    }
    
    //编写二叉树进行中序线索化的方法
    //node:当前需要线索化的节点
    public void threadNode(Node node) {
        //node==null，不能线索化
        if (node == null) {
            return;
        }
        
        //1.线索化左子树
        threadNode(node.getLeft());
        //2.线索化当前节点
        //处理当前节点的前驱节点
        if (node.getLeft() == null) {
            //让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            //修改当前节点的左指针类型，指向前驱节点
            node.setLeftType(1);
        }
        
        //处理后继节点
        if (pre != null && pre.getRight() == null) {
            //让前驱节点的右指针指向该节点
            pre.setRight(node);
            //修改当前节点的右指针类型，指向后继节点
            pre.setRightType(1);
        }
        //没处理一个节点后，让当前节点是下一个节点的前驱节点
        pre = node;
        
        
        //3.线索化右子树
        threadNode(node.getRight());
    }
    
    //前序遍历
    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("二叉树为空，无法遍历");
        }
    }
    
    //前序查找
    public Node preOrderSearch(int no) {
        if (root != null) {
            return root.preOrderSearch(no);
        }else {
            return null;
        }
    }
    
    //中序查找
    public Node infixOrderSearch(int no) {
        if (root != null) {
            return root.infixOrderSearch(no);
        }else {
            return null;
        }
    }
    
    //后序查找
    public Node postOrderSearch(int no) {
        if (root != null) {
            return root.postOrderSearch(no);
        }else {
            return null;
        }
    }
}

//创建Node节点
class Node{
    private int no;
    private String name;
    private Node left;//默认为null
    private Node right;
    //如果leftType==0,表示指向的是左子树，1表示指向前驱节点
    //如果rightType==0,表示指向的是右子树，1表示指向后继节点
    private int leftType;
    private int rightType;
    
    public Node(int no, String name) {
        this.no = no;
        this.name = name;
    }
    public int getNo() {
        return no;
    }
    public void setNo(int no) {
        this.no = no;
    }
    public String getName() {
        return name;
    }
    public void setName(String name) {
        this.name = name;
    }
    public Node getLeft() {
        return left;
    }
    public void setLeft(Node left) {
        this.left = left;
    }
    public Node getRight() {
        return right;
    }
    public void setRight(Node right) {
        this.right = right;
    }
    
    public int getLeftType() {
        return leftType;
    }
    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }
    public int getRightType() {
        return rightType;
    }
    public void setRightType(int rightType) {
        this.rightType = rightType;
    }
    @Override
    public String toString() {
        return "Node [no=" + no + ", 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);
    }
    
    //前序查找
    //no为要查找的值，找到返回Node，找不到返回null
    public Node preOrderSearch(int no) {
        System.out.println("前序次数");
        //比较当前节点
        if (this.no == no) {
            return this;
        }
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.preOrderSearch(no);
        }
        if (resNode != null) {//说明找到了
            return resNode;
        }
        
        //右子节点
        if (this.right != null) {
            resNode = this.right.preOrderSearch(no);
        }
        return resNode;
    }
    
    //中序查找
    public Node infixOrderSearch(int no) {
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.infixOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("中序次数");
        //当前节点
        if (this.no == no) {
            return this;
        }
        //右子节点
        if (this.right != null) {
            resNode = this.right.infixOrderSearch(no);
        }
        return resNode;
    }
    
    //后序查找
    public Node postOrderSearch(int no) {
        //左子节点
        Node resNode = null;
        if (this.left != null) {
            resNode = this.left.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右子节点
        if (this.right != null) {
            resNode = this.right.postOrderSearch(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("后序次数");
        //当前节点
        if (this.no == no) {
            return this;
        }
        return resNode;
    }
}