data-structures - 二分木のリーフノードを右から左に出力しますか?

Question

私はこれに対する答えを探しています:

二分木の葉ノードを右から左に出力する擬似コードを見つけます。

いくつかのアイデアを聞いてうれしいです。この問題を理解するのに役立つヒント (もちろん、完全な解決策ではありません) または関連トピックへのリンクが役立つでしょう。

Answer 1

ツリーの深さ優先トラバーサルを実行し、最初に正しいサブツリーを処理し、リーフ ノードのみを出力します。

これを実装する最も簡単な方法は、再帰関数を使用することです。

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 2

メソッドにバイナリ ツリーの最上位ノードを渡すことから始めて、再帰的なメソッドを使用する必要があります。

疑似コードでは、ノードに関する情報を表示するために、ノード自体がノードである「右」メンバーと「左」メンバー、および「名前」プロパティで各ノードが定義されていると想定しています。メソッドは、疑似コードと言ったので、特定の言語ではなく、次のようになります。

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 3

古いスレッドを復活させていることは承知していますが、このスレッドを閲覧している他のユーザーの助けになると思います。面接の質問について話している場合、再帰的な回答は回答のほんの一部であり、面接官は反復的なアプローチも聞きたいと思うでしょう. 右から左へのトラバーサル (印刷) は、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);
    }
}