二叉树中两个节点的最短路径

二叉树中两个节点的最短路径

步骤：求节点6到4的最短路径
1、采用后续遍历的方式求出根节点分别到两个节点的距离路径：1->3->6;1->2->4;
2、最近公共祖先：1
3、第一个路径从后往前输出且包含公共祖先，第二个路径从最近公共祖先+1开始从前往后输出。

#include 

#include
using namespace std;
//#define MaxSize 50
#include
typedef int ElemType;
typedef struct BiTNode{
int data;
BiTNode	*left;
BiTNode *right;
BiTNode(){this->right = NULL; this->left = NULL;}

}BiTNode,*BiTree;

typedef struct {
BiTree t;
int tag;	
}stack;
//后续遍历求路径 
void findshortpath(BiTree root,stack s[],BiTNode *p,int &top){
//static int top=0;
BiTNode *bt=root;

while(bt!=NULL||top>0){
	while(bt!=NULL&& bt!=p){
		s[++top].t=bt;
		s[top].tag=0;
		bt=bt->left;
	}
	if(bt==p){
		s[++top].t=bt;
		return ;
	}
	while(top!=0&&(s[top].tag==1||s[top].t->right==NULL)){
		top--;
	}
	if(top!=0){
	     s[top].tag=1;
		 bt=s[top].t->right;	
	}
	
}
	
}
  
int main(){
//构建一颗从1->6编号的顺序二叉树 
stack s[6]={NULL};BiTNode *p;
stack s1[6]={NULL};
BiTNode *n6= (BiTNode*)malloc(sizeof(BiTNode));
n6->data=6;
BiTNode *n5= (BiTNode*)malloc(sizeof(BiTNode));
n5->data=5;
BiTNode *n4= (BiTNode*)malloc(sizeof(BiTNode));
n4->data=4;
n4->left=NULL;n4->right=NULL;
BiTNode *n3= (BiTNode*)malloc(sizeof(BiTNode));
n3->data=3;
n3->left=n6;
BiTNode *n2= (BiTNode*)malloc(sizeof(BiTNode));
n2->data=2;
n2->left=n4;
n2->right=n5;
BiTNode *n1= (BiTNode*)malloc(sizeof(BiTNode));
n1->data=1;
n1->left=n2;
n1->right=n3;
p=n6;
BiTNode* q=n4;
n5->left=NULL;n5->right=NULL;
n6->left=NULL;n6->right=NULL;
int top=0;int top1=0;
//调用2次求路径 
findshortpath(n1,s,p,top);
findshortpath(n1,s1,q,top1);

//寻找最近公共祖先 
int common=1;
for(int i=1;i<=min(top,top1);i++){
	if(s[i].t==s1[i].t){
		common=i;
	}
}
//开始输出路径 
for(int j=top;j>=common;j--){
cout<<s[j].t->data<<endl;	
}	

for(int j=common+1;j<=top1;j++){
cout<<s1[j].t->data<<endl;	
}
	
}
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

运行结果：