文档章节

设计一个算法,找出二叉查找树中指定结点的“下一个“结点(也即中序后继)。可以假定每个结点都含有指向父结点的连接。

一贱书生
 一贱书生
发布于 2016/11/18 11:34
字数 1078
阅读 31
收藏 0

问题分析

假设需要查找 node 结点的下一个结点,需要考虑三种情况:

①node 节点有右孩子

下一个结点就是以node结点的右孩子为根的子树中的最左下结点。如下图:node=8,它的下一个结点为12.

 

②node 节点没有右孩子时,node节点是其父结点的左孩子。如下图,结点8的下一个结点是结点12

 

 

③node 节点没有右孩子时,node节点是其父结点的右孩子,如下图,结点14 的下一个结点是 结点16

 

 

 

如何在一棵二叉树中查找某个结点?

可以用先序遍历的思路。但是一定要注意递归的实现---第11行的 return target 是很有意义的。

在每一次的递归调用中,每个方法都有一个自己的 target 局部变量。如果在这个方法里面找到了目标结点,如果没有 return 返回的话,当递归回退时就会丢失“已找到的目标结点”----即上一层的 find 方法中的target 变量还是null(尽管在下一层递归中已经找到了目标结点)

通过第11行的 return 语句,如果在某一层还未找到目标结点,则会继续递归调用下去,如果找到了,在 return 的时候,上一层的find方法的target变量就不会为 null ,  从而在最终 find 方法结束时,返回找到的目标结点。

 

复制代码

 1     //采用先序遍历查找值为ele的结点
 2     private BinaryNode find(BinaryNode root, int ele){
 3         if(root == null)
 4             return null;
 5         if(root.ele == ele)
 6             return root;
 7         BinaryNode target = null;
 8         target = find(root.left, ele);
 9         if(target == null)//如果左子树中没有值为ele的结点,if成立,在右子树中查找
10             target = find(root.right, ele);
11         return target;
12     }

复制代码

①第3-4行是应对查找到叶子结点的情况

②第5-6行,是成功查找到了指定结点的情况。(①②类似于先序遍历中的访问根结点)

③第8行,表示先在左子树中查找(类似于先序遍历左子树)

④第9-10行if表示在左子树中未查找到该结点,则查找右子树⑤第11行,返回查找的结点。若返回null,表示未找到

 

三,代码分析

①node 节点有右孩子

复制代码

1 if(node.right != null)
2 {
3     BinaryNode current = node.right;
4     while(current.left != null)
5     {
6     current = current.left;
7     }
8     nextNode = current;
9  }

复制代码

第3行,先定位到node结点的右孩子。

第4行while循环,查找最左下结点

 

②node 节点没有右孩子时,node节点是其父结点的左孩子

1 else if(node.parent != null){//node结点 是 parent 的孩子
2     if(node.parent.left != null && node.parent.left.equals(node))// node 是 parent 的左孩子
3         nextNode = node.parent;

如果node节点是其父结点的左孩子,那么下一个结点就是node节点的父结点。

 

③node 节点没有右孩子时,node节点是其父结点的右孩子

复制代码

1 else{//node 是 parent的右孩子
2     BinaryNode current = node.parent;
3     //一直往着右孩子的父结点指针向上走
4     while(current.parent.right != null && current.parent.right.equals(current))
5     {
6         current = current.parent;
7     }
8     nextNode = current.parent;
9 }

复制代码

要注意第4行while循环中的第一个条件:current.parent.right != null

为什么不要判断 current.parent != null 呢?因为在前面的if语句中已经判断了(if(node.parent != null)

 

完整代码:

public class BSTNextNode {

    private class BinaryNode{
        int ele;
        BinaryNode left;
        BinaryNode right;
        BinaryNode parent;
        int hash;//cache hashCode
        
        public BinaryNode(int ele) {
            this.ele = ele;
            parent = left = right = null;
        }
        
        @Override
        public boolean equals(Object obj) {
            if(obj == null)
                return false;
            if(!(obj instanceof BinaryNode))
                return false;
            BinaryNode node = (BinaryNode)obj;
            return node.ele == this.ele;
        }
        
        @Override
        public int hashCode() {// 参考《effective java》中覆盖equals方法
            int result = hash;
            if(result == 0){
                result = 17;
                result = result*31 + ele;
                hash = result;
            }
            return result;
        }

或者:

 

下面是该算法的实现代码(已正确处理结点为空的情况)

public TreeNode inorderSucc(TreeNode n)
{
if(n==null) return null;
/*
找到右子结点,则返回右子树里最左边的结点
*/
if(n.right!=null)
{
return leftMostChild(n.right);
}
else
{
TreeNode q=n;
TreeNode x=q.parent;
//向上直至位于左边而不是右边
while(x!=null&&x.left!=q)
{
q=x;
x=x.parent;
}
return x;
}
}


public TreeNode leftMostChild(TreeNode n)
{
if(n==null)
return null;
while(n.left!=null)
{
n=n.left;
}
return null;

}

 

 

或者

 

 

© 著作权归作者所有

共有 人打赏支持
一贱书生
粉丝 19
博文 724
码字总数 600123
作品 0
私信 提问
Java数据结构和算法 - 二叉树

前言 数据结构可划分为线性结构、树型结构和图型结构三大类。前面几篇讨论了数组、栈和队列、链表都是线性结构。树型结构中每个结点只允许有一个直接前驱结点,但允许有一个以上直接后驱结点...

fireway
2018/08/23
0
0
数据结构学习笔记-排序/队/栈/链/堆/查找树/红黑树

排序: 插入排序:每次从剩余数据中选取一个最小的,插入已经排序完成的序列中 合并排序:将数据分成左右两组分别排序,然后合并,对每组数据的排序递归处理。 冒泡排序:重复交换两个相邻元...

duanbowen
2017/05/26
0
0
算法知识梳理(10) - 二叉查找树

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/18
0
0
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生
2016/04/28
96
0
MySQL 索引 BST树、B树、B+树、B*树

一、二叉查找树(Binary Search Tree)BST 即二叉搜索树: 所有非叶子结点至多拥有两个儿子(Left和Right); 所有结点存储一个关键字; 非叶子结点的左指针指向小于其关键字的子树,右指针指...

PeakFang-BOK
2018/11/13
0
0

没有更多内容

加载失败,请刷新页面

加载更多

CSS 选择器参考手册

CSS 选择器参考手册 选择器 描述 [attribute] 用于选取带有指定属性的元素。 [attribute=value] 用于选取带有指定属性和值的元素。 [attribute~=value] 用于选取属性值中包含指定词汇的元素。...

Jack088
今天
1
0
数据库篇一

数据库篇 第1章 数据库介绍 1.1 数据库概述  什么是数据库(DB:DataBase) 数据库就是存储数据的仓库,其本质是一个文件系统,数据按照特定的格式将数据存储起来,用户可以对数据库中的数据...

stars永恒
今天
2
0
Intellij IDEA中设置了jsp页面,但是在访问页面时却提示404

在Intellij IDEA中设置了spring boot的jsp页面,但是在访问时,却出现404,Not Found,经过查找资料后解决,步骤如下: 在Run/Debug Configurations面板中设置该程序的Working Directory选项...

uknow8692
昨天
3
0
day24:文档第五行增内容|每月1号压缩/etc/目录|过滤文本重复次数多的10个单词|人员分组|

1、在文本文档1.txt里第五行下面增加如下内容;两个方法; # This is a test file.# Test insert line into this file. 分析:给文档后增加内容,可以用sed 来搞定;也可以用while do done...

芬野de博客
昨天
2
0
深入理解JVM—JVM内存模型

深入理解JVM—JVM内存模型 我们知道,计算机CPU和内存的交互是最频繁的,内存是我们的高速缓存区,用户磁盘和CPU的交互,而CPU运转速度越来越快,磁盘远远跟不上CPU的读写速度,才设计了内存...

onedotdot
昨天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部