6-01 2,412 views
求解思路：
采用递归，深度优先遍历，找到一个节点时，返回，逐层记录遍历方向，另一个节点
同，这样深度优先遍历后，可以找到这两个节点由根节点访问的路径，然后沿着这个
路径找到分叉的地方就行了
代码：
|
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 |
#include <stdlib.h> #include <stdio.h> typedef struct TNode { int data; int pathA; int pathB; TNode* lchild; TNode* rchild; }TNode,*BTree; //采用递归进行深度优先遍历 //计算出路径 int traverse(BTree t,int x,int flag) { if (t == NULL) return 0; if (t->data == x) return 1; if (traverse(t->lchild,x,flag)==1) { if (flag == 1) t->pathA = 1; else t->pathB = 1; return 1; } if (traverse(t->rchild,x,flag)==1) { if (flag == 1) t->pathA = 2; else t->pathB = 2; return 1; } } int main() { BTree tree = (BTree)malloc(sizeof(TNode)); tree->data = 1; tree->pathA = 0; tree->pathB = 0; tree->lchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->data = 2; tree->lchild->pathA = 0; tree->lchild->pathB = 0; tree->rchild = (TNode*)malloc(sizeof(TNode)); tree->rchild->data = 3; tree->rchild->pathA = 0; tree->rchild->pathB = 0; tree->rchild->lchild = NULL; tree->rchild->rchild = NULL; tree->lchild->lchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->lchild->data = 4; tree->lchild->lchild->pathA = 0; tree->lchild->lchild->pathB = 0; tree->lchild->lchild->lchild = NULL; tree->lchild->lchild->rchild = NULL; tree->lchild->rchild = (TNode*)malloc(sizeof(TNode)); tree->lchild->rchild->data = 5; tree->lchild->rchild->pathA = 0; tree->lchild->rchild->pathB = 0; tree->lchild->rchild->lchild = NULL; tree->lchild->rchild->rchild = NULL; int a,b; printf("please input a,b:"); scanf("%d %d",&a,&b); if (traverse(tree,a,1)!=1) printf("no a"); if (traverse(tree,b,2)!=1) printf("no b"); //从根节点开始向下遍历，找到路径分叉点 TNode* node = tree; while(node&&(node->pathA==node->pathB)) { if (node->pathA == 1) node = node->lchild; else node = node->rchild; } printf("the common father node is:%d",node->data); return 0; } |
示例：
please input a,b:4 3
the common father node is:1