0

我正在为此寻找答案：

从右到左找到打印二叉树中叶节点的伪代码。

我很高兴听到一些想法。可以帮助我理解这个问题的提示（当然不是完整的解决方案）或相关主题的链接会有所帮助。

4

9 回答 9

4

执行树的深度优先遍历，首先处理右子树并仅打印叶节点。

实现这一点的最简单方法是使用递归函数。

void printLeafNodes(BinaryTreeNode* treePtr) {
  if(treePtr.leftChild == null && treePtr.rightChild == null) {
    //This is a leaf node; print its value
  } else {
    //Recurse on right subtree
    if(treePtr.rightChild != null) {
      printLeafNodes(treePtr.rightChild);
    }
    //Recurse on left subtree
    if(treePtr.leftChild != null) {
      printLeafNodes(treePtr.leftChild);
    }
  }
}

此页面对于可视化解决方案非常有帮助：Tree Traversal。

于 2013-05-10T17:13:22.293 回答
1 
void in(node* root){
if(root)
    {   
        if(!root->left && !root->right)
              cout<<root->data<<endl;
        in(root->left);
        in(root->right);
    } }

你可以做这样的事情（C++ 中的代码）。

这段代码背后的想法是，进行中序遍历/后序遍历并检查左右子节点是否为 NULL。如果为 Null，则表示它是叶节点。

于 2017-08-14T06:45:40.000 回答
0

您需要使用递归方法，首先将方法传递给二叉树的顶级节点。

在伪代码中，我假设每个节点都定义了“right”和“left”成员，它们本身就是节点和“name”属性，以打印关于节点的一些内容。该方法可能看起来像这样，因为您说的是伪代码，所以没有特定的语言：

function processNode(parent) {
    if(parent.right = null AND parent.left = null)
        print parent.name
    if(parent.right <> null)
        processNode(parent.right)
    if(parent.left <> null)
        processNode(parent.left)
}

然后你会开始：

processNode(topNode)
于 2013-05-10T17:11:22.007 回答
0

蟒蛇代码

def Reverse_print(self):
    if self.right:
        self.right.Reverse_print()
    print(self.data),
    if self.left:
        self.left.Reverse_print()

它是递归，它总是正确的，直到没有权利，然后最后向右它回到根打印它然后向左打印所以实际上你是从最大值打印到最小值然后返回，所以同样的事情然后返回等等同样的事情然后回来，所以同样的事情
bla...blaa..blaa

于 2018-06-12T13:25:53.207 回答
0
  1. 执行按顺序遍历并仅将叶节点添加到访问节点列表中。
  2. 还原列表。

或者

实际上，在第一步中创建列表时，不断在头部添加节点并让它指向前一个节点（而不是前一个节点指向新节点）。

于 2016-01-11T16:36:05.080 回答
0

大概您知道如何使用递归按顺序遍历二叉树。

void visit(Node node) {
     if(node.hasLeft()) {
         visit(node.getLeft());
     }
     handleValue(node.value); // print or whatever
     if(node.hasRight()) {
         visit(node.getRight());
     }
}

您会注意到，当您执行此操作时，除了处理非叶子节点之外，您已经按照从左到右的顺序处理叶子。

要从右到左访问，只需颠倒语句的顺序——访问右边，然后处理值，然后访问左边。

要仅打印叶节点，您只需在if周围放置一条语句handleValue，告诉它仅在节点是叶时才输出。如果一个节点既没有左子节点也没有右子节点，那么它就是叶子节点。

于 2017-08-15T15:53:45.510 回答
0

做 Inode/Preorder/postorder 但先为右孩子然后去左孩子

void postOrder(Node* root)
{
if(root==NULL)
return;
postOrder(root->right);
postOrder(root->left);
if(root->left==NULL && root->right==NULL)
cout << root->data <<" ";
}
于 2017-06-21T04:01:22.927 回答
0

打印叶子节点，同时以相反的顺序进行级别顺序遍历，不包括不是叶子的节点。

于 2017-05-25T19:08:02.397 回答
-1

我知道我正在复活一个旧线程，但我认为它可以帮助其他人查看这个线程。如果您在谈论面试问题，我认为递归答案只是答案的一小部分，面试官也希望听到迭代方法。从右到左遍历（打印）不是 wiki 中描述的常规前/后/中序遍历。这里的主要思想是，您需要尽可能向右走，并首先从最右边的节点开始打印，然后是其父节点，然后才是左子树。

递归：

printRightToLeft(Node root){
  if (root == null)
     return;

  // You can check root.right and root.left for null before calling the
  // printRightToLeft function to avoid pushing unneeded data to recursion
  // call stack.

  printRightToLeft(root.right);
  if (root.right == null && root.left == null)
     print(root);
  printRightToLeft(root.left);
}

迭代：

printRightToLeft(Node root){
  if (root == null)
    return;

  Stack s = new Stack();
  s.push(root);

  while(!s.isEmpty()){
    Node n = s.top();

    if (n.right != null && !n.visited){
      s.push(n.right);
      n.visited = true;
    } else {
      s.pop();

      if (n.right == null && n.left == null)
         print(n);

      if (n.left != null)
         s.push(n.left);
    }
}
于 2013-05-17T08:19:12.277 回答