栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构——二叉树

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构——二叉树

目录

1.树的结构

1.1树结构概念

 2.二叉树(重点)

2.1概念

2.2常见的二叉树

2.3二叉树的遍历问题

 2.4二叉树的基本操作

2.5二叉树的基础面试题


1.树的结构

1.1树结构概念

树是一种非线性的数据结构,它是由n(n>=0)个有限节点组成的一个具有层次关系的集合。把它叫做树是因为它看起来像一颗倒挂的树,也就是说它是根朝上,而叶子朝下的。树天然具有高效的查找与搜索语义!

 

为什么会存在树结构?

 

1.2关于树的基础概念

 

 2.二叉树(重点)

2.1概念

一颗二叉树是节点的一个有限集合,该集合或者为空,或者是由一个根节点加上两颗别称为左子树和右子树的二叉树组成。通俗来讲,就是树中节点最大的度为2。

二叉树的常用性质:

2.2常见的二叉树

满二叉树与完全二叉树:

 

2.3二叉树的遍历问题

所有二叉树的基础操作,其实所有二叉树的问题的解决思路都是遍历问题的衍生!

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

前序遍历:根左右

 
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        //先输出根节点
        System.out.print(root.val + " ");
        //左子树的输出交给子函数
        preOrder(root.left);
        //右子树的输出交给子函数
        preOrder(root.right);
    }

 

 中序遍历:左根右

 
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        //左子树交给子函数处理
        inOrder(root.left);
        //输出根节点
        System.out.print(root.val + " ");
        //右子树交给子函数处理
        inOrder(root.right);
    }

后序遍历:左右根

  
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        //左子树交给子函数出库
        postOrder(root.left);
        //右子树交给子函数处理
        postOrder(root.right);
        //输出根节点
        System.out.print(root.val + " ");
    }

层序遍历:

 

 

 2.4二叉树的基本操作
package bintree;
//二叉树的结点
class TreeNode{
    //当前节点的值
    E val;
    //左子树的根
    TreeNode left;
    //右子树的根
    TreeNode right;

    public TreeNode(E val) {
        this.val = val;
    }
}

public class MyBinTree {
    public TreeNode root;

    //建立二叉树
    public void build(){
        TreeNode node = new TreeNode<>('A');
        TreeNode node1 = new TreeNode<>('B');
        TreeNode node2 = new TreeNode<>('C');
        TreeNode node3 = new TreeNode<>('D');
        TreeNode node4 = new TreeNode<>('E');
        TreeNode node5 = new TreeNode<>('F');
        TreeNode node6 = new TreeNode<>('G');
        TreeNode node7 = new TreeNode<>('H');
        root =  node;
        node.left = node1;
        node.right = node2;
        node1.left = node3;
        node1.right = node4;
        node4.left = node6;
        node6.right = node7;
        node2.right = node5;
    }

    
    public void preOrder(TreeNode root){
        if (root == null){
            return;
        }
        //先输出根节点
        System.out.print(root.val + " ");
        //左子树的输出交给子函数
        preOrder(root.left);
        //右子树的输出交给子函数
        preOrder(root.right);
    }

    
    public void inOrder(TreeNode root){
        if (root == null){
            return;
        }
        //左子树交给子函数处理
        inOrder(root.left);
        //输出根节点
        System.out.print(root.val + " ");
        //右子树交给子函数处理
        inOrder(root.right);
    }

    
    public void postOrder(TreeNode root){
        if (root == null){
            return;
        }
        //左子树交给子函数出库
        postOrder(root.left);
        //右子树交给子函数处理
        postOrder(root.right);
        //输出根节点
        System.out.print(root.val + " ");
    }

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

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

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

    
    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);
    }

}

2.5二叉树的基础面试题

 

 

 

 

 

   public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        // 边界
        if (root == null && subRoot == null) {
            return true;
        }
        if (root == null || subRoot == null) {
            return false;
        }
        // 恰好root和subRoot就是相同的树 => true
        return isSameTree(root,subRoot) || isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);
    }

    public boolean isSameTree(TreeNode p, TreeNode q) {
        // 1.边界
        if (p == null && q == null) {
            // 都是空树,就认为相同
            return true;
        }
        if (p == null || q == null) {
            // 有一棵树为空,另一棵树不为空
            return false;
        }
        // p和q都不为空,判断一下节点值。子树的判断交给子函数
        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }

 

 

public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }
        // 求左树高度
        int left = height(root.left);
        // 求右树高度
        int right = height(root.right);
        int abs = Math.abs(left - right);
        return abs <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    public int height(TreeNode root) {
        return root == null ? 0 : 1 + Math.max(height(root.left),height(root.right));
    }

 

 

 

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        Deque queue = new LinkedList<>();
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode t1 = queue.poll();
            TreeNode t2 = queue.poll();
            if (t1 == null && t2 == null) {
                continue;
            }
            if (t1 == null || t2 == null) {
                // 找到反例
                return false;
            }
            if (t1.val != t2.val) {
                // 找到反例
                return false;
            }
            // 继续t1.left t2.right入队
            queue.offer(t1.left);
            queue.offer(t2.right);
            // 继续t1.right t2.left
            queue.offer(t1.right);
            queue.offer(t2.left);
        }
        return true;
    }

 

   public boolean isCompleteTree(TreeNode root) {
        Deque queue = new LinkedList<>();
        queue.offer(root);
        // 判断是否是第二阶段
        boolean isSecondStep = false;
        while (!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            if (!isSecondStep) {
                // 在第一阶段中,每个节点都必须存在左右子树
                if (cur.left != null && cur.right != null) {
                    queue.offer(cur.left);
                    queue.offer(cur.right);
                }else if (cur.left != null) {
                    // 此时只有左树没有右树,转阶段
                    isSecondStep = true;
                    queue.offer(cur.left);
                }else if (cur.right != null) {
                    // 只有右树没左树,反例
                    return false;
                }else {
                    // 碰到叶子结点,转阶段
                    isSecondStep = true;
                }
            }else {
                // 此时处在第二阶段,所有节点都必须为叶子结点。
                if (cur.left != null || cur.right != null) {
                    // 不是叶子结点,反例
                    return false;
                }
            }
        }
        return true;
    }

 

   public List preorderTraversal(TreeNode root) {
        List ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Deque stack = new LinkedList<>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            ret.add(cur.val);
            if (cur.right != null) {
                stack.push(cur.right);
            }
            if (cur.left != null) {
                stack.push(cur.left);
            }
        }
        return ret;
    }

 

   public List inorderTraversal(TreeNode root) {
        List ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        Deque stack = new ArrayDeque<>();
        TreeNode cur = root;
        while (cur != null || !stack.isEmpty()) {
            // 先一路向左走到底
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // cur已经为空,弹出栈顶元素,就是第一个左子树为空的结点
            cur = stack.pop();
            ret.add(cur.val);
            // 继续访问右子树
            cur = cur.right;
        }
        return ret;
    }

 

 public List postorderTraversal(TreeNode root) {
        List ret = new ArrayList<>();
        if (root == null) {
            return ret;
        }
        TreeNode cur = root;
        Deque stack = new ArrayDeque<>();
        // 上一个完全处理完毕的节点.
        TreeNode prev = null;
        while (cur != null || ! stack.isEmpty()) {
            // 1.先一路向左走到底
            while (cur != null) {
                stack.push(cur);
                cur = cur.left;
            }
            // 2.查看当前栈顶元素的情况
            cur = stack.pop();
            // 检查右子树的情况
            if (cur.right == null || cur.right == prev) {
                // 此时右子树为空或者右子树已经被处理完毕
                // 此时可以放心访问cur节点-根
                ret.add(cur.val);
                // cur节点就是最新的处理结束的结点
                prev = cur;
                // 继续从栈中取出栈顶元素
                cur = null;
            }else {
                // 此时cur.right != null 且没被访问过,继续访问右子树
                stack.push(cur);
                // 继续访问右子树
                cur = cur.right;
            }
        }
        return ret;
    }

 

 

 

 

   // 最近公共祖先
    private TreeNode lca;
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 从树中每个节点开始遍历找p和q这两个节点
        findNode(root,p,q);
        return lca;
    }

    
    private boolean findNode(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null) {
            return false;
        }
        // 返回1说明,此时从左子树中至少找到了一个节点
        int left = findNode(root.left,p,q) ? 1 : 0;
        // 返回1说明在右子树中也至少找到了节点
        int right = findNode(root.right,p,q) ? 1 : 0;
        // 当前树根就是p或者q的其中一个
        int mid = (root == p || root == q) ? 1 : 0;
        if (left + right + mid  == 2) {
            // 此时p和q出现在以root为根的两个位置,这个root一定是lca!!!
            lca = root;
        }
        // 大于0,说明至少找到一个节点
        return (left + right + mid) > 0;
    }

 

import java.util.*
// 节点类定义
class TreeNode {
    char val;
    TreeNode left;
    TreeNode right;
    public TreeNode(char val) {
        this.val = val;
    }
}


public class Main{
    // 表示当前处理到先序遍历的哪个字符了
    private static int index = 0;
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            // 从外部获取了一个先序遍历的结果集字符串
            // abc##de#g##f###
            String str = scanner.nextLine();
            // 就按照先序遍历的方式还原这个二叉树,返回根节点
            TreeNode root = preOrderBuild(str);
            // 按照中序遍历的方式输出二叉树的节点值
            inOrder(root);
            System.out.println();
            index = 0;
        }
    }

    
    private static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }
        // 先递归左子树
        inOrder(root.left);
        // 根
        System.out.print(root.val + " ");
        // 最后递归访问右子树
        inOrder(root.right);
    }

    
    private static TreeNode preOrderBuild(String str) {
        // 读取一个字符
        // abc##de#g##f###
        char cur = str.charAt(index);
        if (cur == '#') {
            // 空树,无需创建节点
            return null;
        }
        TreeNode root = new TreeNode(cur);
        index ++;
        root.left = preOrderBuild(str);
        index ++;
        root.right = preOrderBuild(str);
        return root;
    }
}

 

 

 

 // 表示当前处理到前序遍历的哪个元素
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeHelper(preorder,inorder,0,inorder.length - 1);
    }

    
    private TreeNode buildTreeHelper(int[] preorder, int[] inorder, int left, int right) {
        // 边界
        if (left > right) {
            // [2,1) => 空区间
            return null;
        }
        if (index == preorder.length) {
            // 前序遍历的元素已经处理完毕,没有新节点
            return null;
        }
        // 从前序遍历中取出当前树的树根节点
        TreeNode root = new TreeNode(preorder[index]);
        index ++;
        int pos = find(root.val,inorder);
        root.left = buildTreeHelper(preorder,inorder,left,pos - 1);
        root.right = buildTreeHelper(preorder,inorder,pos + 1,right);
        return root;
    }

    
    private int find(int val, int[] inorder) {
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == val) {
                return i;
            }
        }
        return -1;
    }

 

 

 

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/930694.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号