二叉树指定两个结点共同的祖先
发布网友
发布时间：2022-05-29 06:18
共1个回答
热心网友
时间：2023-10-09 09:05
int FindLowestCommonAncestor(node *root, int value1, int value2)
{
int larger, smaller;
larger = (value1 > value2)? value1:value2;
smaller = (value1 > value2)? value2:value1;
node *curNode = root;
node *curFather = root;
while(curNode){
if(curNode->data == larger || curNode->data == smaller)
return curFather->data;
else if(curNode->data > larger){
curFather = curNode;
curNode = curNode->left;
}
else if(curNode->data < smaller){
curFather = curNode;
curNode = curNode->right;
}
else return curNode->data;
}
}//
/
/
/
/
/
/
C语言实现：
/*二叉排序树的生成及树，任意两结点的最低公共祖先 Amirural设计*/
#include <stdio.h>
#define null 0
int counter=0;
typedef struct btreenode
{int data;
struct btreenode *lchild;
struct btreenode *rchild;
}bnode;
bnode *creat(int x,bnode *lbt,bnode *rbt) //生成一棵以x为结点，以lbt和rbt为左右子树的二叉树
{bnode *p;
p=(bnode*)malloc(sizeof(bnode));
p->data=x;
p->lchild=lbt;
p->rchild=rbt;
return(p);
}
bnode *ins_lchild(bnode *p, int x) //x作为左孩子插到二叉树中
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->lchild!=null) //若p有左孩子，则将原来的左孩子作为结点x的右孩子
q->rchild=p->lchild;
p->lchild=q;
}
return(p);
}
bnode *ins_rchild(bnode *p, int x) //x作为右孩子插入到二叉树
{bnode *q;
if(p==null)
printf("Illegal insert.");
else
{q=(bnode*)malloc(sizeof(bnode));
q->data=x;
q->lchild=null;
q->rchild=null;
if(p->rchild!=null) //若x有右孩子，则将原来的右孩子作为结点x的的左孩子
q->lchild=p->rchild;
p->rchild=q;
}
return(p);
}
void prorder(bnode *p)
{if(p==null)
return;
printf("%d\t%u\t%d\t%u\t%u\n",++counter,p,p->data,p->lchild,p->rchild);
if(p->lchild!=null)
prorder(p->lchild);
if(p->rchild!=null)
prorder(p->rchild);
}
void print(bnode *p) //嵌套括号表示二叉树，输出左子树前打印左括号，
{ //输出右子树后打印右括号。
if(p!=null)
{printf("%d",p->data);
if(p->lchild!=null||p->rchild!=null)
{printf("(");
print(p->lchild);
if(p->rchild!=null)
printf(",");
print(p->rchild);
printf(")");
}
}
}
int FindLowestCommonAncestor(bnode *root, int value1, int value2)
{
bnode *curnode = root;
while(1)
{
if (curnode->data>value1&&curnode->data>value2)
curnode = curnode->lchild;
else if(curnode->data<value1&&curnode->data<value2)
curnode = curnode->rchild;
else
return curnode->data;
}
}
main()
{
bnode *bt,*p,*q;
int x,y,v1,v2;
printf("输入根结点：");
scanf("%d",&x);
p=creat(x,null,null);
bt=p; //使bt p都指向根结点
printf("输入新的结点值：");
scanf("%d",&x);
while(x!=-1)
{p=bt;
q=p;
while(x!=p->data&&q!=null) //q记录当前根结点
{p=q;
if(x<p->data)
q=p->lchild;
else
q=p->rchild;
}
if(x==p->data)
{printf("元素%d已经插入二叉树中！\n",x);
}
else
if(x<p->data) ins_lchild(p,x);
else ins_rchild(p,x);
scanf("%d",&x);
}
p=bt;
printf("struct of the binary tree:\n");
printf("number\taddress\tdata\tlchild\trchild\n");
prorder(p);
printf("\n");
printf("用括号形式输出二叉树:");
print(p);
printf("\n请任意输入树中存在的两个结点:");
scanf("%d,%d",&v1,&v2);
y = FindLowestCommonAncestor(p, v1, v2);
printf("输出%d和%d的最低公共祖先：",v1,v2);
printf("%d\n",y);
}
运行结果：
输入根结点：20
输入新的结点值：8 22 4 12 10 14 -1 （以-1结束结点的输入）
struct of the binary tree:
number addresss data lchild rchild
1 4391168 20 4391104 4391040
2 4391104 8 4390976 4399072
3 4390976 4 0 0
4 4399072 12 4399008 4398944
5 4399008 10 0 0
6 4398644 14 0 0
7 4391040 22 0 0
用括号形式输出：20(8(4,12(10,14)),22) （输出左子树打印左括号，输出右子树后打印括号）
请任意输入树中存在的两个结点：4，14
输出4和14的最低祖先：8
