02 二叉树的DFS（前序、中序或后序遍历实现）【Binary Tree 二叉树】

忘是亡心i 2021-12-21 22:05 136阅读 0赞

> 二叉树的深度优先遍历主要有三种：  
> 前序：根左右  
> 中序：左根右  
> 后序：左右根

下面是完整的实现和讲解：

#include <stdio.h>
    #include <stdlib.h>
    
    /*二叉树的深度遍历：
     * 例如二叉树
     *      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("\nPreorder traversal of binary tree is \n");
        printPreorder(root);//1 2 4 5 3
    
        printf("\nInorder traversal of binary tree is \n");
        printInorder(root);//4 2 5 1 3
    
        printf("\nPostorder traversal of binary tree is \n");
        printPostorder(root);//4 5 2 3 1
    
        return 0;
    }

DFS三种遍历方式，采用递归的方式，相对来说比较好理解一些。