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

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

2023-08-14 103
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 【数据结构】二叉树重点知识和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
数据结构二叉树代码
珠江上上上
目录
相关文章
ephemerals__
|
4天前
|
C语言
【数据结构】二叉树（c语言）（附源码）
本文介绍了如何使用链式结构实现二叉树的基本功能，包括前序、中序、后序和层序遍历，统计节点个数和树的高度，查找节点，判断是否为完全二叉树，以及销毁二叉树。通过手动创建一棵二叉树，详细讲解了每个功能的实现方法和代码示例，帮助读者深入理解递归和数据结构的应用。
ephemerals__
32 8
东方睿赢
|
14天前
|
存储 Java 开发者
Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效
【10月更文挑战第19天】在软件开发中，随着项目复杂度的增加，数据结构的组织和管理变得至关重要。Java中的Map接口提供了一种优雅的方式来管理数据结构，使代码更加清晰、高效。本文通过在线购物平台的案例，展示了Map在商品管理、用户管理和订单管理中的具体应用，帮助开发者告别混乱，提升代码质量。
东方睿赢
24 1
小强在此
|
29天前
|
存储 Java
数据结构第三篇【链表的相关知识点一及在线OJ习题】
数据结构第三篇【链表的相关知识点一及在线OJ习题】
小强在此
24 7
java冯坚持
|
27天前
|
存储 算法 关系型数据库
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
这篇文章主要介绍了多路查找树的基本概念，包括二叉树的局限性、多叉树的优化、B树及其变体（如2-3树、B+树、B*树）的特点和应用，旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
java冯坚持
16 0
数据结构与算法学习二一：多路查找树、二叉树与B树、2-3树、B+树、B*树。（本章为了解基本知识即可，不做代码学习）
java冯坚持
|
27天前
|
存储 算法 搜索推荐
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
java冯坚持
17 0
数据结构与算法学习十七：顺序储存二叉树、线索化二叉树
Dylaniou
|
24天前
|
存储 算法 索引
HashMap底层数据结构及其增put删remove查get方法的代码实现原理
HashMap 是基于数组 + 链表 + 红黑树实现的高效键值对存储结构。默认初始容量为16，负载因子为0.75。当存储元素超过容量 * 负载因子时，会进行扩容。HashMap 使用哈希算法计算键的索引位置，通过链表或红黑树解决哈希冲突，确保高效存取。插入、获取和删除操作的时间复杂度接近 O(1)。
Dylaniou
26 0
阿客不是客
|
27天前
|
存储 算法
探索数据结构：分支的世界之二叉树与堆
探索数据结构：分支的世界之二叉树与堆
阿客不是客
18 0
java冯坚持
|
27天前
|
存储 算法
数据结构与算法学习十六：树的知识、二叉树、二叉树的遍历(前序、中序、后序、层次)、二叉树的查找(前序、中序、后序、层次)、二叉树的删除
这篇文章主要介绍了树和二叉树的基础知识，包括树的存储方式、二叉树的定义、遍历方法（前序、中序、后序、层次遍历），以及二叉树的查找和删除操作。
java冯坚持
22 0
ephemerals__
|
5天前
|
C语言
【数据结构】栈和队列（c语言实现）（附源码）
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表，遵循“先进后出”原则；队列则在一端插入、另一端删除，遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现，并提供了完整的代码示例。栈和队列在实际应用中非常广泛，如二叉树的层序遍历和快速排序的非递归实现等。
ephemerals__
64 9
html的七十二变
|
2天前
|
存储 JavaScript 前端开发
执行上下文和执行栈
执行上下文是JavaScript运行代码时的环境，每个执行上下文都有自己的变量对象、作用域链和this值。执行栈用于管理函数调用，每当调用一个函数，就会在栈中添加一个新的执行上下文。
html的七十二变
12 2