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

Question

Я ищу ответ на это:

Найти псевдокод печати узлов листьев в бинарном дереве, из справа налево.

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

Answer 1

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

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

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) 

Answer 2

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

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

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.

Answer 3

Я знаю, что я воскрешаю старую нить, но я думаю, что это может помочь другим, просматривающим эту тему. Если вы говорите об интервью, я думаю, что рекурсивный ответ - это лишь небольшая часть ответа, и интервьюер также захочет услышать итеративный подход. Право налево (печать) не является обычным прохождением pre/post/inorder, описанным в 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); 
    } 
} 

Answer 4

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

Или

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

Answer 5

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

Answer 6

Do Inoder/Предзаказ/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 <<" "; 
} 

Answer 7

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

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

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

Answer 8

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

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

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

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

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