关于java:数据结构二叉树

二叉树

二叉树是一种非凡的树，每个节点最多只能有两个子节点。

二叉搜寻树要求：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；它的左、右子树也别离为二叉排序树

查找节点

查找节点从根节点开始遍历查找

1、查找值比以后节点值大，则搜寻右子树；

2、查找值等于以后节点值，进行搜寻（终止条件）；

3、查找值小于以后节点值，则搜寻左子树；

插入节点

要插入节点，必须先找到插入的地位。与查找操作类似，因为二叉搜寻树的特殊性，待插入的节点也须要从根节点开始进行比拟，小于根节点则与根节点左子树比拟，反之则与右子树比拟，直到左子树为空或右子树为空，则插入到相应为空的地位，在比拟的过程中要留神保留父节点的信息 及 待插入的地位是父节点的左子树还是右子树，能力插入到正确的地位

 public boolean insert(int data) {
        count++;
        // 如果第一个节点为空 设置第一个节点
        Node newNode = new Node(data);
        if (root == null) {
            root = newNode;
            return true;
        }
        Node current = root;
        Node parentNode = null;
 
        while (current != null) {
            parentNode = current;
            // 以后值比新插入值大
            if (current.data > data) {
                current = current.leftNode;
                // 若左节点为空 则直接插入即可
                if (current == null) {
                    parentNode.leftNode = newNode;
                    return true;
                }
            } else {
                // 以后值小于新插入值
                current = current.rightNode;
                if (current == null) {
                    parentNode.rightNode = newNode;
                    return true;
                }
            }
        }
        return false;
    }

删除节点

删除节点绝对于查问和删除略微简单点，次要是删除时思考的状况多一点点。

• 删除节点没有子节点
  这种的话就间接删除以后节点就好了，只需将以后节点的父节点指向的节点置为 null 即可

// 以后节点是否为左节点
        boolean isLeftNode = false;

// 1 第一种状况 此节点为叶子节点
        if (current.leftNode == null && current.rightNode == null) {if (current == root) {root = null;} else if (isLeftNode) {
                // 如果要删除的节点为父节点的左节点 把父节点的左节点置为空
                parentNode.leftNode = null;
            } else {parentNode.rightNode = null;}
            return true;
        }

• 删除节点有一个子节点
  删除有一个子节点的节点，咱们只须要将其父节点本来指向该节点的援用，改为指向该节点的子节点即可。

if (current.leftNode == null && current.rightNode != null) {if (root == current) {root = current.rightNode;} else if (isLeftNode) {parentNode.leftNode = current.rightNode;} else {parentNode.rightNode = current.rightNode;}
        } else if (current.leftNode != null && current.rightNode == null) {if (root == current) {root = current.leftNode;} else if (isLeftNode) {parentNode.leftNode = current.leftNode;} else {parentNode.rightNode = current.leftNode;}
        }

• 删除节点有两个子节点
  当删除的节点存在两个子节点，那么删除之后，两个子节点的地位咱们就没方法解决了。既然解决不了，咱们就想到一种方法，用另一个节点来代替被删除的节点，那么用哪一个节点来代替呢？
  这实际上就是要找比删除节点要害值大的节点汇合中最小的一个节点，只有这样代替删除节点后能力满足二叉搜寻树的个性。
  程序找到删除节点的右节点，(留神这里前提是删除节点存在左右两个子节点，如果不存在则是删除状况的后面两种)，而后转到该右节点的左子节点，顺次顺着左子节点找上来，最初一个左子节点即是后继节点；如果该右节点没有左子节点，那么该右节点便是后继节点。
  二叉树

   if(current.leftNode != null && current.rightNode != null){
            // 获取删除节点的后继结点
            Node successor = getSuccessor(current);
            if (root == current) {root = successor;} else if (isLeftNode) {parentNode.leftNode = successor;} else {parentNode.rightNode = successor;}
        }
        return false;
  public Node getSuccessor(Node delNode) {
   
        Node successorParent = delNode;
        Node successor = delNode;
        Node current = delNode.rightNode;
        while (current != null) {
            successorParent = successor;
            successor = current;
            current = current.leftNode;
        }
        if (successor != delNode.rightNode) {
            successorParent.leftNode = successor.rightNode;
            successor.leftNode= delNode.leftNode;
        }
        return successor;
    }
  

前序遍历

前序遍历：首先拜访根结点，而后遍历左子树，最初遍历右子树（根 -> 左 -> 右）

程序：拜访根节点 -> 前序遍历左子树 -> 前序遍历右子树

中序遍历

中序遍历：首先遍历左子树，而后拜访根节点，最初遍历右子树（左 -> 根 -> 右）

程序：中序遍历左子树 -> 拜访根节点 -> 中序遍历右子树

后序遍历

后序遍历：首先遍历左子树，而后遍历右子树，最初拜访根节点（左 -> 右 -> 根）

程序：后序遍历左子树 -> 后序遍历右子树 -> 拜访根节点

层序遍历; 按层从左到右拜访

前序中序后序

前序遍历：根 -> 左 -> 右：12473568
中序遍历：左 -> 根 -> 右：47215386
后序遍历：左 -> 右 -> 根：74258631

重构二叉树

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) {val = x;}
 * }
 */
public class Solution {// 前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列{4,7,2,1,5,3,8,6}
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {

        int len = pre.length;

        TreeNode root = new TreeNode(pre[0]);
        // 阐明只剩下一个了，示意叶子节点, 递归能够退出了
        if (pre.length == 1) {
            root.left = null;
            root.right = null;
            return root;
        }

        // 两头值 在{4,7,2,1,5,3,8,6} 这个两头值第一次应该是 3
        int flag = 0;
        for (int i = 0; i < len; i++) {
            // 在中序中找到
            if (pre[0] == in[i]) {
                flag = i;
                break;
            }
        }
        if (flag > 0) {
            // 左子树的先序
            int[] leftPre = new int[flag];
            // 左子树的中序
            int[] leftIn = new int[flag];
            for (int j = 0; j < flag; j++) {leftPre[j] = pre[j + 1];
            }
            for (int j = 0; j < flag; j++) {leftIn[j] = in[j];
            }
            // 左子树递归
            root.left = reConstructBinaryTree(leftPre, leftIn);
        } else {root.left = null;}
        if (pre.length - flag - 1 > 0) {
            // 右子树的先序, 长度为 总 - 根 - 左子树
            int[] rightPre = new int[pre.length - 1 - flag];
            // 右子树的中序
            int[] rightIn = new int[pre.length - 1 - flag];

            for (int j = flag + 1; j < len; j++) {
                // 右子树中序，为什么要 j -flag- 1 呢 因为我的 rightIn 要从 0 开始 而 j 是 k + 1 开始的，所以很难堪，只能用 j -flag-1
                rightIn[j - flag - 1] = in[j];

                rightPre[j - flag - 1] = pre[j];
            }

            root.right = reConstructBinaryTree(rightPre, rightIn);
        } else {root.right = null;}

        return root;

    }
 
}