二叉查找树的性质
- 若任意节点的左子树不为空，则左子树上所有结点的值均小于它的根结点的值；
- 任意节点的右子树不为空，则右子树上所有结点的值均大于它的根结点的值；
- 任意节点的左、右子树也分别为二叉查找树。
- 没有键值相等的节点（no duplicate nodes）。
节点
根据二叉查找树性质不难写出节点类
class Node
attr_reader :value
attr_accessor :left, :right
def initialize(v)
@value = v
end
end
插入节点
根据二叉查找树的性质:
- 若值等于根节点, 不插入
- 若根节点为空, 插入根节点
- 若值小于根节点, 插入左子树
- 若值大于根节点
def insert(v)
case value <=> v
when 1 then insert_left(v)
when -1 then insert_right(v)
when 0 then false
end
end
def inspect
"{#{value}::#{left.inspect}|#{right.inspect}}"
end
private
def insert_left(v)
if left
left.insert(v)
else
self.left = Node.new(v)
end
end
def insert_right(v)
if right
right.insert(v)
else
self.right = Node.new(v)
end
end
空节点
在上面的Node对象中, left和right为nil, 这样在插入时就需要判断左右是否为nil, 在之后的查找中也需要做nil判断, 十分的繁琐
加入空节点的概念就可以去除冗余的nil判断, 简化代码
class EmptyNode
# 预留给查询用
def include?(*)
false
end
def insert(*)
false
end
def inspect
"{}"
end
end
重新定义一下Node的代码
class Node
attr_reader :value
attr_accessor :left, :right
def initialize(v)
@value = v
@left = EmptyNode.new
@right = EmptyNode.new
end
def inspect
"{#{value}::#{left.inspect}|#{right.inspect}}"
end
def insert(v)
case value <=> v
when 1 then insert_left(v)
when -1 then insert_right(v)
when 0 then false
end
end
private
# 插入时不再需要nil判断, 空节点的insert返回false
def insert_left(v)
left.insert(v) or @left = Node.new(v)
end
def insert_right(v)
right.insert(v) or @right = Node.new(v)
end
end
查找
因为二叉树的左右是有序的, 使用递归就可以简单实现, 步骤如下
- 若树是空的, 则查找未命中
- 若等于根节点, 则查找命中
- 若小于根节点, 则查找左子树
- 若大于根节点, 则查找右子树
def include?(v)
case value <=> v
when 1 then left.include?(v)
when -1 then right.include?(v)
when 0 then true
end
end
现在找不到值时, 自然会返回false
若是没有EmptyNode的定义, 这里会有很繁琐的nil判断
