二 元 搜 尋 樹
Binary search tree | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | |||||||||||||||||||||
发明时间 | 1960 | ||||||||||||||||||||
发明 | P·F· | ||||||||||||||||||||
|
二叉查找树(
若 任意 节点的 左 子 树不空 ,则左子 树上所有 节点的 值均小 于它的 根 节点的 值;若 任意 节点的 右子 树不空 ,则右子 树上所有 节点的 值均大 于它的 根 节点的 值;任意 节点的 左 、右子 树也分 别为二叉查找树;
二叉查找树相比于其他数据结构的优势在于查找、
二叉查找树的查找过程和
二叉查找树的查找算法[编辑]
若 b是 空 樹 ,則 搜索 失敗 ,否 則 :若 x等 於b的 根 節點 的 數 據 域 之 值,則 查找成功 ;否 則 :若 x小 於b的 根 節點 的 數 據 域 之 值,則 搜索 左 子 樹 ;否 則 :- 查找
右子 树。
Status SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) {
// 在 根 指 针T所 指 二叉查找树中递归地查找其關键字等於key的 數 據 元素 ,若 查找成功 ,
// 則 指 针p指向 該數據 元素 節點 ,并返回 TRUE,否 則 指 针指向 查找路 徑 上 訪問 的 最後
// 一 個 節點 并返回 FALSE,指 针f指向 T的 雙 親 ,其初始 调用值為NULL
if (!T) { // 查找不 成功
p = f;
return false;
} else if (key == T->data.key) { // 查找成功
p = T;
return true;
} else if (key < T->data.key) // 在 左 子 樹 中 繼續 查找
return SearchBST(T->lchild, key, T, p);
else // 在 右子 樹 中 繼續 查找
return SearchBST(T->rchild, key, T, p);
}
在 二叉查找树插入節点的算法[编辑]
若 b是 空 树,则将s所 指 節点 作 为根節点 插入 ,否 则:若 s->data等 于b的 根 節点 的 数 据 域 之 值,则返回 ,否 则:若 s->data小 于b的 根 節点 的 数 据 域 之 值,则把s所 指 節点 插入 到 左 子 树中,否 则:把 s所 指 節点 插入 到 右子 树中。(新 插入 節點 總 是 葉子 節點 )
/* 当 二 元 搜 尋 樹 T中 不 存在 关键字 等 于e.key的 数 据 元素 时,插入 e并返回 TRUE,否 则返回 FALSE */
Status InsertBST(BiTree *&T, ElemType e) {
if (!T) {
s = new BiTNode;
s->data = e;
s->lchild = s->rchild = NULL;
T = s; // 被 插節点 *s为新的 根 结点
} else if (e.key == T->data.key)
return false;// 关键字 等 于e.key的 数 据 元素 ,返 回 錯誤
if (e.key < T->data.key)
InsertBST(T->lchild, e); // 將 e 插入 左 子 樹
else if (e.key > T->data.key)
InsertBST(T->rchild, e); // 將 e 插入 右 子 樹
return true;
}
在 二叉查找树删除结点的算法[编辑]
若 *p结点为叶子 结点,即 PL(左 子 树)和 PR(右子 树)均 为空树。由 于删去叶 子 结点不破 坏整棵树的 结构,则只需修改 其双亲结点 的 指 针即可 。若 *p结点只 有 左 子 树PL或 右子 树PR,此时只 要 令 PL或 PR直接 成 为其双 亲结点 *f的 左 子 树(当 *p是 左 子 树)或 右子 树(当 *p是 右子 树)即 可 ,作 此修改 也不破 坏二叉查找树的特性。若 *p结点的 左 子 树和右子 树均不空 。在 删去*p之 后 ,为保持 其它元素 之 间的相 对位置 不 变,可 按中序 遍 历保持 有 序 进行调整,可 以有两种做法:其一是 令 *p的 左 子 树为*f的 左 /右 (依 *p是 *f的 左 子 树还是 右子 树而定 )子 树,*s为*p左 子 树的最 右 下 的 结点,而*p的 右子 树为*s的 右子 树;其二 是 令 *p的 直接 前 驱(in-order predecessor)或 直接 后 继(in-order successor)替 代 *p,然 后 再 从二叉查找树中删去它的直接前驱(或 直接 后 继)。
Status DeleteBST(BiTree *T, KeyType key) {
// 若 二 叉 查找树T中 存在 关键字 等 于key的 数 据 元素 时,则删除 该数据 元素 ,并返回
// TRUE;否 则返回 FALSE
if (!T)
return false; //不 存在 关键字 等 于key的 数 据 元素
else {
if (key == T->data.key) // 找到关键字 等 于key的 数 据 元素
return Delete(T);
else if (key < T->data.key)
return DeleteBST(T->lchild, key);
else
return DeleteBST(T->rchild, key);
}
}
Status Delete(BiTree *&p) {
// 该节点 为叶子 节点,直接 删除
BiTree *q, *s;
if (!p->rchild && !p->lchild) {
delete p;
p = NULL; // Status Delete(BiTree *&p) 要 加 &才能 使 P指向 NULL
} else if (!p->rchild) { // 右子 树空则只需重接 它的左 子 树
q = p->lchild;
/*
p->data = p->lchild->data;
p->lchild=p->lchild->lchild;
p->rchild=p->lchild->rchild;
*/
p->data = q->data;
p->lchild = q->lchild;
p->rchild = q->rchild;
delete q;
} else if (!p->lchild) { // 左 子 树空只 需重接 它的右子 树
q = p->rchild;
/*
p->data = p->rchild->data;
p->lchild=p->rchild->lchild;
p->rchild=p->rchild->rchild;
*/
p->data = q->data;
p->lchild = q->lchild;
p->rchild = q->rchild;
delete q;
} else { // 左右 子 树均不空
q = p;
s = p->lchild;
while (s->rchild) {
q = s;
s = s->rchild;
} // 转左,然 后 向 右 到 尽 头
p->data = s->data; // s指向 被 删结点 的 “前 驱”
if (q != p)
q->rchild = s->lchild; // 重 接 *q的 右子 树
else
q->lchild = s->lchild; // 重 接 *q的 左 子 树
delete s;
}
return true;
}
struct Node
节点Node
- 如:
sizeof( Probe )
,Probe
作 为二 叉 树节点在 typedef
中 定 义的指 针。
Python实现:
def find_min(self): # Gets minimum node (leftmost leaf) in a subtree
current_node = self
while current_node.left_child:
current_node = current_node.left_child
return current_node
def replace_node_in_parent(self, new_value=None):
if self.parent:
if self == self.parent.left_child:
self.parent.left_child = new_value
else:
self.parent.right_child = new_value
if new_value:
new_value.parent = self.parent
def binary_tree_delete(self, key):
if key < self.key:
self.left_child.binary_tree_delete(key)
elif key > self.key:
self.right_child.binary_tree_delete(key)
else: # delete the key here
if self.left_child and self.right_child: # if both children are present
successor = self.right_child.find_min()
self.key = successor.key
successor.binary_tree_delete(successor.key)
elif self.left_child: # if the node has only a *left* child
self.replace_node_in_parent(self.left_child)
elif self.right_child: # if the node has only a *right* child
self.replace_node_in_parent(self.right_child)
else: # this node has no children
self.replace_node_in_parent(None)
二叉查找树的遍历[编辑]
def traverse_binary_tree(node, callback):
if node is None:
return
traverse_binary_tree(node.leftChild, callback)
callback(node.value)
traverse_binary_tree(node.rightChild, callback)
排 序 (或 称 构造)一棵二叉查找树[编辑]
def build_binary_tree(values):
tree = None
for v in values:
tree = binary_tree_insert(tree, v)
return tree
def get_inorder_traversal(root):
'''
Returns a list containing all the values in the tree, starting at *root*.
Traverses the tree in-order(leftChild, root, rightChild).
'''
result = []
traverse_binary_tree(root, lambda element: result.append(element))
return result
二叉查找树性能分析[编辑]
二叉查找树的优化[编辑]
参 见[编辑]
外部 链接[编辑]
- Literate implementations of binary search trees in various languages(页面
存 档备份,存 于互联网档案 馆) on LiteratePrograms - Binary Tree Visualizer(页面
存 档备份,存 于互联网档案 馆) (JavaScript animation of various BT-based data structures) - Kovac, Kubo. Binary Search Trees. Korešponden?ný seminár z programovania. [2018-04-29]. (
原始 内容 (Java applet)存 档于2018-04-30). (页面存 档备份,存 于互联网档案 馆) - Madru, Justin. Binary Search Tree. JDServer. 18 August 2009 [2018-04-29]. (
原始 内容 存 档于2010-03-28). (页面存 档备份,存 于互联网档案 馆) C++ implementation. - Binary Search Tree Example in Python(页面
存 档备份,存 于互联网档案 馆) - References to Pointers (C++).
微 软开发者网络.微 软. 2005 [2018-04-29]. (原始 内容 存 档于2017-03-29). (页面存 档备份,存 于互联网档案 馆) Gives an example binary tree implementation.
|