求节点x在二叉树中的双亲结点

设计一个求节点x在二叉树中的双亲结点算法。

 1 typedef int TElemType;
 2 typedef struct BiTNode
 3 {
 4     TElemType data;
 5     struct BiTNode *lchild, *rchild;
 6 }BiTNode, *BiTree;
 7 
 8 /*
 9 设计思路：以先序遍历二叉树的方法，从根结点出发，
10          1、如果左子树等于x结点，则返回根结点，否则，递归查找左子树，直到找到x或者树为空。
11          2、如果右子树等于x结点，则返回根结点，否则，递归查找右子树，直到找到x或者树为空。
12 */
13 BiTNode *find_parents(BiTree T, BiTNode node)
14 {
15     BiTNode *parents = NULL;
16     if (!T) return parents;
17 
18     if (T->lchild && !parents) {
19         if (T->lchild->data == node.data) {
20             parents = T;
21         } else {
22             parents = find_parents(T->lchild, node);//递归查找左子树，这里不能直接返回，否则就不会遍历右子树
23         }
24     }
25 
26     if (T->rchild && !parents) {
27         if (T->rchild->data == node.data) {
28             parents = T;
29         } else {
30             parents = find_parents(T->rchild, node);//递归查找右子树
31         }
32     }
33 
34     return parents;
35 }

2021-11-18

13:59:33