网站导航
> 文档中心 > Java｜二叉树基础详解

Java｜二叉树基础详解

网友: 文档中心 2022-05-31 11:23:43

文章目录

  • 树结构的引入
  • 关于树的基础概念
    • 树的特点
    • 树的概念
  • 二叉树
    • 二叉树常考的性质
    • 常见二叉树
    • 关于完全二叉树的编号
    • 二分搜索树(BST)
    • 平衡二叉树
  • 二叉树的实现
  • 二叉树的基本操作
    • 遍历
      • 前序遍历
      • 中序遍历
      • 后序遍历
      • 层序遍历
      • 前中后序遍历的结果
    • 二叉树基本题
      • 求结点个数
      • 求叶子结点个数
      • 求第k层结点个数
      • 求二叉树的高度
      • 判断二叉树中是否包含值val
  • 总结

树结构的引入

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

在OS中的文件系统就是基于树结构进行文件管理的

如果所有文件都放在一个“目录”下，若当前操作系统有1亿个文件，最坏情况遍历1亿次才能找到特定元素

OS分为多级目录，我们只需要O(logn)的时间复杂度就可以找到指定元素

关于树的基础概念

我们已经知道，线性数据结构或者说线性表的元素之间是逻辑上连续的，呈直线排列

而树是一种非线性的数据结构，它是有n个有限结点组成一个具有层次关系的集合

树的特点

树有一个特殊的结点，称为根结点，根结点没有前驱结点

除根结点，其余结点被分成m个集合，彼此之间互不相交，若相交，就不是树

每棵子树有且只有一个前驱，但可以有0或者多个后继

树的概念

1.子树不相交

2.除了根结点没有父结点之外，每个结点有且只有一个父结点

3 树，边的个数x以及结点的个数n之间的关系：x = n - 1 (每个结点都有一个与父结点相连的边，只有根结点没有)

4.结点和树的度：

结点的度：该结点中包含的子树个数称为该结点的度

树的度：书中最大的结点的度称为了树的度

5.叶子结点：度为0的结点

非叶子结点：度不为0的结点，说明还存在子树

6.根结点：没有父结点的结点，树中有且只有一个根结点

7.结点的层次：从根结点开始计算，根结点为第一层

树的高度：当前树中结点层次最大的即为树的高度

二叉树

树中结点最大的度为2的树称之为二叉树

二叉树中，一个结点最多有两颗子树，二叉树结点的度小于等于2

且子树有左右之分，左右的顺序不能颠倒，分为只有左子树没有右子树的结点，只有右子树没有左子树的结点

二叉树常考的性质

1.在深度为k的二叉树中，最多存在2^k - 1个结点

2.在第k层，该层最多有2^(k -1)个结点

3.由于任意二叉树都满足结点个数n和边长具备x = n - 1

在二叉树中，度为2的结点和度为0的结点有以下关系：n0 = n2 + 1

度为0度结点个数永远比度为2的结点的个数多一个

关于第三种性质的推导：

二叉树中只有三种结点：n0, n1, n2

n0 + n1 + n2 = n ( 三种结点的个数相加就是总结点的个数 )

n1 + 2n2 = n - 1 ( n1有一条边，n2有两条边，相加后总共有 n - 1条边 )

将两个式子化简可以得到：n0 = n2 + 1

常见二叉树

满二叉树：在该二叉树中，每一层的结点个数都是最大值

完全二叉树：完全二叉树的结点编号和满二叉树完全一致，一一对应

满二叉树就是一个特殊的完全二叉树

在完全二叉树中不存在只有右子树而没有左子树的结点，换言之，如果存在度为1的结点，这个结点必然只有左树而没有右树的结点，这样的结点有且只有一个

关于完全二叉树的编号

1.若根结点从1开始编号，若任意一个结点x，即存在子树也有父结点，则该结点的父结点编号为x / 2，其左子树编号为2x，右子树编号为2x + 1

2.若根结点从0开始编号(“堆”就是基于数组实现的完全二叉树)：则在完全二叉树中，若任意结点既有子树也有父结点，该结点编号为x，则父结点的编号为(x - 1) / 2，左子树的结点编号为2x + 1，右子树的结点编号为2x + 2

二分搜索树(BST)

结点的值之间有一个大小关系：左子树结点值 < 根结点值 < 右子树结点值

Java｜二叉树基础详解

若在BST中查找一个元素，其实就是二分查找

平衡二叉树

该树中任意一个结点的左右子树高度差 <= 1

注意是所有结点都要满足，仅仅是根结点的子树满足情况是不够的，因为子树的子树可能不平衡

二叉树的实现

树结点：

class TreeNode<E> {    E val;    TreeNode<E> left;    TreeNode<E> right;    public TreeNode(E val){ this.val = val;    }}

二叉树的纯手工构建：

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

构建完成后的二叉树见后图

二叉树的基本操作

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

遍历

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

对于二叉树来说一共有四种遍历方式：前序遍历、中序遍历、后序遍历、层序遍历

前三种称为深度优先遍历(DFS)，最后一种称为广度优先遍历(BFS)

深度优先遍历借助栈实现，广度优先遍历借助队列实现

二叉树图例：

Java｜二叉树基础详解

前序遍历

先访问根结点，然后递归访问左子树，再递归问右子树(根左右)

上图为例的遍历结果：A B D E G H C F

代码实现：

/** * 传入根结点，就能按照前序遍历的方式输出 - 根左右 * @param root */public void preOrder(TreeNode root){    if(root == null){ return;    }    System.out.print(root.val + " ");    preOrder(root.left);    preOrder(root.right);}

中序遍历

先递归的访问左子树，然后访问根结点，最后访问右子树(左根右)

当根结点第二次走到时才能访问

上图为例的遍历结果：D B G H E A C F

代码实现：

/** * 传入根结点，就能按照中序遍历的方式输出 - 左根右 * @param root */public void inOrder(TreeNode root){    if(root == null){ return;    }    inOrder(root.left);    System.out.print(root.val + " ");    inOrder(root.right);}

后序遍历

先递归访问左子树，在递归访问右子树，最后访问根结点

上图为例的遍历结果：D H G E B F C A

代码实现：

/** * 传入根结点，就能根据后序遍历的方式输出 - 左右根 * @param root */public void postOrder(TreeNode root){    if(root == null){ return;    }    postOrder(root.left);    postOrder(root.right);    System.out.print(root.val + " ");}

层序遍历

将二叉树一层一层遍历，从上往下，从左至右

前三种遍历通过画栈的方式来辅助遍历顺序

上图为例的遍历结果：A B C D E F G H

层序遍历需要借助递归函数和队列来实现，因此在之后的博客中会专门讲解前中后序以及层序遍历

前中后序遍历的结果

  1. 前序遍历的第一个结点一定是根结点
  2. 中序遍历左子树在根结点的左侧，右子树的遍历结果在根结点的右侧
  3. 后序遍历的结果集反转之后是(根右左)，后序遍历的最后一个结果一定为根结点

二叉树基本题

求结点个数

public int getNodes(TreeNode root){    if(root == null){ return 0;    }  //如果根结点不为空，那么返回自身加上左子树的结点个数和右子树的结点个数之和    return 1 + getNodes(root.left) + getNodes(root.right);    //可以简化为一句话    //return root == null ? 0 : 1 + getNodes(root.left) + getNodes(root.right);}

求叶子结点个数

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

求第k层结点个数

public int getKLevelNodes(TreeNode root, int k){    if(k < 1 || root == null){ return 0;    }    if(k == 1){ //当k为1时，说明只有根结点这一层，因此直接返回1即可 return 1;    }    //此时k不为1，就继续找下一层    return getKLevelNodes(root.left, k - 1) + getKLevelNodes(root.right, k - 1);}

求二叉树的高度

public int height(TreeNode root){    if(root == null){ return 0;    }  //树的高度 = 当前层 + 子树中的高度    return 1 + Math.max(height(root.left), height(root.right));}

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

public boolean contains(TreeNode<E> root, E val){    if(root == null){ return false;    }    if(root.val == val){ return true;    }    return contains(root.left, val) || contains(root.right, val);}

总结

该博客仅针对二叉树的基础部分做一个介绍，关于二叉树的内容、题目还有很多，之后会陆续发布关于前中后序以及层序遍历的详细解法，以及一些常考笔试、面试题的解答，如果有需要的话，就点个小小的关注吧～～

网络标签：

相关问题