[又一次C++] 这两个程序怎么写。进来讨论，没有重谢！

[陪你去看龙卷风]

omg, you just dont get it.

 

[风中有影]

subRoot->key>=n,等于的情况不是加进去了么,再说我没有看过完整的题目,楼主是说PRINT大于N的情况没说等于N.

 

[陪你去看龙卷风]

read the comment part and codes plz

	void printShittyNodes(TreeNode *r, int toFind)
	{
		if (r != null)//node不为空的情况下
		{
			if ((r->key) >= toFind)//如果parent node大于n ,左右node的key都大于n,因此要同时访问2边
			{ 
				cout << key << endl;
				printShittyNodes(r->left, toFind);
				printShittyNodes(r->right, toFind);
 			} else { //如果parent node小于n
			 //只有当右node不为empty node, and the key of the right node is greater than n
				if ((r->right) != null) //we have to separate these 2 condition, a seq. fault might occur
					if ((r->right)->key) > toFind)
					printShittyNodes(r->right, toFind); 
			}
		}
	}

 

[陪你去看龙卷风]

你的主要问题不是bst search
而是如果走到bottom of the tree
你的subRoot->right->key跟subRoot->left->key一定会有seq. fault的
因为bottom of the tree的时候subRoot->right = null, subRoot->left = null
null pointer -> key 是绝对错误的

bst的结构我已经在前头阐述过了

left node's key < parent node's key < right node's key
parent key如果大于n,逻辑十分明了
{
左边右边subtree都需要访问
}
parent key如果小于n
只要确定right node不是empty node还有key大于n
{
左边是不需要访问的，因为bst的property限制了这一点
只有在上头那个condition确定的情况下，右边subtree才需要访问
}

 

[风中有影]

恩,对,我发现问题了,这样才有进步,呵呵

 

[陪你去看龙卷风]

我现在是真tmd无语了

 

[风中有影]

void TreeNode::subprint (TreeNode *subRoot,int n) {

if(subRoot==NULL) return;

if(subRoot->key>=n){
subPrint (subRoot -> left,n);
cout << subRoot -> key << endl;
subPrint (subRoot -> right,n);
}
if(subRoot->right!=NULL&&subRoot->right->key>n){
subPrint (subRoot -> right,n);
}
else{
return;
}
}

 

[大漠张三]

最初由 风中有影 发布
void TreeNode::subprint (TreeNode *subRoot,int n) {

if(subRoot==NULL) return;

if(subRoot->key>=n){
subPrint (subRoot -> left,n);
cout << subRoot -> key << endl;
subPrint (subRoot -> right,n);
}
if(subRoot->right!=NULL&&subRoot->right->key>n){
subPrint (subRoot -> right,n);
}
else{
return;
}
}

if(subRoot->key>=n){
subPrint (subRoot -> left,n);
cout << subRoot -> key << endl;
subPrint (subRoot -> right,n);
}

我觉得更make sense的顺序是if (subRoot->key > n) 以后就可以cout key了。然后再check left，check right。

if(subRoot->right!=NULL&&subRoot->right->key>n){
subPrint (subRoot -> right,n);
}
这行看起来没有什么用，因为在前面已经有过了subPrint(rubRoot-> right, n) 了。

最后那个
else{
return;
这个else是和上面那个if再一起的，也就是说subRoot == NULL, 或者 subRoot->right->key < n的时候 就return。但在一个BST里，你要找的key有可能在subRoot->right->right->right->key，如果第一个subRoot->right不比n大就return了是不对的。

热狗的那个code的逻辑和正确答案一样，写成pseudocode就是：

Basic case:
     subRoot == NULL, 说明没找到比n大的，就return。
     subRoot->key > n 说明subRoot比n大，按题目要求应该print。

Recursive process:
     因为subRoot比n大，所以check 左面的tree，右面的tree其实不用check 直接print就好了。
     
如果subRoot->key < n, 说明你要找的key不可能在左边的tree里，所以直接check 右面。