1 #include<list>
2 #include<vector>
3 #include<stdlib.h>
4 #include<iostream>
5 #include<algorithm>
6
7 using namespace std;
8
9 struct BinaryTreeNode//二叉树结点类型
10 {
11 char value;
12 BinaryTreeNode* left;
13 BinaryTreeNode* right;
14 };
15
16 void CreatBinaryTree(BinaryTreeNode** pRoot)//创建二叉树
17 {
18 char data;
19 cin>>data;
20 if(data!='.')
21 {
22 *pRoot=new BinaryTreeNode;
23 (*pRoot)->value=data;
24 CreatBinaryTree(&((*pRoot)->left));//创建左子树
25 CreatBinaryTree(&((*pRoot)->right));//创建右子树
26 }
27 else *pRoot=NULL;
28 }
29
30
31
32 bool GetNodePath(BinaryTreeNode* pRoot,char pNode,list<BinaryTreeNode*> &path)//获得结点路径
33 {
34 bool found=false;
35 path.push_back(pRoot);
36 if(pRoot->value==pNode) return true;
37 if(!found&&pRoot->left!=NULL)
38 {
39 found=GetNodePath(pRoot->left,pNode,path);
40 }
41 if(!found&&pRoot->right!=NULL)
42 {
43 found=GetNodePath(pRoot->right,pNode,path);
44 }
45 if(!found)
46 path.pop_back();
47 return found;
48 }
49 char GetLastCommonNode(list<BinaryTreeNode*> &path1,list<BinaryTreeNode*> &path2)//获得最近相同根结点的值
50 {
51 list<BinaryTreeNode*>::iterator ite1=path1.begin();
52 list<BinaryTreeNode*>::iterator ite2=path2.begin();
53 BinaryTreeNode* pLast;
54 while(ite1!=path1.end()&&ite2!=path2.end())
55 {
56 if(*ite1==*ite2)
57 pLast=*ite1;
58 ite1++;
59 ite2++;
60 }
61 return pLast->value;
62 }
63
64 void print(list<BinaryTreeNode*> &path)//打印路径
65 {
66 list<BinaryTreeNode*>::iterator ite;
67 for(ite=path.begin();ite!=path.end();++ite)
68 {cout<<(*ite)->value<<' ';}
69 cout<<endl;
70 }
71
72
73 void main()
74 {
75 BinaryTreeNode* pRoot;
76 CreatBinaryTree(&pRoot);
77 list<BinaryTreeNode*> path1,path2,path3;
78 cout<<"请输入结点字符："<<endl;
79 char s1,s2;
80 cin>>s1>>s2;
81 GetNodePath( pRoot,s1,path1);
82 GetNodePath( pRoot,s2,path2);
83 char common=GetLastCommonNode(path1,path2);
84 GetNodePath( pRoot,common,path3);
85 print(path1);
86 print(path2);
87 print(path3);
88 int distance=path1.size()+path2.size()-2*path3.size();
89 cout<<s1<<" with "<<s2<<" distance is: "<<distance<<endl;
90 }
这个问题很全面的考察了二叉树的相关的知识，建议大家先尝试自己解决分析：假设给定的节点为node1,node2,可以分为下面的两种情况：1）node1是node2的祖先节点或孩子结点，可以理解为两个节点在一条线上。例如：Dist(2,4),Dist(6,1)2）node1和node2没有直接或间接的父子关系。例如，Dist(4,3)，他们需要一个共同的祖先结点1连接起来假设lca是两个节点的最低公共祖先节点：Dist(n1,n2)=Dist(root,n1)+Dist(root,n2)-2*Dist(root,lca)这个公式已经涵盖了上面的两种情况。先找出lca,再求root节点到某个节点的距离就比较简单了。参考代码：