首页 > 代码库 > 算法导论 第12章 二叉查找树
算法导论 第12章 二叉查找树
二叉查找树是一种树数据结构，它与普通的二叉树最大的不同就是二叉查找树满足一个性质：对于树中的任意一个节点，均有其左子树中的所有节点的关键字值都不大于该节点的关键字值，其右子树中的任意一个节点的关键字值都不小于该节点的关键字值。
在二叉查找树上可以进行搜索、取最小值、取最大值、取指定节点的前驱、取指定节点的后继以及插入和删除节点操作，因此二叉查找树和堆（大顶堆和小顶堆）一样，也可以做优先队列，都能够在 O(lgn) 的时间内取得集合的最大值和最小值。一个二叉查找树的期望高度为O(lgn)，因此在二叉查找树上的基本操作都能在期望时间O(lgn)下实现。对二叉查找树的前序、中序和后序遍历均是在 O(n) 的时间复杂度内实现。
使用二叉查找树也有一个问题，随着插入和删除操作的不断执行，树的高度就会发生变化，不一定为O(lgn)，这也是它的一个缺陷，因此在做优先队列时，虽然堆和查找树都是利用二叉树的结构来实现的，但是用堆较查找树多。
/*
* 算法导论 第十二章 二叉查找树
*/
#include <iostream>
#include <stack>
using namespace std;
//二叉树节点定义
typedef struct TNode
{
int key;
TNode *parent, *left, *right;
} TNode, Tree;
/*
* 前序遍历
* 递归
*/
void preOrderTreeWalkRecursion(Tree* tree)
{
if (tree)
{
cout<<tree->key<<" ";
preOrderTreeWalkRecursion(tree->left);
preOrderTreeWalkRecursion(tree->right);
}
}
/*
* 前序遍历二叉树
* 非递归
*/
void preOrderTreeWalkNoRecursion(Tree* tree)
{
if (! tree)
{
return;
}
stack<TNode*> treeStack;
treeStack.push(tree);
while (! treeStack.empty())
{
tree = treeStack.top();
while (tree)
{
cout<<tree->key<<" ";
tree = tree->left;
treeStack.push(tree);
}
treeStack.pop();
if (! treeStack.empty())
{
tree = treeStack.top();
treeStack.pop();
treeStack.push(tree->right);
}
}
}
/*
* 中序遍历
* 递归
*/
void inOrderTreeWalkRecursion(Tree* tree)
{
if (tree)
{
inOrderTreeWalkRecursion(tree->left);
cout<<tree->key<<" ";
inOrderTreeWalkRecursion(tree->right);
}
}
/*
* 中序遍历
* 非递归 用栈
*/
void inOrderTreeWalkNoRecursionStack(Tree* tree)
{
if (! tree)
return;
stack<TNode*> treeStack;
treeStack.push(tree);
while (! treeStack.empty())
{
tree = treeStack.top();
while (tree)
{
tree = tree->left;
treeStack.push(tree);
}
treeStack.pop();
if (! treeStack.empty())
{
tree = treeStack.top();
treeStack.pop();
cout<<tree->key<<" ";
treeStack.push(tree->right);
}
}
}
/*
* 中序遍历
* 非递归 无栈
*/
void inOrderTreeWalkNoRecursionNoStack(Tree* tree)
{
if (! tree)
return;
while (tree)
{
TNode* pLeft = tree->left;
if (pLeft)
{
while (pLeft->right && pLeft->right != tree)
{
pLeft = pLeft->right;
}
if (! pLeft->right)
{//向下搜索建立遍历顺序的链接关系
pLeft->right = tree;
tree = tree->left;
continue;
} else {//向上回溯遍历解除链接关系
pLeft->right = NULL;
}
}
//在向下阶段直到没有左孩子，在向上回溯阶段表示左子树已经遍历完
//此时应该遍历此节点，然后遍历其右孩子
cout<<tree->key<<" ";
tree = tree->right;
}
}
/*
* 后序遍历
* 递归
*/
void postOrderTreeWalkRecursion(Tree* tree)
{
if (tree)
{
postOrderTreeWalkRecursion(tree->left);
postOrderTreeWalkRecursion(tree->right);
cout<<tree->key<<" ";
}
}
/*
* 后序遍历
* 非递归
*/
void postOrderTreeWalkNoRecursion(Tree* tree)
{
if (! tree)
return;
stack<TNode*> treeStack;
treeStack.push(tree);
TNode* tempNode = NULL;//保存刚刚访问过的节点
while (! treeStack.empty())
{
tree = treeStack.top();
while (tree)
{
tree = tree->left;
treeStack.push(tree);
}
treeStack.pop();
if (! treeStack.empty())
{
tree = treeStack.top();
//如果右孩子为空，或者右孩子为刚刚访问过的节点则
//说明此节点的所有左右孩子都访问过了，可以访问此节点了
if (! tree->right || tree->right == tempNode)
{
cout<<tree->key<<" ";
tempNode = tree;
treeStack.pop();
//子树tree已经全部访问完，为了避免重复访问tree这颗子树，需要压入一个空指针
//以便下次直接访问tree的父节点
treeStack.push(NULL);
} else {
//否则访问右孩子
treeStack.push(tree->right);
}
}
}
}
/*
* 二叉排序树的查找
* 递归
* 时间复杂度为树的高度O(lgn)
*/
TNode* treeSearch(Tree* tree, int k)
{
if (! tree || tree->key == k)
{
return tree;
}
if (k < tree->key)
{
treeSearch(tree->left, k);
} else {
treeSearch(tree->right, k);
}
}
/*
* 二叉排序树查找
* 非递归
* 时间复杂度为O(lgn)
*/
TNode* treeSearchIterative(Tree* tree, int k)
{
while (tree && tree->key != k)
{
if (k < tree->key)
{
tree = tree->left;
} else {
tree = tree->right;
}
}
return tree;
}
/*
* 查找二叉排序树中的最小元素
* 即为最左元素
* 时间复杂度为O(lgn)
*/
TNode* treeMinimum(Tree* tree)
{
while (tree->left)
{
tree = tree->left;
}
return tree;
}
/*
* 查找二叉查找树中的最大元素
* 即为最右元素
* 时间复杂度为O(lgn)
*/
TNode* treeMaximum(Tree* tree)
{
while (tree->right)
{
tree = tree->right;
}
return tree;
}
/*
* 求二叉排序树中指定节点node的中序遍历后继
* 如果node右子树不为空，则后继则为node右子树中的最小节点
* 否则node右子树为空，必须向上回溯找到第一个节点：该节点为其父节点的左孩子
* 后继即为其父节点，如果不存在这样的节点，说明node为最右节点，后继为空
* 时间复杂度为O(lgn)
*/
TNode* treeSuccessor(TNode* node)
{
if (! node)
return NULL;
if (node->right)
{
return treeMinimum(node->right);
}
TNode* temp = node->parent;
while (temp && node == temp->right)
{
node = temp;
temp = node->parent;
}
return temp;
}
/*
* 求二叉排序树中指定节点node的中序遍历前驱
* 如果node左子树不为空，则前驱则为node左子树中的最大节点
* 否则node左子树为空，必须向上回溯找到第一个节点：该节点为其父节点的右孩子
* 前驱即为其父节点，如果不存在这样的节点，说明node为最左节点，前驱为空
* 时间复杂度为O(lgn)
*/
TNode* treePredecessor(TNode* node)
{
if (! node)
return NULL;
if (node->left)
{
return treeMaximum(node->left);
}
TNode* temp = node->parent;
while (temp && node == temp->left)
{
node = temp;
temp = node->parent;
}
return temp;
}
/*
* 二叉查找树插入元素
* 新元素只能插入到二叉树的叶子节点上
* 首先需要找到这个插入点
* 时间复杂度主要在搜索插入位置上，为O(lgn)
*/
void treeInsert(Tree* tree, TNode* node)
{
if (! tree)
{
return;
}
TNode* pos = NULL;
while (tree)
{
pos = tree;
if (node->key < tree->key)
{
tree = tree->left;
} else {
tree = tree->right;
}
}
if (node->key < pos->key)
{
pos->left = node;
} else {
pos->right = node;
}
node->parent = pos;
}
/*
* 二叉查找树删除元素
* 删除二叉查找树中的一个元素根据被删除节点分三种情况
* 1、删除节点没有孩子，这种情况下直接删除该节点即可
* 2、删除节点有一个孩子，这种情况先将节点删除，再将该节点的孩子填补上来即可
* 3、删除节点有两个孩子，这种情况相对麻烦一点，需要先找到删除节点的后继节点
* 然后将该删除节点的数据值修改为后继结点的值，然后将后继节点删除，由于后继节点不可能有左孩子，否则删除节点
* 的后继就应该是后继节点的左孩子，所以后继节点的删除很简单
* 时间主要用在查找删除节点的后继节点上，所以需要O(lgn)
*/
TNode* treeDelete(Tree* tree, TNode* node)
{
if (! tree || ! node)
return NULL;
TNode* delNode = NULL;//要删除的节点
if (! (node->left && node->right))
{
delNode = node;
} else {
delNode = treeSuccessor(node);
}
TNode* fillNode = NULL;//填补（到被删除的位置）节点
if (delNode->left)
{
fillNode = delNode->left;
} else {
fillNode = delNode->right;
}
//可能delNode没有孩子
if (fillNode)
{
fillNode->parent = delNode->parent;
}
//delNode可能是根节点
if (delNode->parent)
{
if (delNode == delNode->parent->left)
{
delNode->parent->left = fillNode;
} else {
delNode->parent->right = fillNode;
}
}
//如果删除的是node的后继节点，则复制数据
if (delNode != node)
{
node->key = delNode->key;
}
return delNode;
}
int main()
{
int arr[] = {15, 5, 16, 3, 12, 20, 10, 13, 18, 23, 6, 7};
int len = sizeof(arr) / sizeof(arr[0]);
Tree* tree = new Tree();
tree->key = arr[0];
tree->left = tree->parent = tree->right = NULL;
for (int i=1; i<len; i++)
{
TNode* node = new TNode();
node->key = arr[i];
node->left = node->parent = node->right = NULL;
treeInsert(tree, node);
}
cout<<"前序递归遍历二叉排序树："<<endl;
preOrderTreeWalkRecursion(tree);
cout<<endl<<"前序非递归遍历二叉排序树："<<endl;
preOrderTreeWalkNoRecursion(tree);
cout<<endl<<"中序递归遍历二叉排序树："<<endl;
inOrderTreeWalkRecursion(tree);
cout<<endl<<"中序非递归用栈遍历二叉排序树："<<endl;
inOrderTreeWalkNoRecursionStack(tree);
cout<<endl<<"中序无栈非递归遍历二叉排序树："<<endl;
inOrderTreeWalkNoRecursionNoStack(tree);
cout<<endl<<"后序递归遍历二叉排序树："<<endl;
postOrderTreeWalkRecursion(tree);
cout<<endl<<"后序非递归遍历二叉排序树："<<endl;
postOrderTreeWalkNoRecursion(tree);
cout<<endl;
cout<<"最大元素为："<<treeMaximum(tree)->key<<endl;
cout<<"最小元素为："<<treeMinimum(tree)->key<<endl;
int key = 7;
TNode* pNode = treeSearch(tree, key);
cout<<key<<"的中序前驱是："<<(treePredecessor(pNode))->key
<<"，中序后继是："<<(treeSuccessor(pNode))->key<<endl;
key = 19;
pNode = new TNode();
pNode->key = key;
pNode->left = pNode->parent = pNode->right = NULL;
treeInsert(tree, pNode);
cout<<"插入节点"<<key<<"以后，先序遍历结果为："<<endl;
preOrderTreeWalkRecursion(tree);
cout<<endl;
pNode = treeSearch(tree, key);
pNode = treeDelete(tree, pNode);
if (pNode)
{
delete pNode;
pNode = NULL;
}
cout<<"删除节点"<<key<<"以后，先序遍历结果为："<<endl;
preOrderTreeWalkRecursion(tree);
cout<<endl;
return 0;
}算法导论 第12章 二叉查找树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。