二叉搜索树的一些性质 - vzard's blog
vzardlloo
·
2020-09-22
·
via vzard's blog
二叉搜索树的中序遍历的结果序列是一个递增排序的序列。
中序遍历的顺序是：左节点 - 根节点 - 右节点
示例代码：
1
2
3
4
5
6
7
8
9
10
11
12
| result := make([]*Node,0)
func inorder(root *Node) {
if root == nil {
return
}
inorder(root.Left)
result = append(result,root)
inorder(root.Right)
return
}
|
二叉搜索树的后继节点
即比当前节点大的最小节点，主要思路：取改节点的右节点，然后一直取左节点直到左节点为空，最后指向的就是该节点的后继节点
示例代码：
1
2
3
4
5
6
7
| func Successor(node *Node) *Node {
succ := node.Right
for succ.Left != nil {
succ = node.Left
}
return succ
}
|
二叉搜索树的前驱节点
即比当前节点小的最大节点，主要思路：取改节点的左节点，然后一直取右节点直到右节点为空，最后指向的就是该节点的前驱节点
示例代码：
1
2
3
4
5
6
7
| func Predecessor(node *Node) *Node {
pre := node.Left
for pre.Right != nil {
pre = pre.Right
}
return pre
}
|
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。
