精华内容
下载资源
问答
  • 二叉树基本操作

    2021-04-05 16:56:52
    二叉树基本操作二叉树的遍历前序遍历中序遍历后序遍历层序遍历获取二叉树元素个数获取二叉树叶子节点个数获取二叉树第K层元素个数获取二叉树高度/深度查找二叉树中指定的元素判断两颗二叉树是否相同 二叉树的遍历 ...

    二叉树的遍历

    前序遍历

        前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子
    

    树。

    //这里的访问就是打印
    public static void perOrder(Node root) {
            if (root == null) {
                return;
            }
            System.out.println(root.val);
            //递归遍历左子树
            perOrder(root.left);
            //递归遍历右子树
            perOrder(root.right);
    
        }
    

    中序遍历

    中序遍历的访问顺序是:根节点- ->根的左子树- ->根的右子树

    public static void inOrder(Node root) {
            if (root == null) {
                return;
            }
            inOrder(root.left);
            System.out.println(root.val);
            inOrder(root.right);
    
        }
    

    后序遍历

    根的左子树 - ->根的右子树 - ->根节点

    public static void postOrder(Node root) {
            if (root == null) {
                return;
            }
            postOrder(root.left);
            postOrder(root.right);
            System.out.println(root.val);
        }
    

    层序遍历

    设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节
    点,然后从左到右访问第2层上的节点,接着是第三层的节点,以此类推,自上而下,自左至右逐层访问
    树的结点的过程就是层序遍历

    public static void levelOrder(TreeNode root) {
            if (root == null) {
                return;
            }
            Queue<TreeNode> queue = new LinkedList<>();
            queue.offer(root);
            while (true) {
                TreeNode cur = queue.poll();
                if (cur == null) {
                    break;
                }
                System.out.println(cur.val);
                if (cur.left != null) {
                    queue.offer(cur.left);
    
                    if (cur.right != null) {
                        queue.offer(cur.right);
                    }
                }
            }
        }
    

    获取二叉树元素个数

    public static int count = 0;
        public static int lenght(Node root) {
    
            if (root == null) {
                return 0;
            }
            return lenght(root.left) + lenght(root.right) + 1;
        }
    

    获取二叉树叶子节点个数

    public static int  getLeafsize(TreeNode root) {
            if (root == null) {
                return 0;
            }
            if (root.left == null && root.right == null) {
                return  1;
            }
            return getLeafsize(root.left) + getLeafsize(root.right);
        }
    

    获取二叉树第K层元素个数

    public static int  getKLevelSize(TreeNode root,int k) {
            if (root == null || k < 1) {
                return 0;
            }
            if (k == 1) {
                return 1;
            }
            return getKLevelSize(root.left, k - 1) + getKLevelSize(root.right, k - 1);
        }
    

    获取二叉树高度/深度

    public static int getHight(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int leftHight = getHight(root.left);
            int rightHight = getHight(root.right);
            return 1 + (leftHight > rightHight ? leftHight : rightHight);
        }
    

    查找二叉树中指定的元素

    public static Node Find(Node root, String toFind) {
            if (root == null) {
                return null;
            }
            if (root.val.equals(toFind)) {
                return root;
            }
            Node result = Find(root.left, toFind);
            if (result != null) {
                return result;
            }
            return Find(root.right, toFind);
        }
    

    判断两颗二叉树是否相同

    public static boolean isSameTree(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
            if (p == null || q == null) {
                return false;
            }
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 5,296
精华内容 2,118
关键字:

二叉树基本操作