树及树的算法（2） —— 二叉查找树

二叉查找树（Binary Search Tree，简称BST），或者是一棵空树，或者是具有下列性质的二叉树：

若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

它的左、右子树也分别为二叉排序树。二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，期望O(logn)，最坏O(n)(数列有序，树退化成线性表)。

虽然二叉排序树的最坏效率是O(n)，但它支持动态查询，且有很多改进版的二叉排序树可以使树高为O(logn)，如SBT，AVL，红黑树等。故不失为一种好的动态排序方法。

二叉查找树的总体架构如图：

二叉查找树包括平衡二叉树（AVL树）和红黑树，首先是一个可搜索容器：

class SearchTree :
	public virtual Tree, public virtual SearchableContainer
{
public:
	virtual Object& FindMin () const = 0;
	virtual Object& FindMax () const = 0;
};

所以BST实现了可搜索容器的特性：

enum TREENODE{
    TREE_LEFT = 0,
    TREE_RIGHT = 1
};

class BinaryTree : public virtual Tree
{
protected:
	Object* key;          //根的值
	BinaryTree* left;
	BinaryTree* right;
public:
	BinaryTree ();
	BinaryTree (Object& _key);
	virtual ~BinaryTree ();

	Object& Key () const;
	Object* getKeyPtr() const;
	virtual BinaryTree& Left () const;
	virtual BinaryTree& Right () const;

    virtual void SetLeft(BinaryTree* root);
    virtual void SetRight(BinaryTree* root);
    virtual void SetKey(Object* object);

	virtual void AttachLeft (BinaryTree& tree);
	virtual void AttachRight (BinaryTree& tree);
	virtual void AttachKey (Object& object);

	virtual Object& DetachKey ();
	virtual BinaryTree& DetachLeft ();
	virtual BinaryTree& DetachRight ();

	// ...
    void Purge();
    virtual Tree& Subtree (unsigned int n) const;
    virtual bool IsEmpty () const;
    virtual bool IsLeaf () const;
    virtual unsigned int Degree () const;
	void DepthFirstTraversal (PrePostVisitor& visitor) const;
};

BinaryTree::BinaryTree():
key(0),
left(0),
right(0)
{}

BinaryTree::BinaryTree( Object& _key ):
key(&_key),
left(new BinaryTree()),
right(new BinaryTree())
{}

void BinaryTree::Purge()
{
	if (!IsEmpty ())
	{
		if (IsOwner ())
			delete key;
		delete left;
		delete right;
		key = 0;
		left = 0;
		right = 0;
	}
}

BinaryTree::~BinaryTree()
{
	Purge();
}

bool BinaryTree::IsEmpty() const
{
    return key == 0;
}

bool BinaryTree::IsLeaf() const
{
    return (left==0 && right==0)?true:false;
}

unsigned int BinaryTree::Degree() const
{
    return 2U;
}

Tree& BinaryTree::Subtree( unsigned int n ) const
{
    switch (n)
    {
    case TREE_LEFT:
        return *left;
    case TREE_RIGHT:
        return *right;
    default:
        break;
    }

    throw domain_error ("out of range");
}

Object& BinaryTree::Key() const
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    return *key;
}

BinaryTree& BinaryTree::Left() const
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    return *left;
}

BinaryTree& BinaryTree::Right() const
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    return *right;
}

void BinaryTree::AttachLeft( BinaryTree& tree )
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    left = &tree;
}

void BinaryTree::AttachRight( BinaryTree& tree )
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    right = &tree;
}

void BinaryTree::AttachKey( Object& object )
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    key = &object;
}

Object& BinaryTree::DetachKey()
{
    if (IsLeaf())
    {
        throw domain_error("invalid operation");
    }

    Object& result=*key;
    key = 0;

    return result;
}

BinaryTree& BinaryTree::DetachLeft()
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    BinaryTree& ret = *left;
    left = new BinaryTree();
    return ret;
}

BinaryTree& BinaryTree::DetachRight()
{
    if (IsEmpty())
    {
        throw domain_error("invalid operation");
    }
    BinaryTree& ret = *right;
    right = new BinaryTree();
    return ret;
}

//二叉树的遍历，采用先序方式
void BinaryTree::DepthFirstTraversal( PrePostVisitor& visitor ) const
{
    if (visitor.IsDone ())
    {
        return;
    }

    if (!IsEmpty ())
    {
        visitor.PreVisit (*key);
        left->DepthFirstTraversal (visitor);
        visitor.Visit (*key);
        right->DepthFirstTraversal (visitor);
        visitor.PostVisit (*key);
    }
}

void BinaryTree::SetLeft( BinaryTree* root )
{
    left = root;
}

void BinaryTree::SetRight( BinaryTree* root )
{
    right = root;
}

void BinaryTree::SetKey( Object* object )
{
    key = object;
}

Object* BinaryTree::getKeyPtr() const
{
	return key;
}