6.4.2 二叉树其它操作算法举例

　五、在二叉树上查询某个结点

　　假设给定一个和二叉树中数据元素有相同类型的值，在已知二叉树中进行查找，若存在和给定值相同的数据元素，则返回函数值为 TRUE，并用引用参数返回指向该结点的指针；否则返回函数值为 FALSE。

　　算法的基本思想为：
　　1) 若二叉树为空树，则二叉树上不存在这个结点，返回 FALSE；否则和根结点的元素进行比较，若相等，则找到，即刻返回指向该结点的指针和函数值 TRUE，从而查找过程结束；2) 否则在左子树中进行查找，若找到，则返回 TRUE；3) 否则返回在右子树中进行查找的结果。因为右子树上查找的结果即为整个查找过程的结果，即若找到，返回的函数值为 TRUE，并且已经得到指向该结点的指针，否则返回的函数值为 FALSE。

算法 算法 6.7
　　bool Locate (BiTree T, ElemType x, BiTree &p)
　{
　　// 若二叉树中存在和 x 相同的元素，则 p 指向该结点并返回 TRUE，
　　// 否则 p = NULL 且返回 FALSE
　　if (!T)
　　{ p = NULL; return FALSE; }　　　　　　// 空树中不存在这样的结点
　　else {
　　　if (T->data==x)
　　　{ p = T; return TRUE; }　　　　　　　// 找到所求结点 else
　　　if (Preorder(T->Lchild,x,p))
　　　　return TRUE;　　　　　　　　　　　 // 在左子树中找到所求结点
　　　else return(Preorder(T->Rchild,x,p)); // 返回在右子树中查找的结果
　　} // else
　}
　

   　　

　
　　和其它结构一样，欲在已知结构中查询某个特定的数据元素，只需对此结构进行"遍历"即可，对于二叉树而言，沿任何一条搜索路径(包括层次遍历的搜索路径)进行搜索均可。若采用先左后右的搜索路径显然进行先序遍历最为直截了当。
　
　　你可能会想这个算法没有必要写得这么复杂，就对二叉树进行一遍遍历，遍历过程中判别是否存在这样的数据元素不就行了吗？那么下列算法是否正确？
算法
　void locate(BiTree T,ElemType x,BiTree& p)
{
　// 若二叉树 T 中存在和 x 相同的元素，
　// 则 p 指向该结点，否则 p = NULL
　if (!T) p=NULL;
　else {
　　if (T->data==x) p=T;
　　locate(T->lchild, x, p);
　　locate(T->rchild, x, p);
　}
}
  
  算法
　void locate(BiTree T,ElemType x,BiTree& p)
{
　// 若二叉树 T 中存在和 x 相同的元素，则 p 指向
　// 该结点，否则 p 的值不变，p 的初值为 NULL
　if (T)
　{ if (T->data==x) p=T;
　　locate(T->lchild, x, p);
　　locate(T->rchild, x, p);
　}// if
} 		  　　上面的这个算法不正确，不论二叉树中是否存在这个数据元素，最后返回的指针 p 都是"NULL"。应该修改成如左算法。

　
　　你只要仔细对比这两个算法的差异就能明白为什么上面这个算法是错的。