删除二叉查找树BST中某一特定范围中的所有元素

1. 删除二叉查找树BST中某一特定范围中的所有元素

一开始检查该树的根节点是否在删除范围内，如果在则检查它的左子树和右子树，对于左子树而言，如果根节点还在范围内，删除该左子树跟节点以及它的右子树，继续向左检查，直到子树的跟节点不再范围内为止，然后子树向下和它的右子树检查，如果右子树跟在范围内，则删除右子树跟和它的右子树，然后子树的右子树连接到它原始右子树的左子树，直到为跟节点为止，对于该树的右子树而言，只需使用同样方法反过来即可，最后全部子树处理好了之后，对跟节点进行处理，只需删除根节点然后重新建立二叉查找树，这个方法的时间复杂度是O(h)，其中h代表树的高度

2. 、编写递归算法，对于二叉树中每一个元素值为X的结点，删去以它为根的子树，并释放相应的空间。

//结点定义
template
class BstTree;
template
class BstNode
{   
  friend class BstTree;
 private:
  int Level;
  T data;
  BstNode* LeftPtr;
  BstNode* RightPtr;
 public:
  BstNode(const T& info=0,BstNode* left=0,BstNode* right=0,int lev=0)
  {
   data=info;LeftPtr=left;RightPtr=right;Level=lev;
  }
};

//释放子树空间，注意传递一个二维指针（即searchTree函数返回的结点的地址），即指针的地址，以此来释放空间
template
void BstTree::releaseHelper(BstNode** root)
{
 if(*(root)!=0)
 {
  BstNode* tempt=(*root);
   releaseHelper(&((*root)->LeftPtr));
   releaseHelper(&((*root)->RightPtr));
   coutdata<<" ";
   delete tempt;
 }
}

//查找要删除的子树的根结点
template
BstNode* BstTree::serchTree(const T& value)
{
 BstNode* tempt=Root;
 bool found=false;
 for(; ;)
 {
  if(found || tempt==0) break;
  if(valuedata)
   tempt=tempt->LeftPtr;
    else if(value>tempt->data)
   tempt=tempt->RightPtr;
    else
     found=true;
    }
   if(found)
               return tempt;//查找到要删除子树的根节点
          else
               return NULL;//否则返回NULL
  

}

写的较匆忙，仅供参考

3. 验证一颗树是否为有效的二叉搜索树bst，比如，二叉树

满意答案望远镜8级2010-03-22完全二叉树看是几层的，比如3层完全二叉树，就有7个结点，结点总数是（2的3次方）减1个；叶子结点数是2的（3减1次方）个，就是4个。如果是n层完全二叉树，结点总数是（2的n次方）减1个；叶子结点数是2的（n减1次方）个；会了就非常简单。这回你明白了吗？追问：如果完全二叉树700个结点，有多少叶子结点回答：所谓完全二叉树，是不可能有700个结点的，完全二叉树的第N层，都会是2的N-1次幂个结点，而上一层，则是N-2次幂个结点，所以总节点数应该是2N次幂减1，700不是一个这样的数，所以不会有700个结点。如果是两层，那应该是4－1＝3个结点，三层，是8－1＝7个结点四层，是16－1＝15个结点五层，是32－1＝31个结点六层，是64－1＝63个结点七层，是128－1＝127个结点八层，是256－1＝255个结点九层，是512－1＝511个结点十层，是1024－1＝1023个结点。。。。因此，不会出现700个结点的完全二叉树。追问：可是我做到这个题了啊！回答：你确定是完全二叉树吗？有“完全”二字吗？追问：题目中确实有啊，答案是350回答：正好是总结点数的一半！那这个好记了

4. 写出删除二叉排序树bt中值为x的结点的算法并实现（二叉排序树以二叉链表形式存储，删除后仍然保持二叉排序

//定义二叉树链式结构
typedef struct BitSortNode
{
	int data;				   //数据域
	struct BitSortNode *lchild;//左子树
	struct BitSortNode *rchild;//右子树
}BitSortNode,*BiSortTree;

//递归实现删除值为item的节点
int DeleteBiSortTree(BiSortTree &bst,int item) 
{
	BiSortTree p;
	//树为空,未找到待删除元素,删除失败
    if (bst==NULL)  
		return 0;
    //待删除元素小于树根结点值,继续在左子树中删除
	if(item data)  
		return  DeleteBiSortTree(bst->lchild,item);
    //待删除元素大于树根结点值,继续在右子树中删除
    if(item > bst->data)  
		return  DeleteBiSortTree(bst->rchild,item);

    //待删除元素等于树根结点值且左子树为空，将右子树作为整个树并返回真
    if(bst->lchild==NULL)  
	{
		p=bst;
		bst=bst->rchild;
		free(p);
		return 1;
    }
    //待删除元素等于树根结点值且右子树为空，将左子树作为整个树并返回真
    else if(bst->rchild==NULL)  
	{
		p=bst;
		bst=bst->lchild;  
		free(p);
		return 1;
    }
    //待删除元素等于树根结点值且左、右子树均不为空时的处理情况
    else  
	{
		//中序前驱结点就是左孩子结点时，把左孩子结点值赋给树根结点，
		//然后从左子树中删除根结点
		if(bst->lchild->rchild==NULL)  
		{
			bst->data=bst->lchild->data;
			//转换成删除左孩子节点
			return  DeleteBiSortTree(bst->lchild,bst->lchild->data);
		}
		//找出中序前驱结点，即左子树的右下角结点，把该结点值赋给树根结点，
		//然后从以中序前驱结点为根的树上删除根结点
		else  
		{
			BiSortTree p1=bst, p2=bst->lchild;
			while(p2->rchild!=NULL)  
			{
				p1=p2;
				p2=p2->rchild;
			}
			bst->data=p2->data;
			//转换成删除最右节点
			return DeleteBiSortTree(p1->rchild, p2->data);
		}
	}
}

5. 编写在以BST为树根指针的二叉搜索树上进行查找值为item的结点的非递归算法，若查找成功能则由item带回整个

typedef int ElemType;
typedef struct bn{
    ElemType item;
    struct bn *left,*right;
} BTreeNode;
bool   Find(BTreeNode *BST,ElemType &item)
{
    BTreeNode *now=BST;
    while (now)
    {
        if (item>now->item) now=now->right;
        else if (itemitem) now=now->left;
        else return true;
    }
    return false;
}

6. 二叉排序树的插入 如果遇到 相同的节点 怎么办

二叉排序树不过是提供一种数据结构，如果没有应用，它的存在没有任何意义。所以随便怎么样都行，看你的具体需求。

如果你实际应用中允许相同的值，那么向左向右插入都可以，你只要保证你的树在中序遍历时是非严格单调递增即可
如果你实际应用中要求值唯一，那么你的实现应该以某种形式告诉用户，比如说返回某个特殊值，或者抛出异常

7. 若某二叉树中的所有节点值均大于其左树上的所有节点小于右书上的，为什么序

这是二叉查找树，也叫二叉排序树、二叉搜索树。
其特点是若左子树不空，则左子树上所有结点的值均小于它的根结点的值；若右子树不空，则右子树上所有结点的值均大于它的根结点的值。
这样查找时，与根的关键值比较，如果小递归找左子树，大递归找右子树，直到找到或者为空为止。查找时间为O(logn)，效率高。

8. 为什么删除二叉排序树中一个结点,再重新插入上去,不一定得到原来的二叉排序树

二叉排序树只要求每一个结点的左孩子小于它；右孩子大于等于它；
首先我们看看删除操作： 
“先将删除的节点与最后一个结点交换，交换之后，删除最后一个结点，然后重构二叉树。”
在这个过程中，如果你删除的是一个在根结点左边的结点，那么跟最后一个结点交换之后，为了保持二叉排序树的特性，最后一个结点会逐渐上移，很可能改变根结点的位置。

然后我们看看插入操作：
“直接跟根节点比较，如果比根结点小，插入左子树，一次递归下去，选择合适的结点,如果大于根结点，依次类推”
在这个过程中，不会改变根结点的位置。
所以得到的平衡二叉树很可能不一样。
建议你画一个图，尝试操作一下，加深对这个两个操作的理解就好办了！