【二叉树】二叉排序树专题

什么是二叉排序树？

二叉排序树要么是空树，要么具有以下的特性：

• 如果其根节点有左子树，那么左子树上所有结点的值都小于根结点的值
• 如果其根结点有右子树，那么右子树上所有结点的值都大于根结点的值
• 二叉排序树的左右子树也要都是二叉排序树

【算法】二叉排序树中查找值

递归遍历二叉树

递归结束条件：

• 传入结点为NULL，返回NULL，表示key值不存在
• 或传入结点值与key值一样，返回结点

若key值小于结点值，进入左孩子查找。否则进入右孩子查找

BiTree SearchBST(BiTree root, int key) {
	//如果root为NULL，说明树中并无该结点，返回NULL；若结点值等于key，返回结点
	if(!root || root->val == key)
		return root;
	else if(key < root->val)
		return SearchBST(root->left, key);
	else if(key > root->val)
		return SearchBST(root->right, key);
}

【算法】二叉排序树中插入数值

二叉排序树是动态查找表的一种形式，有时会在搜索过程中删除或删除表中元素。该元素的插入位置一定位于二叉排序树的叶子结点，并且一定是查找失败时访问的最后一个叶子结点的左或右孩子

/*
*root:被搜索的当前结点
*lastNode：上一个结点，当root为NULL（表明未找到key值时，为该插入位置的双亲结点）
*BiTree* p：用来返回该操作结点
*/
bool SearchBST(BiTree root, int key, BiTree lastNode, BiTree *p) {
	//若root结点不存在，代表二叉排序树中没有key值，将lastNode结点赋给p，方便之后的插入操作
	if(!root) {
		*p = lastNode;
		return 0;
	}

	//如果相等，让p指向该结点
	if(root->val == key) {
		*p = root;
		return 1;
	}
	else if(key < root->val) {
		return SearchBST(root->left, key, root, p);
	}
	else if(key > root->val) {
		return  SearchBST(root->right, key, root, p);
	}
}

bool InsertBST(BiTree root, int key) {
	BiTree* p = NULl;
	//若未找到结点，在二叉排序树中添加结点
	if(!SearchBST(root, key, NULL, p)) {
		BiTree* node = (BiTree*)malloc(sizeof(BiTree));
		node->val = key;
		node->lchild = NULL;
		node->rchild = NULL;
		
		//如果p为NULL，证明二叉排序树为空
		if(!p) {
			root = node;
		}
		//此时p为该被操作的双亲结点
		if(key < p->val)
			p->lchild = node;
		else if(key > p->val)
			p->rchild = node;
		return true;
	}
	//若查找成功，则不需要做任何操作
	return false;
}