[游戏开发]【算法框架】二叉搜索树BST

【算法框架】二叉搜索树BST

提取自labuladong得算法小抄

查找数是否存在

void BST(TreeNode root,int target){
	if (root.val == target){
		...
		...
		//找到目标之后，所需要做的事
	}
	
	//递归
	if (root.val < target)
		BST(root.right,target);
	if (root.val > target)
		BST(root.left,target);

插入一个数

TreeNode insertIntoBST(TreeNode root ,int val){
// 找到空位插入
	if(root == null)
		return new TreeNode(val);
// 如果已经存在就不用重复插入了，直接返回
	if(root.val == val)
		return root
// val大，则应该插在右子树上面
	if (root.val<val)
		root.right = insertIntoBST(root.right,val)；
// val小，则应该插在左子树上面
	if(root.val>val);
		root.left = insertIntoBST(root.left,val);
	return root;
}

删除一个数

TreeNode deleteNode(TreeNode root ,int key){
	if (root.val=key){
	// 删除操作
	}elsr if(root.val>key){
	//去左子树寻找key
		root.left = deletNode(root.left,key);
	}else if(root.val<key){
	//去右子树寻找key
		root.right= deletNode(root.right,key);
	}
	return root;
}