Печатать листовые узлы в двоичном дереве справа налево?

Выполните обход дерева в глубину, сначала обработав правые поддеревья и распечатав только конечные узлы.

Самый простой способ реализовать это — использовать рекурсивную функцию.

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);
    }
  }
}

Эта страница очень полезна для визуализации решения: Обход дерева.

void in(node* root){
if(root)
    {   
        if(!root->left && !root->right)
              cout<<root->data<<endl;
        in(root->left);
        in(root->right);
    } }

Вы можете сделать что-то вроде этого (код на C++).

Идея этого кода заключается в том, чтобы выполнить обход в обратном порядке/обход в обратном порядке и проверить, являются ли левые и правые дочерние элементы NULL или нет. Если это Null, это означает, что это конечный узел.

Вам нужно будет использовать рекурсивный метод, начав с передачи метода узлу верхнего уровня двоичного дерева.

В псевдокоде я предполагаю, что каждый узел определяется с «правыми» и «левыми» членами, которые сами являются узлами, и свойством «имя», чтобы напечатать что-то об узле. Метод может выглядеть так, на каком-либо конкретном языке, поскольку вы сказали псевдокод:

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)

1. Выполнять обход по порядку и добавлять в список посещенных узлов только конечные узлы.
2. Вернуть список.

Or

На самом деле при создании списка на первом этапе продолжайте добавлять узел во главе и пусть он указывает на предыдущий узел (а не предыдущий узел, указывающий на новый узел).

Распечатайте листовые узлы, выполняя обход порядка уровней в обратном порядке, исключая узлы, которые не являются листами.

Сделайте Inoder/Предварительный заказ/постзаказ, но сначала для правого ребенка, затем перейдите к левому ребенку

void postOrder(Node* root)
{
if(root==NULL)
return;
postOrder(root->right);
postOrder(root->left);
if(root->left==NULL && root->right==NULL)
cout << root->data <<" ";
}

Предположительно, вы знаете, как обходить бинарное дерево по порядку, используя рекурсию.

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

Вы заметите, что когда вы делаете это, вы уже обрабатываете листья в порядке слева направо, в дополнение к обработке нелистовых узлов.

Чтобы посетить справа налево, просто измените порядок операторов — так что посетите справа, затем обработайте значение, а затем посетите слева.

Чтобы напечатать только листовые узлы, вам просто нужно поместить оператор if вокруг handleValue, указав, что он будет выводить только в том случае, если узел является листом. Узел является листом, если он не имеет ни левого, ни правого дочернего узла.

код питона

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

это рекурсия, она всегда идет вправо, пока не останется правого, затем, наконец, вправо, он вернется к корню, напечатает его, затем напечатает влево, так что на самом деле вы печатаете от наибольшего значения к наименьшему, затем назад, и так то же самое, затем назад, и так то же самое потом обратно и так то же самое
бла...блаа..блаа

Я знаю, что воскрешаю старую ветку, но думаю, что это может помочь другим, просматривающим эту ветку. Если вы говорите о вопросе интервью, я думаю, что рекурсивный ответ — это лишь малая часть ответа, и интервьюер также хотел бы услышать итеративный подход. Обход справа налево (печать) не является обычным обходом pre/post/inorder, описанным в вики. Основная идея здесь заключается в том, что вам нужно идти как можно дальше вправо и начинать печать сначала с крайнего правого узла, затем его родителя и только потом левого поддерева.

Рекурсивный:

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);
    }
}