为什么二叉树的父节点输出为空？

Question

在二叉树中查找某个节点值，如果找到，返回该节点的父节点，否则返回空。以下为代码：

#include<iostream>

#include<string.h>

using namespace std;

 

#define maxsize 100

#define OK 1

#define ERROR 0

#define OVERFLOW -2

 

// char ch;

typedef char TElemType;

/*二叉链表*/

typedef struct BiTNode//创建一个结构体作为二叉树

{

TElemType data;//结点数据域

BiTNode* lchild, * rchild;//左右孩子指针

}BiTNode, * BiTree;

 

void initBiTree(BiTree& T)//二叉树的初始化

{

T = NULL;//二叉树置为空

}

 

void CreateBiTree(BiTree& T)

{//按先序次序输入二叉树的结点值（一个字符），创建二叉链表表示的二叉树T

char ch;

cin >> ch; //扫描字符序列，读入字符ch

if (ch == '#') T = NULL; //递归结束，建空树,输入了n个字符，就要有n+1个#

else //递归创建二叉树

{

T = new BiTNode; //生成根结点

T->data = ch; //根结点数据域置为ch

CreateBiTree(T->lchild);//递归创建左子树

CreateBiTree(T->rchild);//递归创建右子树

}

}

 

BiTree h;

BiTree Search(BiTree& T, char& a)//查找函数

{

if (T)

{

if (T->data == a)

{

cout << "查找成功（根结点）：" << " " << T->data << endl;

return T;

}

else if (T->lchild != NULL && T->lchild->data == a&& T->data != '#')

{

cout << "成功查找父结点：" << " " << T->data << endl;

return T;

}

else if (T->rchild != NULL && T->rchild->data == a&&T->data!='#')

{

cout << "成功查找父结点：" << " " << T->data << endl;

return T;

}

h = Search(T->lchild, a);

if (T->rchild)

{

Search(T->rchild, a);

}

}

int main()

{

//int a, b;

BiTree t;//建一个树t

initBiTree(t);//初始化t

 

cout << "输入一个二叉树(#代表空)：" << endl;

CreateBiTree(t);//创建二叉树t

 

char n = 'E';

//cin >> n;

//cout << n;

cout << endl;

cout << "若输出值只有一个，那么查找值为根结点，否则输出父结点：" << endl;

Search(t, n);//查找n

BiTree m;

m = Search(t, n);

cout << "输出" << m->data;

return 0;

}

Answer 1

我这几天已经弄了出来，可以将search函数改为如下：

BiTree getparent(BiTree T, char& a)
{

	if (T == nullptr)return T;
	if (T->rchild != NULL) { if (T->rchild->data == a)return T; }
	if (T->lchild != NULL) { if (T->lchild->data == a)return T; }
	BiTree left = getparent(T->lchild, a);
	if (left != NULL)return left;
	BiTree right = getparent(T->rchild, a);
	if (right != NULL)  return right;
	return left;
}