|
这棵树的前序遍历结果是：1 2 4 0 0 5 0 0 3 6 0 8 0 0 7 0 0
前序建立二叉树：
void buildTree(Node *&root)
{
int num;
scanf("%d",&num);
if(num==0)
{
root=NULL;
return;
}
root=new Node;
root->data=num;
buildTree(root->lchild);
buildTree(root->rchild);
}
Node *getPublicParetnNode(Node *root,int n1,int n2) {
if(root==NULL) return NULL;
if(root->data==n1||root->data==n2)
return root;//返回当前结点的原因是我们找到了要找的子结点，在回传的过程中两个结点会聚到一起，返回。
Node *lNode=getPublicParetnNode(root->lchild,n1,n2);
Node *rNode=getPublicParetnNode(root->rchild,n1,n2);
if(!lNode&&!rNode) return NULL;
else if(lNode&&rNode) return root;
else return lNode==NULL?rNode:lNode;
}
//这个算法 考虑不全面，只是考虑到了 两个结点都在树中的情况，如果 一个结点没有在树中 就出错了
//=========================二叉树中两个节点的最低祖先结点========================================
/*
查找二叉树中两个节点的最低祖先节点（或最近公共父节点等）
如果给定pRoot是NULL，即空树，则返回的公共节点自然就是NULL；
如果给定pRoot与两个节点中任何一个相同，说明，pRoot在就是所要找的两个节点之一，则直接返回pRoot，
表明在当前链路中找到至少一个节点； 如果给定pRoot不是两个节点中任何一个，
则说明，需要在pRoot的左右子树中重新查找，此时有三种情况：
两个节点都在左子树上； 两个节点都在右子树上；一个在左子树，一个在右子树上；
具体来说，就是：
情况一：如果左子树查找出的公共节点是NULL，则表明从左子树根节点开始到左子树的所有叶子节点等所有节点中，
没有找到两个节点中的任何一个，这就说明，这两个节点不在左子树上，不在左子树，则必定在右子树上；
情况二：如果右子树查找的公共节点是NULL，说明在右子树中无法找到任何一个节点，则两个节点必定在左子树上；
情况三： 如果左右子树查找的公共节点都不是NULL，说明左右子树中各包含一个节点，
则当前节点pRoot就是最低公共节点，返回就可以了。
三种情况是互斥的， 只能是其中之一。
*/
BiNode *get_comm_parent(BiNode *root,BiNode *node1,BiNode *node2)
{
if(root==NULL) return NULL;
if(root==node1||root==node2) return root;//表示这个顶点就是要找的公共点
BiNode *lnode=get_comm_parent(root->lchild,node1,node2); //在左子树中查找是否有相应的结点
BiNode *rnode=get_comm_parent(root->rchild,node1,node2); //在左子树中查找是否有相应的结点
if(lnode==NULL)
return rnode;
if(rnode==NULL)
return lnode;
return root;
}
| 
转播
