计算二叉排序树两个结点间的结点数

13、在一棵高度为O(logn)的二叉排序树的结点上存储着浮点数，请用C语言写一个函数来计算一棵树上界于任意俩个浮点数x1和x2 (x1<x2)之间的结点数。说明你的算法的计算复杂度，算法计算复杂度越低越好。 这个题我扩展到更一般情况，可求二叉树两个结点间的结点数。（或者求二叉树两个结点间的路径，或者求二叉树两个结点的最近公共祖先） #include<iostream> #include<cstdlib> using namespace std; typedef struct BTNode { int data; struct BTNode *lchild; struct BTNode *rchild; }BTNode; //二叉排序树插入结点 int BSTInsert(BTNode * &p, int num) { if(p == NULL) { p = (BTNode*)malloc(sizeof(BTNode)); p->data = num; p->lchild = p->rchild = NULL; return 1; }else { if(p->data == num) return 0; else if(num < p->data) return BSTInsert(p->lchild, num); else return BSTInsert(p->rchild, num); } } //找到根节点到指定num结点的路径 path里存的是路径 count是数组长度，即路径长度 int find_print(BTNode *p, int num, int path[], int level, int &count) { if(p!=NULL) { path[level-1] = p->data; if(num == p->data) { count = level; return 1; } if(find_print(p->lchild, num, path, level+1, count)) return 1; return find_print(p->rchild, num, path, level+1, count); }else{ return 0; } } //打印路径 void show_arr(int a[], int len) { int i; for(i=0; i<len; ++i) cout<<a[i]<<" "; cout<<endl; } int main() { int arr[] = {12, 15, 5, 9, 3, 49, 25, 66, 19, 21}; BTNode *root=NULL; int i, len=sizeof(arr)/sizeof(arr[0]); for(i=0; i<len; ++i) { BSTInsert(root, arr[i]); } int path1[len], path2[len]; int cout1, cout2; find_print(root, 3, path1, 1, cout1); find_print(root, 21, path2, 1, cout2); //打印根结点到3的路径 show_arr(path1, cout1); //打印根结点到21的路径 show_arr(path2, cout2); //找到最近的公共祖先 for(i=0; i<cout1 && i<cout2; ++i) if(path1[i] != path2[i]) break; //因为i指向的是最近公共祖先的数组下标，实际长度应该i+1 //++i; int result = cout1-i+cout2-i+1; 和下面是等价的 int result = cout1-i+cout2-i-1; cout<<"结果为："<<result<<endl; return 0; }