毕设做网站太简单/网站建设的流程及步骤

最近公共祖先问题：
情况1：二叉树是个二叉查找树，且root和两个节点的值(a, b)已知。

如果该二叉树是二叉查找树，那么求解LCA十分简单。

基本思想为：从树根开始，该节点的值为t，如果t大于t1和t2，说明t1和t2都位于t的左侧，所以它们的共同祖先必定在t的左子树中，从t.left开始搜索；如果t小于t1和t2，说明t1和t2都位于t的右侧，那么从t.right开始搜索；如果t1<=t<= t2，说明t1和t2位于t的两侧（或t=t1，或t=t2），那么该节点t为公共祖先。
代码如下：

#include<iostream>
#include<string>
using namespace std;
struct BinaryTree
{int value;struct BinaryTree *pLeft,*pRight;
};
BinaryTree * createSearchTree(int a[],int lo,int hi)//创建二叉搜索树,基于二叉查找算法
{
//  int lo = 0,hi = n-1;BinaryTree *p = NULL;if (lo < hi){int mid = (lo+hi)/2;p = (BinaryTree *)malloc(sizeof(BinaryTree));p->value = a[mid];p->pLeft = createSearchTree(a,lo,mid-1);p->pRight = createSearchTree(a,mid+1,hi);}return p;
}
BinaryTree *lca(BinaryTree *p,int value1,int value2)//lca算法
{BinaryTree *pNode = p;while (pNode != NULL){if (pNode->value > value1 && pNode->value > value2)pNode = pNode->pLeft;else if (pNode->value < value1 && pNode->value pNode = pNode->pRight;else{return pNode;}}return NULL;
}
int main()
{int a[] = {1,2,3,4,5,6};BinaryTree *p = createSearchTree(a,0,5);BinaryTree *pp = lca(p,1,6);cout << pp->value;cout << endl;return 0;
}

情况2：普通二叉树，root未知，但是每个节点都有parent指针。

基本思想：分别从给定的两个节点出发上溯到根节点，形成两条相交的链表，问题转化为求这两个相交链表的第一个交点，即传统方法：求出linkedList A的长度lengthA， linkedList B的长度LengthB。然后让长的那个链表走过abs(lengthA-lengthB)步之后，齐头并进，就能解决了
代码如下：

int getLength(bstNode *pNode)
{int length = 0;bstNode *pTemp = pNode;int count = 0;while (pTemp != NULL){count++;pTemp = pTemp->pParent;}return count;
}
bstNode * Lcal(bstNode *pNode1,bstNode *pNode2)
{//pNode1,pNode2为给定的两个节点int len1 = getLength(pNode1);int len2 = getLength(pNode2);int k = 0;bstNode *iter1 = NULL;bstNode *iter2 = NULL;if (len1 <= len2){bstNode *pTemp = pNode2;while (len2-len1>k)//这里注意下，局部变量的使用{k++;pTemp = pTemp->pParent;}iter1 = pNode1;iter2 = pTemp;}else{k = 0;bstNode *pTemp = pNode1;while (len1-len2 > k){k++;pTemp = pTemp->pParent;}iter1 = pTemp;iter2 = pNode2;}//bstNode *iter1 = pNode1;//bstNode *iter2 = pNode2;while (iter1&&iter2 && iter1 != iter2){iter1 = iter1->pParent;iter2 = iter2->pParent;}return iter1;
}