Java实现数据结构——二叉树_满二叉树按第一层为1,二层2,3,第三层4,5,6,7用java实现

目录

树

引言

关于树的基础概念

二叉树

二叉树的性质

关于完全二叉树的编号问题

二分搜索树 (BST)及其他二叉树

二叉树的遍历问题

二叉树的基本操作

二叉树的建立，前、中、后序遍历

统计二叉树节点个数

统计叶子结点的个数

统计第k层节点个数

求二叉树的高度

判断二叉树中是否包含指定值val

借助队列，实现二叉树的层序遍历

---

树

引言

为什么会存在树结构？

树：高效的查找与搜索的语义。

企业中员工的分类就是一个“树”结构，若是一个线性结构，所有人都在一个“目录”里，比如当前公司中一共有300号员工，要找到一个特定的员工最坏情况下得找300次，O(n)。现在是个树结构，按照员工的职级进行分类，当前300个员工一共分为四级，搜索一个特定员工只需要4次即可找到，O(logn)——树的深度。

---

操作系统OS的文件系统就是基于树结构进行文件管理的，若当前OS中所有文件都放在一个“目录”下，若当前操作系统有1亿个文件，最坏情况遍历1亿次才能找到特定元素。OS分为多级目录，我们只需要logN级别的查找次数。

关于树的基础概念

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

特点：
1. 有一个特殊的节点，称为根节点，根节点没有前驱节点。
2. 除根节点外，其余节点被分成M(M > 0)个互不相交的子集，彼此之间不能相交，若相交就不是树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继。

3. 树中，边的个数x，节点的个数n，x = n - 1（每个节点都有一个父节点，只有根节点没有父节点）。
4. 树是递归定义的。

5. 节点和树的"度”。
节点的度：该节点中包含的子树个数称为该节点的度。

树的度：树中最大的节点的度就称为树的度。

上图中

5. 叶子节点：度为0的节点，M、J、K都没有子树，都是叶子节点。

非叶子节点：度不为0的节点。还存在子树，D、I都是非叶子节点。
6. 根节点：没有父节点的结点，树中有且只有一个，D就是根节点

7. 节点的层次(高度)：从根节点开始计算，根节点为第一层，l、J、K就是第二层，M就是第三层。
树的高度：当前树中节点层次最大的即为树的高度，3。

---

树与非树

二叉树

树中节点最大的度为2的树，称之为二叉树。

二叉树中，一个节点最多有两棵子树，二叉树节点的度<=2；子树有左右之分，左右的顺序不能颠倒。

二叉树的性质

1. 在深度为k的二叉树中，最多存在2^k-1个节点。
2. 在第k层，该层最多有2^(k-1)个节点。
3. 由于任意二叉树都满足节点个数n和边长x具备：x = n - 1的关系。
可以推出——>在二叉树中 度为0的结点 和 度为2的结点 有 n0 = n2 + 1 的关系。

推导：

---

满二叉树：在该二叉树中，每一层的节点个数都是最大值，每一层节点个数都是满的。满二叉树就是一颗特殊的完全二叉树。

完全二叉树：

1. 完全二叉树的结点编号和满二叉树完全一致。

2. 完全二叉树只可能最深的一层结点没有满，没有满的这一层，结点都是靠左排列，其余层都是满的。

3. 在完全二叉树中不存在只有右子树而没有左子树的结点。

4. 在完全二叉树中，若存在度为1的节点，这个节点必然只有左树没有右树而且这个节点有且只有个1个。

关于完全二叉树的编号问题

1. 若根节点从1开始编号

若任意—个节点x，既存在子树也有父节点，则该节点的父节点编号为x / 2，
左子树的编号为2x，右子树的编号为2x + 1。

2. 若根节点从1开始编号

若任意—个节点x，既存在子树也有父节点，则该节点的父节点编号为(x - 1) / 2，
左子树的编号为2x + 1，右子树的编号为2x + 2。

二分搜索树 (BST)及其他二叉树

二分搜索树（BST）：节点的值之间有一个大小关系，左子树节点值 < 根节点值 < 右子树节点值。

平衡二叉树：该树中任意一个节点的左右子树高度差<= 1AVL，严格平衡BST。
RBTree（红黑树）："黑节点"严格平衡的BST。

二叉树的遍历问题

二叉树的遍历问题：所有二叉树的基础操作，所有二叉树问题的解决思路都是遍历问题的衍生。

遍历：按照一定的顺序访问这个集合的所有元素，做到不重复，不遗漏。

---

4种遍历方式：前序遍历、中序遍历、后序遍历（深度优先遍历DFS），层序遍历（广度优先遍历BFS）。

前序遍历：先访问根节点，然后递归访问左子树，再递归访问右子树。

中序遍历：先递归访问左子树，然后访问根节点，最后递归访问右子树。

后序遍历：先递归访问左子树，然后递归访问右子树，最后访问根节点。

第3次走到根节点才能“访问”。

将后序遍历的结果集reverse得到一个先序遍历的镜像结果集——“根右左”。

层序遍历：将二叉树一层层的从上到下、从左到右访问。

二叉树的基本操作

二叉树的建立，前、中、后序遍历

package bintree;
 
/**
 * 二叉树的基本操作
 */
class TreeNode<E> {
    //当前节点的值
    E val;
    //左子树的根
    TreeNode<E> left;
    //右子树的根
    TreeNode<E> right;
 
    public TreeNode(E val) {
        this.val = val;
    }
}
 
public class MyBinTree<E> {
    public TreeNode<Character> root;
 
    //建立一个测试二叉树
    public void build() {
        TreeNode<Character> node = new TreeNode<>('A');
        TreeNode<Character> node1 = new TreeNode<>('B');
        TreeNode<Character> node2 = new TreeNode<>('C');
        TreeNode<Character> node3 = new TreeNode<>('D');
        TreeNode<Character> node4 = new TreeNode<>('E');
        TreeNode<Character> node5 = new TreeNode<>('F');
        TreeNode<Character> node6 = new TreeNode<>('G');
        TreeNode<Character> node7 = new TreeNode<>('H');
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node4.left = node6;
        node6.right = node7;
        node2.right = node5;
        root = node;
    }
 
    /**
     * 传入一棵二叉树的根节点root，就能按照前序遍历 根左右的方式进行输出
     */
    public void preOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //根
        System.out.print(root.val + " ");
        //左子树的输出交给子函数
        preOrder(root.left);
        //右子树的输出交给子函数
        preOrder(root.right);
    }
 
    /**
     * 传入一棵二叉树的根节点root，就能按照中序遍历 左根右的方式进行输出
     */
    public void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //左子树的输出交给子函数
        inOrder(root.left);
        //打印根
        System.out.print(root.val + " ");
        //打印右子树
        inOrder(root.right);
    }
 
    /**
     * 传入一棵二叉树的根节点root，就能按照后序遍历 左右根的方式进行输出
     */
    public void postOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        //左子树的输出交给子函数
        postOrder(root.left);
        //右子树的输出交给子函数
        postOrder(root.right);
        //根
        System.out.print(root.val + " ");
    }
}

package bintree;
/**
 * 测试类
 */
public class TreeTest {
    public static void main(String[] args) {
        MyBinTree binTree = new MyBinTree();
        binTree.build();
        System.out.println("前序遍历结果为：");
        binTree.preOrder(binTree.root);
        System.out.println();
        System.out.println("中序遍历结果为：");
        binTree.inOrder(binTree.root);
        System.out.println();
        System.out.println("后序遍历结果为：");
        binTree.postOrder(binTree.root);
    }
}

统计二叉树节点个数

    /**
     * 统计二叉树节点个数
     * 传入一棵以root为根的二叉树，就能求出节点个数为多少
     */
    public int getNodes(TreeNode root) {
        //第一种方法
//        if (root == null) {
//            return 0;
//        }
//        //根节点至少存在1
//        //总节点数 = 根 + 左子树 +右子树
//        return 1 + getNodes(root.left) + getNodes(root.right);
        //第二种方法
        return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);
    }

---

统计叶子结点的个数

1. 递归写法

    /**
     * 传入一颗以root为根的树，就能求出叶子结点的个数
     */
    public int getLeafNodes(TreeNode root) {
        // 1.边界
        if (root == null) {
            return 0;
        }
//        if (root.left == null && root.right == null) {
        if ((root.left = root.right) == null) {
            //只有叶子节点
            return 1;
        }
        // 此时root不为空，也有子树，总叶子结点个数 = 左树中的叶子结点个数 + 右树中的叶子结点个数
        return getLeafNodes(root.left) + getLeafNodes(root.right);
    }

2. 层序遍历统计节点

    /**
     * 使用层序遍历统计一颗二叉树的结点个数
     */
    public int getNodesNonRecursion(TreeNode<E> root) {
        if (root == null) {
            return 0;
        }
        int size = 0;
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode<E> node = queue.poll();
            size++;
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        return size;
    }

---

统计第k层节点个数

    /**
     * 传入一颗以root为根的二叉树，就能求出第k层的节点个数 k <= height(root)
     */
    public int getKLevelNodes(TreeNode<E> root, int k) {
        // 1.边界条件
        if (root == null || k <= 0) {
            return 0;
        }
        if (k == 1) {
            return 1;
        }
        // 求以root为根的第k层结点个数 = 以root.left为根的第k - 1层结点个数 + 以root.right为根的第k - 1层结点个数
        return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);
    }

---

求二叉树的高度

    /**
     * 传入一颗以root为根的二叉树，就能求出该树的高度是多少
     */
    public int height(TreeNode<E> root) {
//        if (root == null) {
//            return 0;
//        }
//        return 1 + Math.max(height(root.left), height(root.right));
        return root == null ? 0 : 1 + Math.max(height(root.left), height(root.right));
    }

---

判断二叉树中是否包含指定值val

    /**
     * 判断以root为根的二叉树中是否包含指定值val
     */
    public boolean contains(TreeNode root,E val) {
        if (root == null) {
            return false;
        }
        if (root.val.equals(val)) {
            return true;
        }
        return contains(root.left,val)||contains(root.right,val);
    }

---

借助队列，实现二叉树的层序遍历

    /**
     * 借助队列，实现二叉树的层序遍历
     */
    public void levelOrder(TreeNode<E> root) {
        Deque<TreeNode<E>> queue = new LinkedList<>();
        queue.offer(root);
        //循环终止条件 队列为空
        while (!queue.isEmpty()) {
            //
            int n = queue.size();
            for (int i = 0; i < n; i++) {
                TreeNode<E> node = queue.poll();
                System.out.print(node.val + " ");
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
    }