先序建立二叉树中查找孩子返回双亲那快函数怎么执行都是显示找不到双亲。大佬帮看看是我哪写错了呗。以下是完整代码:
#include
#include
#include
using namespace std;
typedef char DataType;
typedef struct BitNode
{
DataType data;
struct BitNode lchild,*rchild; //创建左右节点
}*BitTree;
/初始化一个二叉树*/
void Init(BitTree &BT)
{
BT = (BitTree)malloc(sizeof(BitNode));
BT->data = NULL;
return;
}
//先序建立二叉树
int BinTreeCreate(BitTree &BT)
{
char ch;
scanf("%c", &ch);
if(ch == '$') BT = NULL;
else{
BT = (BitTree)malloc(sizeof(BitNode));
BT->data = ch;
BinTreeCreate(BT->lchild);
BinTreeCreate(BT->rchild);
}
return 0;
}
/*判断二叉树是否为空*/
bool BinTreeEmpty(BitTree BT)
{
if(BT == NULL) return true;
return false;
}
/*先序遍历二叉树*/
void BinTraverse(BitTree BT)
{
if(BT == NULL) return;
printf("%c",BT->data);
if(BT->lchild != NULL)
BinTraverse(BT->lchild);
if(BT->rchild != NULL);
BinTraverse(BT->rchild);
}
/*中序遍历二叉树*/
void MidTraverse(BitTree BT)
{
if(BT == NULL)return;
MidTraverse(BT->lchild);
printf("%c",BT->data);
MidTraverse(BT->rchild);
}
/*后序遍历二叉树*/
void BhTraverse(BitTree BT)
{
if(BT == NULL)return;
BhTraverse(BT->lchild);
BhTraverse(BT->rchild);
printf("%c",BT->data);
}
/*q求二叉树结点数*/
int BinTreeCount(BitTree BT)
{
int cnt;
if(BT)
{
int cntLeft = BinTreeCount(BT->lchild);
int cntRight = BinTreeCount(BT->rchild);
cnt = cntLeft + cntRight + 1;//左子树的结点数加上右子树的结点数
}
else cnt = 0;
return cnt;
}
/*查找孩子返回双亲*/
BitTree back(BitTree T , char str){
if(T == NULL) return NULL ;
if(T->lchild!= NULL&&T->lchild->data == str) {
return T;
}
if(T->rchild!= NULL&&T->rchild->data == str){
return T;
}
else{
// back(T->lchild,str);
// back(T->rchild,str);
BitNode* P=NULL;
if(P=back(T->lchild,str))
return P;
if(P=back(T->rchild,str))
return P;
}
return NULL;
}
int main(){
BitTree BT;
printf("<------欢迎使用二叉树系统------->\n");
printf("<------1.初始化二叉树----------->\n");
printf("<------2.先序建立二叉树--------->\n");
printf("<------3.判断二叉树是否为空----->\n");
printf("<------4.先序遍历二叉树--------->\n");
printf("<------5.中序遍历二叉树--------->\n");
printf("<------6.后序遍历二叉树--------->\n");
printf("<------7.求二叉树结点数--------->\n");
printf("<------8.查找孩子返回双亲------->\n");
printf("<------9.退出------------------->\n");
while(1){
int choose;
char ch;
BitTree T = NULL;
BitTree p = NULL;
printf("请输入选择:");
scanf("%d",&choose);
if(choose == 9)break;
switch(choose)
{
case 1:
Init(BT);
break;
case 2:
printf("请输入二叉树的元素:");
getchar();
BinTreeCreate(BT);
break;
case 3:
if(BinTreeEmpty(BT)) printf("二叉树为空!\n");
else printf("二叉树不为空!\n");
break;
case 4:
printf("先序遍历二叉树序列如下:");
BinTraverse(BT);
printf("\n");
break;
case 5:
printf("中序遍历二叉树序列如下;");
MidTraverse(BT);
printf("\n");
break;
case 6:
printf("后序遍历二叉树序列如下:");
BhTraverse(BT);
printf("\n");
break;
case 7:
printf("二叉树的结点数为 %d\n", BinTreeCount(BT));
break;
case 8:
printf("\n请输入要查找的值:");
getchar();
scanf("%c",&ch);
back(T,ch);
if(T==NULL){
printf("输入的值不存在双亲!!\n");
}
else{
printf("输入结点的双亲为:%c",T);
}
break;
}
}
return 0;
}