使用顺序遍历在二叉树中搜索元素

Question

struct tnode
{
    int val;
    struct tnode *left;
    struct tnode *right;
};

int search(struct tnode *root, int val)
{
    int p = 0;
    int q = 0;
    if (!root) return 0;
    p = search(root->left, val);
    if (p == 1) return 1;
    if (root->val == val) return 1;
    q = search(root->right, val);
    if (q == 1) return 1;
}

我不明白在搜索树时找不到 val 时上面的代码是如何返回 0 的。

Answer 1

你所拥有的是一个非结构化函数。有四个 return 语句和五个可能的 return 路径。其中一个 return 显式 return 为零，其他显式 return 1，因此您调用 search 时 root 为 NULL 或第五个隐式return 路径恰好 return 为零。

调高编译器的警告级别，它应该已经标记了并非所有执行路径 return 一个值的事实。

我建议您重新安排您的逻辑，以便在函数末尾有一个 return 语句。

Answer 2

这里，我使用栈来迭代中序遍历一棵树

int find_element(struct node *root,int val){

     if(!root) return 0;
     std::stack<node*> s;
     while(!s.empty() || root){
          if(root){
              s.push(root);
              root=root->left;
          }
          else
          {
              root=s.top();
              s.pop();
              if(root->val==val) return 1;
              root=root->right;
          }
     }
     return 0;
}

使用顺序遍历在二叉树中搜索元素

searching an element in binary tree using in order traversal

c

search

binary-tree

data-structures