Отпечатване на листови възли в двоично дърво отдясно наляво?

Извършете първо обхождане на дървото в дълбочина, като първо обработвате десните поддървета и отпечатвате само листовите възли.

Най-лесният начин да реализирате това е с рекурсивна функция.

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.

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/Preorder/postorder Но първо за Right Child След това отидете на ляво Child

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, като му кажете да извежда само ако възелът е лист. Възелът е лист, ако няма нито ляв, нито десен дъщерен възел.

код на python

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

това е рекурсия, върви винаги надясно, докато няма надясно, след това накрая надясно, връща се обратно към корена, отпечатва го, след това отпечатва наляво, така че всъщност вие печатате от най-голямата стойност до най-ниската, след това обратно и така същото нещо, след това обратно и така същото нещо, после обратно и така същото нещо
бла...блаа..блаа

Знам, че възкресявам стара тема, но мисля, че това може да помогне на другите, които гледат тази тема. Ако говорите за въпрос за интервю, мисля, че рекурсивният отговор е само малка част от отговора и интервюиращият ще иска да чуе и итеративния подход. Обхождането отдясно наляво (отпечатване) не е обичайно преминаване преди/след/в ред, описано в 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);
    }
}