以二叉链表为存储结构,如何编写算法求二叉树中结点x的双亲？

Question

如题所述

Answer 1

如下代码是通过算法的方式求父节点，其中二叉树的创建是先序方式，如abd##e##c##\x0d\x0a\x0d\x0a#include "stdlib.h"\x0d\x0atypedef int Element;\x0d\x0astruct Tree\x0d\x0a{ \x0d\x0a Element data;\x0d\x0a struct Tree *left; \x0d\x0a struct Tree *right;\x0d\x0a};\x0d\x0a\x0d\x0avoid CreateBinSortTree(struct Tree **t);\x0d\x0avoid InsertNode2Tree(struct Tree **root, Element num);\x0d\x0avoid PrintTree(struct Tree *r, int order);\x0d\x0astruct Tree *FindParent(struct Tree *r, char ch);\x0d\x0a\x0d\x0aint main(int argc, char* argv[])\x0d\x0a{\x0d\x0a printf("请输入一组字母(#表示子树为空)\n");\x0d\x0a struct Tree *t=NULL;\x0d\x0a CreateBinSortTree(&t);\x0d\x0a printf("\n根左右:");\x0d\x0a PrintTree(t,1);\x0d\x0a printf("\n左根右:");\x0d\x0a PrintTree(t,2);\x0d\x0a printf("\n左右根:");\x0d\x0a PrintTree(t,3);\x0d\x0a printf("\n");\x0d\x0a char ch='a';\x0d\x0a getchar();//获取前次输入回车符\x0d\x0a printf("请输入节点数据值");\x0d\x0a scanf("%c",&ch);\x0d\x0a struct Tree *temp = FindParent(t,ch);\x0d\x0a if (temp!=NULL)\x0d\x0a {\x0d\x0a printf("其父节点数据值为:%c",temp->data);\x0d\x0a }\x0d\x0a else\x0d\x0a {\x0d\x0a printf("找不到父节点");\x0d\x0a }\x0d\x0a return 0;\x0d\x0a \x0d\x0a}\x0d\x0avoid CreateBinSortTree(struct Tree **t)\x0d\x0a{ \x0d\x0a char ch;\x0d\x0a ch = getchar(); \x0d\x0a if (ch == '#') \x0d\x0a { \x0d\x0a *t = NULL; \x0d\x0a return ; \x0d\x0a }\x0d\x0a *t = (struct Tree *)malloc(sizeof(struct Tree)); \x0d\x0a (*t)->data = ch;\x0d\x0a CreateBinSortTree( &((*t)->left)); \x0d\x0a CreateBinSortTree( &((*t)->right));\x0d\x0a \x0d\x0a}\x0d\x0a\x0d\x0avoid PrintTree(struct Tree *r, int order)\x0d\x0a{ \x0d\x0a if (r == NULL) \x0d\x0a { \x0d\x0a return ; \x0d\x0a }\x0d\x0a switch(order)\x0d\x0a { \x0d\x0a case 1: \x0d\x0a printf("%c ",r->data);\x0d\x0a PrintTree(r->left,order); \x0d\x0a PrintTree(r->right,order); \x0d\x0a break;\x0d\x0a case 2: \x0d\x0a PrintTree(r->left,order); \x0d\x0a printf("%c ",r->data); \x0d\x0a PrintTree(r->right,order); \x0d\x0a break; \x0d\x0a case 3: \x0d\x0a PrintTree(r->left,order); \x0d\x0a PrintTree(r->right,order); \x0d\x0a printf("%c ",r->data); \x0d\x0a break; \x0d\x0a }\x0d\x0a}\x0d\x0a\x0d\x0astruct Tree *FindParent(struct Tree *r, char ch)\x0d\x0a{\x0d\x0a if (r==NULL)\x0d\x0a {\x0d\x0a return NULL;\x0d\x0a }\x0d\x0a if (r->left != NULL)\x0d\x0a {\x0d\x0a if (r->left->data == ch)\x0d\x0a {\x0d\x0a return r;\x0d\x0a }\x0d\x0a }\x0d\x0a if (r->right != NULL)\x0d\x0a {\x0d\x0a if (r->right->data == ch)\x0d\x0a {\x0d\x0a return r;\x0d\x0a }\x0d\x0a }\x0d\x0a struct Tree *t=FindParent(r->left,ch);\x0d\x0a if (t != NULL)\x0d\x0a {\x0d\x0a return t;\x0d\x0a }\x0d\x0a t = FindParent(r->right,ch);\x0d\x0a return t;\x0d\x0a}