在树中寻找两个节点的最低公共祖先

 1 //通过寻找从根至节点的路径，取两个节点路径上的最后一个相同的节点，即为最低公共祖先
 2 #include <time.h>
 3 #include <stdlib.h>
 4 #include <vector>
 5 #include "BinarySearchTree.h"
 6 #include <iostream>
 7 using namespace std;
 8 
 9 void printv(const vector<Position>& v)
10 {
11      vector<Position>::const_iterator cit = v.begin();
12      while(cit != v.end())
13           cout<<(*cit)->data<<" ", ++cit;
14      cout<<endl;
15 }
16 //从根开始搜索到某一节点的路径（采用了二叉查找树，但没利用其性质故可以推广至具有任一数量的儿子的树中）
17 bool find_path(BinarySearchTree t, vector<Position>& v, const int x)
18 {
19      if(t != NULL && t->data != x)
20      {
21           v.push_back(t);
22           bool res = (find_path(t->left, v, x) || find_path(t->right, v, x));
23           if(true != res)
24                v.pop_back();
25           return res;
26      }
27      else if(t == NULL)
28           return false;
29      v.push_back(t);
30      return true;
31 }
32 
33 int main(int argc, char const *argv[])
34 {
35      std::vector<Position> v1, v2;
36      BinarySearchTree t = NULL;
37      MakeEmpty(&t);
38      srand((unsigned)time(NULL));
39      for(int i = 0; i != 100; ++i)
40           Insert(rand()%30, &t);
41      PrintTree(t, 2, 0);
42      find_path(t, v1, 8);
43      cout<<"path to 8: ";
44      printv(v1);
45      find_path(t, v2, 15);
46      cout<<"path to 15: ";
47      printv(v2);
48      
49      return 0;
50 }