AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

【数据结构】二叉树重点知识和OJ题汇总（附有代码）

2023-08-14 100
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】二叉树重点知识和OJ题汇总（附有代码）

思维导图：

1.树的概念：

  1. 树是一种非线性的数据结构，由递归定义出来的。根节点R在上，其他节点在下；树形结构中子树不能有交集，否则不能称为树形结构。
  2. 树的几种重要概念，参照上图：

1.节点的度：一个节点含有子树的个数，例如：c的度就是3

2.树的度：一棵树中所有节点的度的最大值，例如：上图中树的度就是3

3.叶子节点或终端节点：一个节点没有任何子树，例如：j、k、e、f、g、m、n、i

4.双亲节点或父节点：一个节点含有子节点，例如：r是a、b、c的父节点

5.孩子节点或子节点：例如：a、b、c是r的孩子节点

6.根节点：一棵树中，没有双亲节点的节点，例如：r就是根节点

7.节点的层次：从根开始算，r为第1层，a、b、c为第2层

8.树的高度或深度：树中节点的最大层次，例如：上图中树的最大高度为4

2.二叉树：

  1. 二叉树是由1个根节点加上左子树和右子树组成的，每个根节点可以有2棵子树、1棵子树也可以没有子树。因此：二叉树不会存在度大于2的节点；二叉树的子树有左右之分，不可以颠倒；一颗二叉树的左子树和右子树也必须是二叉树。
  2. 有2种特殊的二叉树分别为满二叉树和完全二叉树。满二叉树是1棵二叉树上的每层节点数达到最大值，如果1棵二叉树的层数为n并且节点总数为 (2^n) - 1；则这棵树就是满二叉树。
  3. 二叉树的性质：

1.规定根节点的层数为1，则1棵非空二叉树的第i层上最多有2^(i-1)个节点

2.规定根节点的二叉树高度为1，则高度为k的二叉树最大节点数是2^k - 1

3.度为0的节点个数比度为2的个数多1个

4.有n个节点的完全二叉树的深度为log以2为底的(n+1)向上取整


  1. 二叉树的存储是通过一个一个的节点引用起来的，常用的表示方式有孩子表示法和孩子双亲表示法。二叉树的存储分为顺序存储和类似于链表的链式存储，注意类似于链表不是链表。

 

3.二叉树的遍历：

  1. 二叉树的遍历是二叉树最重要的基本功能。
  2. 前序遍历：先访问根节点—>左子树—>右子树

参照上图前序遍历：r a d e c g i


  1. 中序遍历：先访问左子树—>根节点—>右子树

参照上图中序遍历：d a e r g c i


  1. 后序遍历：先访问左子树—>右子树—>根节点

参照上图后序遍历：d e a g i c r

  1. 层序遍历：从左到右遍历每一层

参照上图层序遍历：r a c d e g i

  1. 根据前序遍历和后序遍历不能创建出一个二叉树，前序和后序只能确定根。
  2. 前、中、后、层+序遍历的代码实现：
public class BinaryTree {
    class TreeNode{
        //孩子表示法
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public TreeNode root;
    //前序遍历1
    public void preOrder1(TreeNode root){
        if(root == null) return;
        System.out.print(root.val+" ");
        preOrder1(root.left);
        preOrder1(root.right);
    }
    //前序遍历2：有返回值类型，遍历思路
    class Solution{
        //list必须定义在外面，否则每次递归都会创建1个list
        List<Character> list = new ArrayList<>();
        public List<Character> preOrder2(TreeNode root){
            if(root == null) return list;
            list.add(root.val);
            preOrder2(root.left);
            preOrder2(root.right);
            return list;
        }
    }
    //前序遍历3：有返回值，子问题思路
    public List<Character> preOrder3(TreeNode root){
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        list.add(root.val);
        List<Character> leftTree = preOrder3(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = preOrder3(root.right);
        list.addAll(rightTree);
        return list;
    }
    //中序遍历1
    public void inOrder(TreeNode root){
        if(root == null) return;
        inOrder(root.left);
        System.out.print(root.val+" ");
        inOrder(root.right);
    }
    //中序遍历2：有返回值，子问题思路
    public List<Character> inOrder2(TreeNode root){
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        List<Character> leftTree = inOrder2(root.left);
        list.addAll(leftTree);
        list.add(root.val);
        List<Character> rightTree = inOrder2(root.right);
        list.addAll(rightTree);
        return list;
    }
    //后序遍历1
    public void postOrder(TreeNode root){
        if(root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val+" ");
    }
    //后序遍历2：有返回值，子问题思路
    public List<Character> postOrder2(TreeNode root){
        List<Character> list = new ArrayList<>();
        if(root == null) return list;
        List<Character> leftTree = postOrder(root.left);
        list.addAll(leftTree);
        List<Character> rightTree = postOrder2(root.right);
        list.addAll(rightTree);
        list.add(root.val);
        return list;
    }
    //层序遍历1:使用到了队列
    public void levelOrder(TreeNode root){
        if(root == null) return;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.print(cur+" ");
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
    }
}

 

4.二叉树的模拟实现：

获取树中节点得个数

获取叶子节点的个数

获取第k层节点的个数

获取二叉树的高度

检测值value是否存在

代码实现如下：

public class BinaryTree {
    class TreeNode{
        //孩子表示法
        public char val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode(char val){
            this.val = val;
        }
    }
    public TreeNode root;
    //获取树中节点的个数1:子问题思路
    public int size(TreeNode root){
        if(root == null) return 0;
        return size(root.left)+size(root.right)+1;
    }
    //获取树中节点的个数2:遍历思路
    public static int nodeSize;
    public void size2(TreeNode root){
        if(root == null) return;
        nodeSize++;
        size2(root.left);
        size2(root.right);
    }
    //获取叶子节点的个数1：子问题思路
    public int getLeafNodeCount(TreeNode root){
        if(root == null) return 0;
        if(root.left == null && root.right==null){
            return 1;
        }
        return getLeafNodeCount(root.left)+
                    getLeafNodeCount(root.right);
    }
    //获取叶子节点的个数2：遍历思路
    public static int leafSize;
    public void getLeafNodeCount2(TreeNode root){
        if(root == null) return;
        if(root.left == null && root.right == null){
            leafSize++;
        }
        getLeafNodeCount2(root.left);
        getLeafNodeCount2(root.right);
    }
    //获取第k层节点的个数：子问题思路
    public int getKLevelNodeCount(TreeNode root,int k){
        if(root == null) return 0;
        if(k == 1) return 1;
        //对k操作不会影响右树
        return getKLevelNodeCount(root.left,k-1)
                    +getKLevelNodeCount(root.right,k-1);
    }
    //获取二叉树的高度
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight?
                            leftHeight+1 : rightHeight+1);
    }
    //检测value是否存在
    public TreeNode find(TreeNode root,int value){
        if(root == null) return null;
        if(root.val == value){
            return root;
        }
        TreeNode ret1 = find(root.left,value);
        if(ret1 != null) return ret1;
        TreeNode ret2 = find(root.right,value);
        if(ret2 != null) return ret2;
        return null;
    }
    //判断一棵树是不是完全二叉树
    public boolean isCompleteTree(TreeNode root){
        if(root == null) return true;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            System.out.println(cur+" ");
            if(cur != null){
                queue.offer(cur.left);
                queue.offer(cur.right);
            }else{
                break;
            }
        }
        while(!queue.isEmpty()){
            TreeNode cur = queue.peek();
            if(cur != null){
                return false;
            }else{
                queue.poll();
            }
        }
        return true;
    }
}

5.二叉树的OJ题：

1.检查俩颗二叉树是否完全相同，时间复杂度为O(min(m,n))

//检查俩颗树是否完全相同
public boolean isSameTree(TreeNode p,TreeNode q){
    if(p == null &&q != null || q == null && p != null) return false;
    if(p == null && q == null) return true;
    if(p.val == q.val) return true;
    return isSameTree(p.left,q.left) &&
            isSameTree(p.right,q.right);
}

2.判断一棵树是不是另外一棵树的子树，时间复杂度为O(m*n)

//判断一棵树是不是另外一棵树的子树
public boolean isSubTree(TreeNode root,TreeNode subRoot){
    if(root == null || subRoot == null)  return false;
    if(isSameTree(root,subRoot)) return true;
    if(isSameTree(root.left,subRoot)) return true;
    if(isSameTree(root.right,subRoot)) return true;
    return false;
}

3.二叉树的最大深度

//得到一棵树的高度
private int getHeight(TreeNode root) {
    if(root == null) return 0;
    int leftTree = getHeight(root.left);
    int rightTree = getHeight(root.right);
    return leftTree > rightTree?
                leftTree+1 : rightTree+1;
}

4.判断一棵树是不是平衡二叉树

//得到一棵树的高度
private int getHeight(TreeNode root) {
    if(root == null) return 0;
    int leftTree = getHeight(root.left);
    int rightTree = getHeight(root.right);
    return leftTree > rightTree?
                leftTree+1 : rightTree+1;
}
//1.判断一棵树是否是平衡二叉树,时间复杂度为O(n^2)
public boolean isBalanced(TreeNode root){
    if(root == null){
        return true;
    }
    int leftTree = getHeight(root.left);
    int rightTree = getHeight(root.right);
    return Math.abs(leftTree-rightTree)<=1
            && isBalanced(root.left)
            && isBalanced(root.right);
}
//2.判断一棵树是否是平衡二叉树，时间复杂度为O(n)
public boolean isBalanced2(TreeNode root){
    if(root == null) return true;
    return maxDepth(root)>=0;
}
private int maxDepth(TreeNode root) {
    if(root == null) return 0;
    int leftTree = maxDepth(root.left);
    int rightTree = maxDepth(root.right);
    if(leftTree >= 0 && rightTree >= 0 && Math.abs(leftTree-rightTree) <= 1){
        return Math.max(leftTree,rightTree)+1;
    }else{
        return -1;
    }
}

5.构建一颗二叉树

//构建一颗二叉树
public static int i;
public TreeNode createTree(String s){
    TreeNode root = null;
    if(s.charAt(i) != '#'){
        root = new TreeNode(s.charAt(i));
        i++;
        root.left = createTree(s);
        root.right = createTree(s);
    }else{
        i++;
    }
    return root;
}

6.二叉树的分层遍历

//二叉树的分层遍历
public List<List<Character>> levelOrder(TreeNode root){
    List<List<Character>> ret = new ArrayList<>();
    if(root == null) return ret;
    Queue<TreeNode> queue = new LinkedList<>();
    queue.offer(root);
    while(!queue.isEmpty()){
        int size = queue.size();
        List<Character> row = new ArrayList<>();
        while(size > 0){
            TreeNode cur = queue.poll();
            size--;
            row.add(cur.val);
            if(cur.left != null){
                queue.offer(cur.left);
            }
            if(cur.right != null){
                queue.offer(cur.right);
            }
        }
        ret.add(row);
    }
    return ret;
}

7.找到俩个二叉树的公共祖先

//找俩个节点的公共祖先,方法1
public TreeNode lowestAncestor(TreeNode root,TreeNode p,TreeNode q){
    if(root == null) return null;
    if(root == p || root == q) return root;
    TreeNode retleft = lowestAncestor(root.left,p,q);
    TreeNode retright = lowestAncestor(root.right,p,q);
    if(retleft != null && retright != null){
        return root;
    } else if (retleft != null) {
        return retleft;
    }else{
        return retright;
    }
}
//找俩个节点的公共祖先,方法2:找到根节点到指定节点之间的所有节点，存到stack中
private boolean getPath(TreeNode root, TreeNode node, Stack<TreeNode> stack){
    if(root == null || node == null) return false;
    stack.push(root);
    if(root == node) return true;
    boolean ret1 = getPath(root.left,node,stack);
    if(ret1 == true) return true;
    boolean ret2 = getPath(root.right,node,stack);
    if(ret2 == true) return true;
    stack.pop();
    return false;
}
public TreeNode lowestAncestor2(TreeNode root,TreeNode p,TreeNode q){
    if(root == null || p == null || q == null) return null;
    Stack<TreeNode> stack1 = new Stack<>();
    getPath(root,p,stack1);
    Stack<TreeNode> stack2 = new Stack<>();
    getPath(root,q,stack2);
    int size1 = stack1.size();
    int size2 = stack2.size();
    if(size1 > size2){
        int tmp = size1 - size2;
        while(tmp != 0){
            stack1.pop();
            tmp--;
        }
    }else{
        int tmp = size2 - size1;
        while(tmp != 0){
            stack2.pop();
            tmp--;
    }
    while(! stack1.empty() && !stack2.empty()){
        if(stack1.peek() == stack2.peek()){
            return stack1.peek();
        }else{
            stack1.pop();
            stack2.pop();
        }
    }
    return null;
}

8.将二叉搜索树转换成排序双向链表

//二叉搜索树转换成排序双向链表
public TreeNode prev = null;
private void ConvertChild(TreeNode root){
    if(root == null) return ;
    ConvertChild(root.left);
    root.left = prev;
    if(prev != null){
        prev.right = root;
    }
    prev = root;
    ConvertChild(root.right);
}
public TreeNode Convert(TreeNode pRootOfTree){
    if(pRootOfTree == null) return null;
    ConvertChild(pRootOfTree);
    TreeNode head = pRootOfTree;
    while(head.left != null){
        head = head.left;
    }
    return head;
}

9.根据前序和后序遍历构造二叉树

//根据前序和中序遍历构造二叉树
public int preindex = 0;
private TreeNode buildTreeChild(int[] preorder,int[] inorder,int inbegin,int inend){
    //没有了左树或没有右树
    if(inbegin > inend) return null;
    TreeNode root = new TreeNode(preorder[preindex]);
    //找到当前根节点在中序遍历中的位置
    int rootIndex = findInorderIndex(inorder,preorder[preindex],inbegin,inend);
    preindex++;
    root.left = buildTreeChild(preorder,inorder,inbegin,rootIndex-1);
    root.right = buildTreeChild(preorder,inorder,rootIndex+1,inend);
    return root;
}
private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){
    for (int i = inbegin; i <= inend; i++) {
        if (inorder[i] == val){
            return i;
        }
    }
    return -1;
}
public TreeNode buildTree(int[] preorder,int[] inorder){
    return buildTreeChild(preorder,inorder,0,inorder.length-1);
}

10.根据中序和后序遍历构造二叉树

//根据中序和后序遍历构造二叉树
public int postindex = 0;
private TreeNode buildTreeChild(int[] postorder,int[] inorder,int inbegin,int inend){
    //没有了左树或没有右树
    if(inbegin > inend) return null;
    TreeNode root = new TreeNode(postorder[postindex]);
    //找到当前根节点在中序遍历中的位置
    int rootIndex = findInorderIndex(inorder,postorder[postindex],inbegin,inend);
    postindex--;
    root.right = buildTreeChild(postorder,inorder,rootIndex+1,inend);
    root.left = buildTreeChild(postorder,inorder,inbegin,rootIndex-1);
    return root;
}
private int findInorderIndex(int[] inorder,int val,int inbegin,int inend){
    for (int i = inbegin; i <= inend; i++) {
        if (inorder[i] == val){
            return i;
        }
    }
    return -1;
}
public TreeNode buildTree(int[] postorder,int[] inorder){
    postindex = postorder.length-1;
    return buildTreeChild(postorder,inorder,0,inorder.length-1);
}

11.二叉树创建字符串

//二叉树创建字符串
public String tree2str(TreeNode root) {
    StringBuilder sb = new StringBuilder();
    tree2strChild(root,sb);
    return sb.toString();
}
private void tree2strChild(TreeNode t,StringBuilder sb) {
    if(t == null) return ;
    sb.append(t.val);
    if(t.left != null) {
        sb.append("(");
        tree2strChild(t.left,sb);
        sb.append(")");
    }else {
        if(t.right == null) {
            return;
        }else{
            sb.append("()");
        }
    }
    if(t.right == null) {
        return;
    }else{
        sb.append("(");
        tree2strChild(t.right,sb);
        sb.append(")");
    }
}

12.非递归实现前序遍历

//非递归实现前序遍历
public  void preorderTraversalNor(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            System.out.print(cur.val + " ");
            cur = cur.left;
        }
        TreeNode top = stack.pop();
        cur = top.right;
    }
}

13.非递归实现中序遍历

//非递归实现中序遍历
public void inorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.pop();
        System.out.print(top.val + " ");
        cur = top.right;
    }
}

14.非递归实现后序遍历

//非递归实现后序遍历
public void postorderTraversal(TreeNode root) {
    Stack<TreeNode> stack = new Stack<>();
    TreeNode prev = null;
    TreeNode cur = root;
    while (cur != null || !stack.empty()) {
        while (cur != null) {
            stack.push(cur);
            cur = cur.left;
        }
        TreeNode top = stack.peek();
        //top.right 如果已经被访问了 也要弹出top所指向的节点
        if (top.right == null || top.right == prev) {
            stack.pop();
            System.out.print(top.val + " ");
            prev = top;
        } else {
            cur = top.right;
        }
    }
}

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

如果对您有帮助的话，

不要忘记点赞+关注哦，蟹蟹

文章标签：
存储
Java
关键词：
数据结构代码
数据结构二叉树
数据结构oj
数据结构二叉树oj
数据结构二叉树代码
珠江上上上
目录
相关文章
小强在此
|
12天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
21 7
java冯坚持
|
11天前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
13 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
11天前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
14 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
GuGuStudy
|
12天前
|
Java
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（二）
GuGuStudy
23 1
GuGuStudy
|
12天前
|
算法 Java C语言
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
【用Java学习数据结构系列】震惊，二叉树原来是要这么学习的（一）
GuGuStudy
20 1
Dylaniou
|
8天前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16，负载因子为0.75。当存储元素超过容量 * 负载因子时，会进行扩容。HashMap 使用哈希算法计算键的索引位置，通过链表或红黑树解决哈希冲突，确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
Dylaniou
18 0
阿客不是客
|
11天前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
15 0
java冯坚持
|
11天前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
15 0
java冯坚持
|
11天前
|
算法 程序员 索引
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
栈的基本概念、应用场景以及如何使用数组和单链表模拟栈，并展示了如何利用栈和中缀表达式实现一个综合计算器。
java冯坚持
16 1
数据结构与算法学习七：栈、数组模拟栈、单链表模拟栈、栈应用实例 实现 综合计算器
禁默
|
11天前
初步认识栈和队列
初步认识栈和队列
禁默
35 10