二叉树结点的共同祖先问题

【问题描述】假设二叉树采用二叉链表方式存储，root指向根结点，p所指结点和q所指结点为二叉树中的两个不同结点，且互不成为根到该结点的路径上的点，编程求解距离它们最近的共同祖先。
【输入形式】二叉树的前序和中序遍历序列，用以创建该二叉树的链式存储结构；以及二叉树的两个结点数据 x 和 y
【输出形式】结点数据值为 x 和结点数据值为 y 的最近的共同祖先，若没有共同祖先则输出NULL
【样例输入】
GABDCEF
BDAEFCG
DF
【样例输出】
A

 1  2019/6/10 22:37:28
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define N 20
 5 typedef struct Tree{
 6 
 7       char data;
 8       struct Tree *LeftChild;
 9       struct Tree *RightChild;
10 }BiTNode , *BiTree;
11 BiTree  Only(char *pre,char *in,int length){ //根据前序序列和中序序列唯一确定一个二叉树
12                 BiTree  root;
13                 root=(BiTree)malloc(sizeof(BiTNode));
14                 root->data=*pre;
15                 int index;
16                 if(length==0){ return 0;} //哇哦 这句话真是重中之重
17                 for(index=0;index<length;index++){
18                          if(root->data==in[index]){
19                                break;
20                          }
21                 } //到了中序序列第几号元素:index==根节点==前序序列第一个元素
22 
23                 //递归 开始找根节点的左子树------的根节点
24                root->LeftChild=Only(pre+1,in,index);
25                  //递归 开始找根节点的右子树-------的根节点
26                root->RightChild=Only(pre+1+index,in+index+1,length-index-1);
27                return root;
28 }
29 
30 bool Cover(BiTree root,char pt){
31 
32         if(root==NULL) { return false;}
33         if(root->data==pt){
34                return true;
35         }else{
36                 return Cover(root->LeftChild,pt)||Cover(root->RightChild,pt) ;
37         }
38 }
39 BiTree SearchCommen(BiTree node,char pt1, char pt2){
40 
41 
42             if(node==NULL){ return NULL;} //没有找到或者node压根就是个空的 返回null；
43             if(node->data==pt1||node->data==pt2){ return NULL;}//一个元素和根节点元素撞了，另一个是子元素，二者没有共同祖先
44 
45             //两个元素都是正常的子节点的元素
46             //先在根节点的左子树里面找两个元素
47             bool t1=Cover(node->LeftChild,pt1);//leftchild   pt1
48             bool t2=Cover(node->LeftChild,pt2);//leftchild  pt2
49 
50             if(t1!=t2) { return node;} //两个元素 一个在左边找到了 一个没找到 证明一左一右 所以祖先就是node
51               else{
52                 //t1=t2   如果都等于true 就是两个元素都在左子树这边 所以往下循环就好
53                 if(t1==true) { return SearchCommen(node->LeftChild,pt1,pt2);}
54                 //t1=t2   如果都等于No 证明没有在左子树找到，那么就一定在右子树
55                 if(t2==true) { return SearchCommen(node->RightChild,pt1,pt2);}
56               }
57 }
58 
59 int main(){
60     BiTree pt;
61     /*假设二叉树采用二叉链表方式存储*/
62      char pre[N];
63      char in[N];
64      char *preo=pre;
65      char *ino=in;
66      char ch1,ch2;
67      int length;
68      cout<<"输入前序序列";
69      cin>>pre;
70      cout<<endl;
71      cout<<"输入中序序列";
72      cin>>in;
73      cout<<endl;
74      length=strlen(pre);
75      pt=Only(pre,in,length);
76 
77      cin>>ch1>>ch2;
78      pt=SearchCommen(pt,ch1,ch2);
79      if(pt){ cout<<pt->data;}
80      else{ cout<<"NULL";}
81 }