Cバイナリツリーは、ツリーからリストを作成する方法

Question

私は、ツリー内のすべての葉のリストを構築する必要があり葉
例えば、私は次のツリーがあります。

6 
/\ 
    4 3 
/\ /\ 
1 2 5 7 

TREENODE

typedef struct treeNode { 
    int data; 
    struct treeNode* parent; 
    struct treeNode* left; 
    struct treeNode* right; 
} TreeNode; 

のtypedefを

私のリストがあるべきである1-> 2-> 5> 7

リスト

のtypedef

listNodeのtypedef

typedef struct listNode { 
     int data; 
     struct listNode* next; 
    } ListNode; 

Listnode->データ= TreeNode->データ。 （listnode構造体データ）

機能は、I疲れたいくつかの再帰関数総称する必要がありますが、どれも

任意のアイデアを働いていませんか？ ありがとうございます。

Answer 1

基本的な考え方は、ツリーin-orderをトラバースし、出会うすべてのリーフノードをリストにプッシュすることです。次のようなものがあります。

populateList(node) 
    if(node == null) return 

    populateList(node->left) 

    if (node->left == null && node->right == null) 
    pushToList(node) 
    return 

    populateList(node->right) 

Answer 2

これは、試みたとおりに再帰で行うことができます。あなたがしなければならないことは、まずあなたが葉ノードに達したかどうかをチェックすることです。左と右のポインタがNULLの場合、その場合はノードをリストに追加します。疑似コードは次のようになります。

getLeavesList(root) { 
    if root is NULL: return 
    if root is leaf_node: add_to_leaves_list(root) 
    getLeavesList(root -> left) 
    getLeavesList(root -> right) 
} 

このコードはどのプログラミング言語にも適用できます。したがって、ルートがNULLの場合、関数が有効なポインタを受け取らなかった場合は、エラーメッセージを返します。ルートがリーフの場合、左右の子ノードがNULLの場合は、それをリーフノードのリストに追加する必要があります。次に、左と右の子ノードで関数を再帰的に呼び出します。