资讯专栏INFORMATION COLUMN

笨蛋都看得懂的二叉树介绍(Java)

LiuZh / 2974人阅读

摘要:本文专门针对笨蛋介绍如何编写二叉树,包括二叉树的结构如何添加节点如何删除节点。二叉树的结构有三个要点每个节点最多有两个子节点,分别称作左子节点和右子节点。通过这种生长方式,我们无论何时都能得到满足前面三个要素的二叉树。

本文专门针对笨蛋介绍如何编写二叉树,包括二叉树的结构、如何添加节点、如何删除节点。

首先介绍二叉树的结构。

二叉树的结构有三个要点:

每个节点最多有两个子节点,分别称作左子节点和右子节点。

每个节点的左子节点的值比它小,右子节点的值比它大。

每个节点的左子树每个节点的值都比它小,右子树每个节点的值都比它大。

看上面这个例子,就完全符合这三点。

这时候笨蛋就会问了:前面两点我理解,但是第三点是怎么做到的?

所以接下来介绍下二叉树是如何 “生长” 起来的:

如上图所示,当加入一个新节点时,从根节点开始对它进行比较。如果它比根节点小,则放入根节点的左子树,如果比根节点大,则放入根节点的右子树。

然后再进行下一级节点的比较,直到遇到最后一级节点,才将新节点加入为该节点的左或右子节点。

以第四幅图的节点 25 为例,它第一次会与根节点 10 比较,结果就是 25 应该放入 10 的右子树,这就排除了它放入左子树的可能,即 25 不可能放到 4 的下面。

然后 25 再和节点 33 比较,结果是它比较小,所以应该放入 33 的左子树。因为 33 没有左子节点,那么 25 就直接作为 33 的左子节点了。

通过这种生长方式,我们无论何时都能得到满足前面三个要素的二叉树。

那么写代码该如何实现呢?所谓慢工出细活,我们一步一步来。

首先我们创建二叉树节点的基本结构。每个二叉树都有四个成员,如下所示。

</>复制代码

  1. public class BasicBTree {
  2. public int value; // 节点的值
  3. public BasicBTree left; // 节点的左子节点
  4. public BasicBTree right; // 节点的右子节点
  5. public BasicBTree parent; // 节点的父节点。如果为 null 则表示该节点是根节点
  6. // 构造方法
  7. public BasicBTree(int value) {
  8. this.value = value;
  9. }
  10. }

回头看第一张图,你会发现每个节点最多有三根线连着,上面的线就代表 BasicBTreeparent,下面两根线就分别代表 leftright 了。而节点中的数字就是 BasicBTreevalue

接下来我们要为 BasicBTree 编写两个简单的方法,用来给它添加左子节点和右子节点:

</>复制代码

  1. // 将一个节点加为当前节点的左子节点
  2. public void setLeft(BasicBTree node) {
  3. if (this.left != null) {
  4. this.left.parent = null; // 解除当前的左子节点
  5. }
  6. this.left = node;
  7. if (this.left != null) {
  8. this.left.parent = this; // 设置新子节点的父节点为自身
  9. }
  10. }
  11. // 将一个节点加为当前节点的右子节点
  12. public void setRight(BasicBTree node) {
  13. if (this.right != null) {
  14. this.right.parent = null; // 解除当前的右子节点
  15. }
  16. this.right = node;
  17. if (this.right != null) {
  18. this.right.parent = this; // 设置新子节点的父节点为自身
  19. }
  20. }

在上面两个方法的基础上,我们可以添加一个添加任意值节点的方法:

</>复制代码

  1. // 将一个节点加为当前节点的左或右子节点
  2. public void setChild(BasicBTree node) {
  3. if (node == null) {
  4. return;
  5. }
  6. if (node.value < this.value) {
  7. setLeft(node);
  8. } else if (node.value > this.value) {
  9. setRight(node);
  10. }
  11. }

另外我们再添加一个删除左子节点或右子节点的方法:

</>复制代码

  1. // 删除当前节点的一个直接子节点
  2. public void deleteChild(BasicBTree node) {
  3. if (node == null) {
  4. return;
  5. }
  6. if (node == this.left) {
  7. node.parent = null;
  8. this.left = null;
  9. } else if (node == right) {
  10. node.parent = null;
  11. this.right = null;
  12. }
  13. }

这几个方法都是非常简单的,其中 setChild()deleteChild() 这两个方法,我们后面介绍删除节点的时候会用到。

现在我们正式实现构造树的方法,就是把一个一个数字加到树里面去,让树越长越大的方法:

</>复制代码

  1. // 向当前节点下面的树中添加一个值作为新节点
  2. public void add(int value) {
  3. if (value < this.value) { // 表示应该放入左子树
  4. if (this.left == null) { // 如果左子树为空则构建一个节点加进去
  5. setLeft(new BasicBTree(value));
  6. } else {
  7. this.left.add(value); // 否则对左子树同样调用 add 方法(即递归)
  8. }
  9. } else if (value > this.value) { // 表示应该放入右子树
  10. if (this.right == null) { // 如果右子树为空则构建一个节点加进去
  11. setRight(new BasicBTree(value));
  12. } else {
  13. this.right.add(value); // 否则对右子树同样调用 add 方法(即递归)
  14. }
  15. }
  16. }

这个方法稍微复杂一些,主要是因为逻辑上使用了递归。这个方法怎么用呢?以最开始的树为例,演示如何长成这棵树:

</>复制代码

  1. public static void main(String[] args) {
  2. // 根节点
  3. BasicBTree tree = new BasicBTree(10);
  4. // 第一层子节点
  5. tree.add(4);
  6. tree.add(33);
  7. // 第二层子节点
  8. tree.add(25);
  9. tree.add(46);
  10. tree.add(8);
  11. tree.add(1);
  12. }

你可能会注意到,加入每一层的子节点时,层内节点的添加顺序可以任意调换,构造出来的树都是一样的;但是如果将不同层的节点顺序互换,构造出来的二叉树就会变样了。这当中的原因可以自己想想。

最后来介绍二叉树中最复杂的操作:删除节点。为什么这个操作最复杂呢?因为删除一个节点之后,要把它下面的节点接上来,同时要保持这棵树继续满足三要素。

如何把下面的节点接上来呢?最笨的方法当然是把被删节点的所有子节点一个个重新往树里面加。但是这样做效率实在不高。想想如果被删节点有上百万个子节点,那操作步骤就太多了(如下图所示)。

怎么做才能效率高呢?有一个办法,就是从被删节点的子节点中找到一个合适的,替换掉被删节点。这样做的步骤就少得多了。

不过这样的节点是否存在呢?答案是,除非被删节点没有子节点,否则是一定存在的。

而且这样的节点可能不止一个。原则上讲,被删节点的左子树的最大值,或右子树的最小值,都是满足条件的,都可以用来替换被删节点。比如说,将左子树的最大值节点替换上去之后,左子树的剩余节点的值都仍然小于该位置的节点。下面是一个例子:

比如要删除节点 33,而该节点左子树的最大值为 31,那么直接将 31 替换到 33 的位置即可,整棵树仍然满足三要素。

同理,被删节点右子树的最小值也可以用来替换被删节点。比如上图中 33 节点的右子节点 46 也可以用来替换 33,整棵树仍然满足三要素。

所以这个问题就转化为:如何寻找被删节点的左子树的最大值和右子树的最小值。显然,因为二叉树所有的左节点都比较小,右节点都比较大,所以要找最大值,顺着右节点找即可;要找最小值,顺着左节点找即可。下面是实现的代码:

</>复制代码

  1. // 搜索当前节点左子树中的最大值节点,如果没有左子节点则返回 null
  2. public BasicBTree leftMax() {
  3. if (this.left == null) {
  4. return null;
  5. }
  6. BasicBTree result = this.left; // 起始节点
  7. while (result.right != null) { // 顺着右节点找
  8. result = result.right;
  9. }
  10. return result;
  11. }
  12. // 搜索当前节点右子树中的最小值节点,如果没有右子节点则返回 null
  13. public BasicBTree rightMin() {
  14. if (this.right == null) {
  15. return null;
  16. }
  17. BasicBTree result = this.right; // 起始节点
  18. while (result.left != null) { // 顺着左节点找
  19. result = result.left;
  20. }
  21. return result;
  22. }

我们还剩下两个准备工作,第一个是实现节点的查找:

</>复制代码

  1. // 查询指定值的节点,如果找不到则返回 null
  2. public BasicBTree find(int value) {
  3. BasicBTree result = this; // 起始节点
  4. if (result.value == value) {
  5. return result;
  6. }
  7. while (result.left != null || result.right != null) {
  8. // 如果查找的值比当前节点小则顺着左子树查找;
  9. // 如果比当前节点大则顺着右子树查找。
  10. if (value < result.value && result.left != null) {
  11. result = result.left;
  12. } else if (value > result.value && result.right != null) {
  13. result = result.right;
  14. }
  15. if (result.value == value) {
  16. return result;
  17. }
  18. }
  19. return null;
  20. }

第二个是实现节点的替换:

</>复制代码

  1. // 将节点 node 替换为节点 replace
  2. public BasicBTree replace(BasicBTree node, BasicBTree replace) {
  3. // 1. replace 接管 node 的子节点
  4. replace.setLeft(node.left);
  5. replace.setRight(node.right);
  6. // 2. replace 从原来的 parent 脱离
  7. if (replace.parent != null) {
  8. replace.parent.deleteChild(replace);
  9. }
  10. // 3. node 原来的 parent 接管 replace
  11. if (node.parent != null) {
  12. node.parent.setChild(replace);
  13. }
  14. // 注意 2 必须在 3 之前,1 位置不论
  15. return replace;
  16. }

注意这里用到了之前的 setChild()deleteChild() 两个方法。而 replace() 方法之所以设计为返回 replace 参数,是为了使用方便。

最后我们就可以正式实现二叉树删除节点的方法了:

</>复制代码

  1. // 从树的子节点中删除指定的值,并重组剩余节点
  2. public BasicBTree delete(int value) {
  3. BasicBTree node = find(value);
  4. if (node == null) {
  5. return this;
  6. }
  7. // 没有子节点,直接删除即可
  8. if (node.left == null && node.right == null) {
  9. if (node.parent != null) {
  10. node.parent.deleteChild(node);
  11. return this;
  12. } else {
  13. // 表示整棵树唯一的根节点删了,只能返回 null
  14. return null;
  15. }
  16. }
  17. // 如果有子节点,则取左子树的最大值或者右子树的最小值都可以,
  18. // 来取代该节点。这里优先取左子树的最大值
  19. BasicBTree replace;
  20. if (node.left != null) {
  21. replace = replace(node, node.leftMax());
  22. } else {
  23. replace = replace(node, node.rightMin());
  24. }
  25. // 如果被删除的是根节点,则返回用于替换的节点,否则还是返回根节点
  26. return node == this ? replace : this;
  27. }

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/71034.html

相关文章

  • 一文掌握关于Java数据结构所有知识点(欢迎一起完善)

    摘要:是栈,它继承于。满二叉树除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。没有键值相等的节点。这是数据库选用树的最主要原因。 在我们学习Java的时候,很多人会面临我不知道继续学什么或者面试会问什么的尴尬情况(我本人之前就很迷茫)。所以,我决定通过这个开源平台来帮助一些有需要的人,通过下面的内容,你会掌握系统的Java学习以及面试的相关知识。本来是想通过Gitbook的...

    keithxiaoy 评论0 收藏0
  • 【数据结构初阶之二叉树】:二叉树相关的性质和经典的习题(用C语言实现,附图详解)

    摘要:当集合为空时,称该二叉树为空二叉树。也就是说,如果一个二叉树的层数为,且结点总数是,则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。 ...

    Martin91 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享 目录: 印象中的头条 面试背景 准备面试 ...

    tracymac7 评论0 收藏0
  • 从简历被拒到收割今日头条 offer,我用一年时间破茧成蝶!

    摘要:正如我标题所说,简历被拒。看了我简历之后说头条竞争激烈,我背景不够,点到为止。。三准备面试其实从三月份投递简历开始准备面试到四月份收,也不过个月的时间,但这都是建立在我过去一年的积累啊。 本文是 无精疯 同学投稿的面试经历 关注微信公众号:进击的java程序员K,即可获取最新BAT面试资料一份 在此感谢 无精疯 同学的分享目录:印象中的头条面试背景准备面试头条一面(Java+项目)头条...

    wdzgege 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<