在“按顺序遍历树”中查找特定节点

Question

我正在创建自己的shell。

我已经为用户输入创建了词法分析器和解析器（它创建了一个二叉树）。 所以对于这样的命令：cat main.c | ls | wc。

我得到这个树：

  "|" 
     /\ 
     / \ 
     / \ 
"cat main.c" "|" 
       /\ 
      / \ 
      "ls" "wc" 

所以我的树遍历功能（按顺序）是这样的：

inorder(root) 
{ 
    inorder(root->left); 
    //exec cmd and do redirection 

    inorder(root->right); 
} 

我的问题是，当我在节点“LS”或“ wc“，我不知道如何 检查命令之前和之后是否有管道。

有什么想法？

Answer 1

在你的分析树中，管道是节点，命令是树叶。管道必须有左右分支。当你从一个管道离开时，你现在所处的管道就是你将要进入的命令的输出管道。当你向右走时，你所在的管道是目标命令的管道。

所以通过输入和输出管道作为参数。如果没有该命令的重定向或|节点之一，则它们指向NULL。

inorder(root, in, out) 
{ 
    if (root is cmd) { 
     execute(root, in, out); 
    } else { 
     // root is pipe 
     inorder(root->left, in, root); 
     redirect(in, out); 
     inorder(root->right, root, out); 
    } 
} 

从inorder(root, NULL, NULL)开始在树的根部。