题目:判断一个节点是否在一棵二叉树中
结点定义如下
struct BinaryTree
{
BinaryTree(char data)
:_pLeft(NULL)
, _pRight(NULL)
, _data(data)
{}
BinaryTree *_pLeft;
BinaryTree *_pRight;
char _data;
};
首先附上创建树代码
void CreateBinaryTree(BinaryTree *&pRoot, char *str,size_t size, size_t &index)
{
if (index < size && str[index] != '#')
{
pRoot = new BinaryTree(str[index]);
CreateBinaryTree(pRoot->_pLeft, str, size, ++index);
CreateBinaryTree(pRoot->_pRight, str, size, ++index);
}
}
思路:判断当前结点与查找的结点是否相等,如果不相等寻找左子树,继而寻找右子树,这样用递归很容易实现
bool IsNodeInTree(BinaryTree *pRoot,BinaryTree *pNode)
{
if (NULL == pRoot || NULL == pNode)
return false;
if (pRoot->_data == pNode->_data)
return true;
if (IsNodeInTree(pRoot->_pLeft, pNode) || IsNodeInTree(pRoot->_pRight, pNode))
return true;
return false;
}
void funtest()
{
BinaryTree *pRoot;
char *str = "abdh###e##cf##g#i";
size_t index = 0;
CreateBinaryTree(pRoot, str, strlen(str), index);
BinaryTree *node = pRoot->_pLeft;
cout << node->_data << " ";
bool ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pLeft->_pLeft;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pLeft->_pLeft;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pLeft->_pRight;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pRight;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pRight->_pLeft;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pRight->_pRight;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = pRoot->_pRight->_pRight->_pRight;
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = new BinaryTree('n');
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
node = new BinaryTree('e');
cout << node->_data << " ";
ret = IsNodeInTree(pRoot, node);
cout << ret << endl;
ret = IsNodeInTree(pRoot, NULL);
cout << ret << endl;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)