二叉树的遍历

beyes

二叉树的遍历 ---中序遍历方式
中序遍历是沿着树的左方往下走，直到无法继续前进后处理结点，退回父结点依此法往右方走，如果右方都无法前进，再往上层退回。如下图所示二叉树：

经过中序遍历输出数据顺序为：1，2， 3， 4，5， 6，7，8，9

创建二叉树和遍历输出程序：

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree treenode;
typedef treenode *btree;

/*------------------------------*/
/*插入二叉树的结点              */
/*------------------------------*/

btree insertnode (btree root, int value)
{
    btree newnode;            /*新结点指针*/
    btree current;            /*当前结点指针,检测结点用*/
    btree back;            /*父结点指针*/

    /*创建新内存结点*/
    newnode = (btree) malloc (sizeof (treenode));    /*创建新结点*/
    newnode->data = value;                /*结点数据初值*/
    newnode->left = NULL;                /*指针初值*/
    newnode->right = NULL;                /*指针初值*/
   
    if (root == NULL) {
        return newnode;                /*建立根结点*/
    } else {
        current = root;                /*从根结点开始检测*/
        while (current != NULL) {        /*循环检测*/
            back = current;            /*备份父结点指针*/
            if (current->data > value)    /*比较结点值*/
                current = current->left;/*当前指针移向左子树下一个结点*/
            else
                current = current->right;/*当前指针移向右子树下一个结点*/
        }
        if (back->data > value)            /*可以在空的位置处插入新的结点数据了*/
            back->left = newnode;        /*插入新的结点到左子树上*/
        else
            back->right = newnode;        /*插入新的结点到右子树上*/
    }
    return (root);                    /*返回根指针*/
}   

/*------------------------------*/
/*创建二叉树                    */
/*------------------------------*/
btree createbtree (int *data, int len)
{
        btree root = NULL;
        int i;
   
        for (i = 0; i < len; i++)
                root = insertnode (root, data[i]);

        return (root);
}

/*------------------------------*/
/*二叉树的中序遍历              */
/*------------------------------*/
void inorder (btree ptr)
{
    if (ptr != NULL) {
        inorder (ptr->left);
        printf ("[%2d]\n", ptr->data);
        inorder (ptr->right);
    }
}


int main()
{
    btree root = NULL;
    int data [9] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
    root = createbtree (data, 9);        /*创建二叉树*/
    inorder (root);
   
    return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/BinaryTree> ./inoder.exe
[ 1]
[ 2]
[ 3]
[ 4]
[ 5]
[ 6]
[ 7]
[ 8]
[ 9]

说明：
程序中使用了 malloc() 函数分配内存，但是最后因为方便的原因并没有使用free() 释放内存，尽管操作系统在程序结束后会自动回收这部分内存，但毕竟这不是良好的习惯。

程序使用了中序方式遍历了二叉树。中序遍历是一种递归的遍历方式，原理如下图所示：

在上图中，红色数字表名递归的行进路线。从 L -> R 表示打印出结点数据。

beyes

使用和上面一样的二叉树结构。前序遍历方式是每遍历到一个结点就立刻处理结点。遍历的顺序是先向着树的左方走，直到无法前进后，才转往右方走，按照前序遍历二叉树的顺序，二叉树结构输出数据：

5， 4， 2， 1， 6， 8， 7， 9

测试代码：

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree treenode;
typedef treenode *btree;

/*------------------------------*/
/*插入二叉树的结点              */
/*------------------------------*/

btree insertnode (btree root, int value)
{
    btree newnode;            /*新结点指针*/
    btree current;            /*当前结点指针,检测结点用*/
    btree back;            /*父结点指针*/

    /*创建新内存结点*/
    newnode = (btree) malloc (sizeof (treenode));    /*创建新结点*/
    newnode->data = value;                /*结点数据初值*/
    newnode->left = NULL;                /*指针初值*/
    newnode->right = NULL;                /*指针初值*/
   
    if (root == NULL) {
        return newnode;                /*建立根结点*/
    } else {
        current = root;                /*从根结点开始检测*/
        while (current != NULL) {        /*循环检测*/
            back = current;            /*备份父结点指针*/
            if (current->data > value)    /*比较结点值*/
                current = current->left;/*当前指针移向左子树下一个结点*/
            else
                current = current->right;/*当前指针移向右子树下一个结点*/
        }
        if (back->data > value)            /*可以在空的位置处插入新的结点数据了*/
            back->left = newnode;        /*插入新的结点到左子树上*/
        else
            back->right = newnode;        /*插入新的结点到右子树上*/
    }
    return (root);                    /*返回根指针*/
}   

/*------------------------------*/
/*创建二叉树                    */
/*------------------------------*/
btree createbtree (int *data, int len)
{
        btree root = NULL;
        int i;
   
        for (i = 0; i < len; i++)
                root = insertnode (root, data[i]);

        return (root);
}

/*------------------------------*/
/*二叉树的前序遍历              */
/*------------------------------*/
void preorder (btree ptr)
{
    if (ptr != NULL) {
        printf ("[%2d]\\n", ptr->data);    /*输出结点内容*/
        preorder (ptr->left);        /*左子树*/
        preorder (ptr->right);        /*右子树*/
    }
}


int main()
{
    btree root = NULL;
    int data [9] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
    root = createbtree (data, 9);        /*创建二叉树*/
    preorder (root);
   
    return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/BinaryTree> ./preorder.exe
[ 5]
[ 4]
[ 2]
[ 1]
[ 3]
[ 6]
[ 8]
[ 7]
[ 9]

递归行进如下图所示：

图中，闪电箭头表示要打印数据，其左上方标号为打印的顺序。

beyes

仍使用上面的二叉树结构。后序遍历方式刚好和前序的方式相反，它是等到结点的两个子结点都遍历过后才进行处理。按照后续遍历二叉树的顺序，数据输出如下所示：
1，3，2，4，7，9，8，6，5

测试代码：

#include <stdio.h>
#include <stdlib.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};
typedef struct tree treenode;
typedef treenode *btree;

/*------------------------------*/
/*插入二叉树的结点              */
/*------------------------------*/

btree insertnode (btree root, int value)
{
    btree newnode;            /*新结点指针*/
    btree current;            /*当前结点指针,检测结点用*/
    btree back;            /*父结点指针*/

    /*创建新内存结点*/
    newnode = (btree) malloc (sizeof (treenode));    /*创建新结点*/
    newnode->data = value;                /*结点数据初值*/
    newnode->left = NULL;                /*指针初值*/
    newnode->right = NULL;                /*指针初值*/
   
    if (root == NULL) {
        return newnode;                /*建立根结点*/
    } else {
        current = root;                /*从根结点开始检测*/
        while (current != NULL) {        /*循环检测*/
            back = current;            /*备份父结点指针*/
            if (current->data > value)    /*比较结点值*/
                current = current->left;/*当前指针移向左子树下一个结点*/
            else
                current = current->right;/*当前指针移向右子树下一个结点*/
        }
        if (back->data > value)            /*可以在空的位置处插入新的结点数据了*/
            back->left = newnode;        /*插入新的结点到左子树上*/
        else
            back->right = newnode;        /*插入新的结点到右子树上*/
    }
    return (root);                    /*返回根指针*/
}   

/*------------------------------*/
/*创建二叉树                    */
/*------------------------------*/
btree createbtree (int *data, int len)
{
        btree root = NULL;
        int i;
   
        for (i = 0; i < len; i++)
                root = insertnode (root, data[i]);

        return (root);
}

/*------------------------------*/
/*二叉树的后序遍历              */
/*------------------------------*/
void postorder (btree ptr)
{
    if (ptr != NULL) {
        postorder (ptr->left);        /*左子树*/
        postorder (ptr->right);        /*右子树*/
        printf ("[%2d]\\n", ptr->data);    /*输出结点内容*/
    }
}


int main()
{
    btree root = NULL;
    int data [9] = {5, 6, 4, 8, 2, 3, 7, 1, 9};
    root = createbtree (data, 9);        /*创建二叉树*/
    postorder (root);
   
    return (0);
}

运行与输出：

beyes@linux-beyes:~/C/structer/BinaryTree> ./postorder.exe
[ 1]
[ 3]
[ 2]
[ 4]
[ 7]
[ 9]
[ 8]
[ 6]
[ 5]