02ツリーのDFS(前、中、または後)【Binary Treeツリー】

二叉木の深さ優先遍歴は主に3種類ある:前序:根左右中序:左根右後序:左右根
以下に完全な実装と説明を示します.

#include 
#include 

/*        ：
 *      
 *      1
 *     / \
 *    2   3
 *   /\
 * 4  5
 *     ：    4-2-5-1-3
 *     ：    1-2-4-5-3
 *     ：    4-5-2-3-1
 *
 *     BFS（  ）        ：1-2-3-4-5
 *
 */

/*     */
struct node {
    int data;
    struct node *left;
    struct node *right;
};

/*     ，       ，       NULL*/
struct node *newNode(int data) {
    //         ，         
    struct node *node = (struct node *) malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

/*    ：   */
void printInorder(struct node *node) {
    if (node == NULL){
        return;
    }

    //      ，  node null，  node->left NULL,printInorder(node->left)         
    //        ，printf("%d ",node->data);
    //     
    printInorder(node->left);

    //     
    printf("%d ",node->data);

    //     
    printInorder(node->right);
}

/*    ：   */
void printPreorder(struct node* node){
    if (node == NULL){
        return;
    }

    //     
    printf("%d ",node->data);

    //     
    printPreorder(node->left);

    //     
    printPreorder(node->right);
}

//    :   
void printPostorder(struct node* node)
{
    if (node == NULL)
        return;

    // first recur on left subtree
    printPostorder(node->left);

    // then recur on right subtree
    printPostorder(node->right);

    // now deal with the node
    printf("%d ", node->data);
}


int main() {
    //   
    //     
    struct node *root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);

    printf("
Preorder traversal of binary tree is 
");
    printPreorder(root);//1 2 4 5 3

    printf("
Inorder traversal of binary tree is 
");
    printInorder(root);//4 2 5 1 3

    printf("
Postorder traversal of binary tree is 
");
    printPostorder(root);//4 5 2 3 1

    return 0;
}

DFSの3つの遍歴方式は,再帰的な方式を採用し,比較的理解しやすい.