c++ 二叉树中搜索节点

问题描述

创建了一个二叉树，希望搜索到给定info值的节点，

以下为二叉树的相关结构类型定义：

#include 'stdio.h'#include'stdlib.h'#include 'iostream'using namespace std;typedef char ELEMTYPE;#define number 20;struct BinTreeNode;typedef struct BinTreeNode* PBinTreeNode;struct BinTreeNode{ ELEMTYPE info; PBinTreeNode lchild; PBinTreeNode rchild;};typedef struct BinTreeNode* PLNBinTree;

以下为创建二叉树算法：root为已创建好的BinTreeNode类型节点,然后输入一个字符测试是否左子树/右子树为空，不为空则创建左子树/右子树

void constructBinTree(PLNBinTree root)//先根递归创建二叉树{ if (root == NULL)return; char temp = ’0’; cout << '输入左值'; cin >> temp; if (temp == ’#’) {root->lchild = NULL; } else {root->lchild = new BinTreeNode;root->lchild->info = temp; } cout << '输入右值'; cin >> temp; if (temp == ’#’) {root->rchild = NULL; } else {root->rchild = new BinTreeNode;root->rchild->info = temp; } constructBinTree(root->lchild); constructBinTree(root->rchild);}

以下为搜索算法：PBinTreeNode find(PLNBinTree root, char x)//寻找x所在位置{

if (root == NULL) return 0;if (root->info == x){ return root; }else return 0;PBinTreeNode c;c = find(root->lchild, x);if(!c) find(root->rchild, x);return c;

}

以下为测试时结果：

找不出问题所在，求各位会的指教。谢谢！

问题解答

constructBinTree()的参数要传引用才行，你这样按值传递，肯定是有问题的root->lchild = new BinTreeNode;这一句只是给一个临时变量root的左孩子new了一对象，但是root所代表的外层指针是没有左孩子的！形参root和其实参指向的是两个不同的内存区域。明白了吗？

https://github.com/bloomsource/rbtree