C++ 二叉搜索树（一）基础功能

本篇为学习 清华大学-邓俊辉-数据结构课 实现的二叉搜索树（Binary Search Tree），主要集中于查找、插入以及删除操作。

数据结构实现的顺序：节点 → rightarrow → 二叉树 → rightarrow → 二叉搜索树

节点Node

为了方便操作，这里直接将Node定义为二叉树BinaryTree和搜索树BST的友元friend类，你也可以不定义为友元类，而改成给节点实现查询和修改操作。

API

// 获得节点高度的宏
#define getHeight(node) ((node) ? (node)->height : -1)

class Node
{
	friend class BinaryTree;
	friend class BST;
private:
	int data;
	Node* parent; // 父节点
	Node* left, * right; // 左右子节点
	int height; // 高度
public:
	Node(int d = 0, Node* p = NULL, Node* l = NULL, Node* r = NULL, int h = 0)
		: data(d), parent(p), left(l), right(r), height(h) {};

	Node* insertAsLeft(int data); // 给当前节点加入左子
	Node* insertAsRight(int data); // 给当前节点加入右子
    
	Node* getSuccessor() const; // 得到中序遍历下的后继节点
    Node* getTallerChild(); // 得到高度较高的那一个子节点

	bool isRight(); // 判断当前节点是否为某个节点的右子
	bool isLeft(); // 判断当前节点是否为某个节点的左子
};

这里有六个方法以及一个宏，主要是为了方便之后二叉树的实现中对节点的调用：

• insertAsLeft和insertAsRight用于分别在当前节点左和右插入子节点，并返回对应子节点。
• getSuccessor返回当前节点在树的中序遍历中的直接后继节点。
• getTallerChild()返回当前节点的孩子中高度较高的那个。
• isRight和isLeft判断当前节点是否为某个节点的子节点。
• 宏getHeight(node)得到节点的高度，封装为宏而不是直接取node->height是为了防止节点为空的情况。

节点方法的实现

比较简单，不做过多的解释，后面有2点需要说明。

Node* Node::insertAsLeft(int data)
{
	if (!left) left = new Node(data, this);
	return left;
}

Node* Node::insertAsRight(int data)
{
	if (!right) right = new Node(data, this);
	return right;
}

Node* Node::getSuccessor() const
{
	Node* successor;
	// 如果有右子，那么后继在右子树中
	if (right) {
		successor = right;
		while ((successor->left)) successor = successor->left;
	}
	// 如果没有，那么后继在祖先中
	else {
		successor = this->parent;
		while (successor && successor->isRight()) successor = successor->parent;
		if(successor) successor = successor->parent;
	}
	return successor;
}

Node* Node::getTallerChild()
{ // 使用了前面定义的宏getHeight
	return (getHeight(left) >= getHeight(right)) ? left : right;
}

bool Node::isRight()
{
	return parent->right == this;
}

bool Node::isLeft()
{
	return parent->left == this;
}

要注意以下两点：

• 插入子节点时如果位置上已经有节点，那么直接返回当前已有的子节点，不进行插入操作。

• 取当前节点中序遍历下的直接后继有两种情况：

  1. 若当前节点有右子树，那么沿右子树的左子不断向下到最后一个节点，这个节点就是直接后继。

  如图所示，2为current的直接后继：

  2. 若当前节点没有右子树，那么直接后继就是将当前节点作为其左子树中一员的最近祖先。

  如下图所示，两棵树的1都是current的直接后继：

二叉树BinaryTree

下面实现了一个简单的二叉树及基本功能，为后面实现搜索树做准备。

API

class BinaryTree
{
protected:
	int size_; // 树的节点总数
	Node* root_; // 根节点
	int updateHeight(Node* node); // 更新node的高度
	void updateHeightAbove(Node* node); // 更新node及其所有祖先的高度
public:
	BinaryTree() : size_(0), root_(NULL) {};
    ~BinaryTree();
	int size() const { return size_; };
	bool empty() const { return root_ == NULL; };
	Node* insertAsRoot(int data); // 创建根节点
	Node* insertAsLeft(Node* subroot, int data); // 插入左子节点
	Node* insertAsRight(Node* subroot, int data); // 插入右子节点
};

方法的实现 ~BinaryTree()

析构函数只需使用任意一种方法遍历树并删除节点就可以了，下面使用层序遍历的方法实现：

BinaryTree::~BinaryTree()
{
	if (root_) {
		queue q;
		q.emplace(root_);
		while (!q.empty()) {
			Node* node = q.front();
			q.pop();
			if (node->left) q.emplace(node->left);
			if (node->right) q.emplace(node->right);
			delete node;
		}
	}
}	

insertAsXxx()

在不同位置插入节点，一共有三个方法：

// 创建根节点：
Node* BinaryTree::insertAsRoot(int data)
{
	if (!root_) {
		size_ = 1;
		root_ = new Node(data);
	}
	return root_;
}
// 为subroot加入左子节点
Node* BinaryTree::insertAsLeft(Node* subroot, int data)
{
	if (!subroot) return NULL;
	++size_;
	subroot->insertAsLeft(data);
	updateHeightAbove(subroot);
	return subroot->left;
}
// 为subroot加入右子节点
Node* BinaryTree::insertAsRight(Node* subroot, int data)
{
	if (!subroot) return NULL;
	++size_;
	subroot->insertAsRight(data);
	updateHeightAbove(subroot);
	return subroot->right;
}

updateHeight()与updateHeightAbove()

更新树中指定节点的高度。

注意：节点的高度是指当前节点到根节点的路径中的边个数，根节点高度为0，如果为空树那么根节点高度-1。

// 更新node的高度
int BinaryTree::updateHeight(Node* node)
{// 高度为子节点中高度最高的那个加一
	node->height = 1 + max(node->left->height, node->right->height);
	return node->height;
}
// 更新node及其所有祖先的高度
void BinaryTree::updateHeightAbove(Node* node)
{
	while (node) {
		updateHeight(node);
		node = node->parent;
	}
}

二叉搜索树BST API

搜索树继承了上面的BinaryTree。

class BST: public BinaryTree
{
protected:
	Node* hot_; // 下面解释
	Node*& searchIn(Node*& root, int data);// search的辅助函数
	void removeAt(Node*& target); // remove的辅助函数
public:
	Node*& search(int data); // 查找
	Node*& insert(int data); // 插入
	bool remove(int data); // 删除
};

3个操作：

• search查找并返回查找结果
• insert插入元素并返回该元素对应节点
• remove删除指定值的节点

注意：

• hot_用于在各项操作中记录父节点，这样便于跨函数操作，具体作用可以看下面的代码实现。
• 上面的操作中大多使用了Node*&，这类似于Node**，这样可以修改引用的那个指针指向的位置。

方法的实现 search(data)

方法：从根开始搜索，若当前节点值小于data，则转向左子；若大于，则转向右子；若找到了，则返回目标节点；若到树叶后还是没找到，则返回NULL。

下面给出实现，以及各个变量在搜索结束时的位置图示方便理解。

Node*& BST::searchIn(Node*& root, int e) {
    // 终止条件为树找到目标或到叶子还未找到
	if (!root || root->data == e) return root;
    // 记录当前节点
	hot_ = root; 
    // 递归查找
	return searchIn((root->data > e ? root->left : root->right), e);
}

Node*& BST::search(int data)
{
	hot_ = NULL;
	return searchIn(root_, data);
}

下面是三种情况下hot_与return节点在搜索结束时的位置：

• 搜索25：

• 搜索17，注意此时返回的节点为15右子的引用（此时为空）：

• 搜索10，此时hot_为10的空父节点：

insert(data)

先用刚刚实现的search(data)查找要插入数据是否已经存在，若是，直接返回，若否，则在search返回的那个节点处进行插入。

Node*& BST::insert(int data)
{
	Node*& node = search(data);
    // 如果已有要插入数据就直接返回
	if (node) return node;
	++size_;
	node = new Node(data, hot_);
	// 更新祖先高度
	updateHeightAbove(node);
	return node;
}

由于函数中先进行了一次search，此时hot_指向的正是将要加入的新节点的父节点，而search返回的那个指针引用node正是这次数据应该存放的新节点，如代码中6行所示，将node指向新节点同时将hot_指定为父节点即可。

remove(data)

有2种情况：

• 若要删除节点至多1个子节点，则令其父节点指向其子节点或NULL。
• 若要删除节点有2个子节点，那么找到要删除节点中序遍历下的直接后继（在Node中已实现），交换数据，然后对该后继（有一个右子或没有子，此时为情况1）进行删除操作。

具体实现的细节已在代码中注释：

bool BST::remove(int data)
{
	Node*& target = search(data);
	if (target == NULL) return false;
	removeAt(target); // 删除的实际逻辑在这里面
	--size_; 
	updateHeightAbove(hot_); // 在removeAt中已经修改了hot_，以此再更新高度
	return true;
}

void BST::removeAt(Node*& target)
{
	Node* willDelete = target;
    // 前两种为情况1
	if (!target->left) { 
		target = target->right;
		target->parent = willDelete->parent;
	}
	else if (!target->right) {
        hot_ = target->parent;
		target = target->left;
		target->parent = willDelete->parent;
	}
	else {// 情况2 
		// 找到直接后继
		Node* successor = target->getSuccessor(); 
		// 当前节点值改为后继的值
		target->data = successor->data; 
		// 要删除节点变为直接后继
		willDelete = successor; 
		// 临时变量 记录后继的父亲 使下面的代码简洁一些
        Node* p = successor->parent;
        // 后继的父亲的一子指向后继的右节点，这里要判断一下后继为其父的左子还是右子
		((successor == target->right) ? p->right : p->left)
			= successor->right;
        // 后继的右子的父亲变为后继的父亲
		if (successor->right) successor->right->parent = 
			((successor == target->right) ? p->right : p->left);
	}
    hot_ = willDelete->parent; // 指向被删除节点的父亲，高度发生改变的只可能是被删除节点的祖先节点，hot_用于后面高度的更新
	delete willDelete; // 删除
}