• 我们可以在O(h)时间内完成二叉搜索树的查找、最大值、最小值、给定节点的前驱、后继操作，h代表树的高度。下面是用C++实现的《算法导论》12.2节伪代码，附习题解答。

#include 
    
     #include 
     
      #include 
      
       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 nodevoid 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 treevoid destroy(Node* pRoot){    std::queue
       
         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 walkvoid walk(Node* pRoot){    stack
        
          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 searchNode* 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 searchNode* 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 nullNode* 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 nullNode* 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 orderNode* 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 orderNode* 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  20913174minimum in the tree rooted at Node 15   is: 2minimum in the tree rooted at Node 18   is: 17minimum in the tree rooted at Node 7    is: 72177maximum in the tree rooted at Node 15   is: 20maximum in the tree rooted at Node 20   is: 20maximum in the tree rooted at Node 6    is: 13202013maximum in the tree rooted at Node 6    is: 13the predecessor of 15   is: 13the predecessor of 17   is: 15the predecessor of 7    is: 6minimum in the tree rooted at Node 18   is: 17the successor of 15 is: 17the successor of 17 is: 18the successor of 13 is: 15*/
        
       
      
     
    

• 习题

  12.2-1 c “911 240”说明240是911的左子树，这棵子树上不可能出现大于911的912

  12.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