- 我们可以在O(h)时间内完成二叉搜索树的查找、最大值、最小值、给定节点的前驱、后继操作，h代表树的高度。下面是用C++实现的《算法导论》12.2节伪代码，附习题解答。
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
struct Node
{
int key;
Node* parent;
Node* left;
Node* right;
Node(int k) :key(k),parent(nullptr),
left(nullptr),right(nullptr){}
Node(){}
};
//insert a node to the tree rooted at a giver node
void insert(Node* pRoot, Node* pAdd)
{
Node *pParent = pRoot, *pTmpParent;
bool bLeft;
while(true)
{
bLeft = (pAdd->key < pParent->key) ? true : false;
pTmpParent = bLeft ? pParent->left : pParent->right;
if(nullptr != pTmpParent)
{
pParent = pTmpParent;
continue;
}
pAdd->parent = pParent;
if(bLeft)
pParent->left = pAdd;
else
pParent->right = pAdd;
break;
}
}
/*create the tree, we assume all keys to be distinct
* 15
* 6 18
* 3 7 17 20
* 2 4 13
* 9
*/
Node* build()
{
Node* pRoot = new Node(15);
insert(pRoot, new Node(6));
insert(pRoot, new Node(3));
insert(pRoot, new Node(2));
insert(pRoot, new Node(4));
insert(pRoot, new Node(7));
insert(pRoot, new Node(13));
insert(pRoot, new Node(9));
insert(pRoot, new Node(18));
insert(pRoot, new Node(17));
insert(pRoot, new Node(20));
return pRoot;
}
//destroy the tree
void destroy(Node* pRoot)
{
std::queue<Node*> q;
q.push(pRoot);
Node* p;
while(!q.empty())
{
p = q.front();
q.pop();
if(!p)
continue;
q.push(p->left);
q.push(p->right);
delete p;
}
}
//inorder tree walk
void walk(Node* pRoot)
{
stack<Node*> stk;
stk.push(pRoot);
while(true)
{
Node* pCurrent = stk.top();
if(pCurrent)
{
stk.push(pCurrent->left);
continue;
}
stk.pop();
if(stk.empty())
break;
pCurrent = stk.top();
cout << pCurrent->key << "\t";
stk.pop();
stk.push(pCurrent->right);
}
}
//recursive search
Node* search(Node* pRoot, int key)
{
if(!pRoot)
return nullptr;
if(key == pRoot->key)
return pRoot;
if(key < pRoot->key)
return search(pRoot->left, key);
else
return search(pRoot->right, key);
}
//nonrecursive search
Node* search1(Node* pRoot, int key)
{
while(pRoot && key != pRoot->key)
{
if(key < pRoot->key)
pRoot = pRoot->left;
else
pRoot = pRoot->right;
}
return pRoot;
}
//returns a pointer to the minimum element in the subtree rooted at a given node x, which we assume to be not null
Node* minimum(Node* pRoot)
{
cout << "minimum in the tree rooted at Node " << pRoot->key << "\tis: ";
while(pRoot->left != nullptr)
pRoot = pRoot->left;
cout << pRoot->key << endl;
return pRoot;
}
Node* minimum_recursive(Node* pRoot)
{
if(nullptr == pRoot->left)
return pRoot;
return minimum_recursive(pRoot->left);
}
//returns a pointer to the maximum element in the subtree rooted at a given node x, which we assume to be not null
Node* maximum(Node* pRoot)
{
cout << "manimum in the tree rooted at Node " << pRoot->key << "\tis: ";
while(pRoot->right != nullptr)
pRoot = pRoot->right;
cout << pRoot->key << endl;
return pRoot;
}
Node* maximum_recursive(Node* pRoot)
{
if(nullptr == pRoot->right)
return pRoot;
return maximum_recursive(pRoot->right);
}
//returns the node with the largest key smaller than p->key in the sorted order
Node* predecessor(Node* p)
{
if(p->left)
return maximum(p->left);
Node* pParent = p->parent;
while(pParent && p == pParent->left)
{
p = pParent;
pParent = p->parent;
}
return pParent;
}
//returns the node with the smallest key greater than p->key in the sorted order
Node* successor(Node* p)
{
if(p->right)
return minimum(p->right);
Node* pParent = p->parent;
while(pParent && pParent->right == p)
{
p = pParent;
pParent = p->parent;
}
return pParent;
}
void testBinarySearchTree()
{
Node* pRoot = build();
walk(pRoot);
cout << endl;
{
cout << search(pRoot, 9)->key << endl;
cout << search(pRoot, 13)->key << endl;
cout << search1(pRoot, 17)->key << endl;
cout << search1(pRoot, 4)->key << endl;
}
{
minimum(pRoot);
minimum(pRoot->right);
minimum(pRoot->left->right);
cout << minimum_recursive(pRoot)->key << endl;
cout << minimum_recursive(pRoot->right)->key << endl;
cout << minimum_recursive(pRoot->left->right)->key << endl;
}
{
maximum(pRoot);
maximum(pRoot->right->right);
maximum(pRoot->left);
cout << maximum_recursive(pRoot)->key << endl;
cout << maximum_recursive(pRoot->right->right)->key << endl;
cout << maximum_recursive(pRoot->left)->key << endl;
}
{
cout << "the predecessor of " << pRoot->key << "\tis: "
<< predecessor(pRoot)->key << endl;
cout << "the predecessor of " << pRoot->right->left->key << "\tis: "
<< predecessor(pRoot->right->left)->key<< endl;
cout << "the predecessor of " << pRoot->left->right->key << "\tis: "
<< predecessor(pRoot->left->right)->key << endl;
}
{
cout << "the successor of " << pRoot->key << "\tis: "
<< successor(pRoot)->key << endl;
cout << "the successor of " << pRoot->right->left->key << "\tis: "
<< successor(pRoot->right->left)->key<< endl;
cout << "the successor of " << pRoot->left->right->right->key << "\tis: "
<< successor(pRoot->left->right->right)->key << endl;
}
destroy(pRoot);
}
/*output:
2 3 4 6 7 9 13 15 17 18 20
9
13
17
4
minimum in the tree rooted at Node 15 is: 2
minimum in the tree rooted at Node 18 is: 17
minimum in the tree rooted at Node 7 is: 7
2
17
7
maximum in the tree rooted at Node 15 is: 20
maximum in the tree rooted at Node 20 is: 20
maximum in the tree rooted at Node 6 is: 13
20
20
13
maximum in the tree rooted at Node 6 is: 13
the predecessor of 15 is: 13
the predecessor of 17 is: 15
the predecessor of 7 is: 6
minimum in the tree rooted at Node 18 is: 17
the successor of 15 is: 17
the successor of 17 is: 18
the successor of 13 is: 15
*/
-
习题
12.2-1 c “911 240”说明240是911的左子树，这棵子树上不可能出现大于911的91212.2-2 见maximum_recursive() minimum_recursive()
12.2-3 见 predecessor()
12.2-4 反例： 在下面这棵树上查找关键字5，集合A{3}，B{2,4,5} A中的元素3 < b中的元素2 不成立。
正确的结论应该是：对集合A中任意元素a有a < k,对集合C中任意元素c有c > k。12.2-5 如果节点A的前驱P有左孩子K，那么A的前驱就应该是K而不是P了，所以前驱没有左孩子。
12.2-7 简单来讲，调用一次minimum和n-1次successor行走的路径和inorder_tree_walk是一样的，都是每个节点被访问两次，每次从一个节点到下一个节点的过程都是O(1)-time的，所以n个节点总共耗时O(n)-time。
12.2-8 受7题启发，successor和tree-walk的共同点是最终走过的路途长度和遍历过的节点树是相同的，不同之处在于路程和已遍历节点数两者的递增速度有差异。tree-walk算法中两者是始终匀速的，互不相欠；successor算法中路程有时稍块，提前预支了一些尚未遍历节点的路程份额，而这个预支长度最多是h，所以O（n+h）
12.2-9 按照predecessor和successor的算法，如果x是y的左孩子，y就是x的successor，如果x是y的右孩子，y就是x的predecessor
2
\
4
/ \
3 5