从前序遍历数组创建二叉树 c实现

网上很多实现创建二叉树的方法，很大程度受《大话数据结构》影响，不断通过输入节点来创建。个人觉得这样很不方便，修改起来也很麻烦。不过按照《大话数据结构》创建二叉树的思路，可以从前序遍历的数组创建二叉树，首先，规定该数组的格式：

格式还是按照《大话数据结构》里面，最后的空节点用一个特殊的值来替代，并且也遍历进数组

其中ABCD就是自己的数，#可以用以数来表示。这里我用0x7fffffff来表示。具体的数值，应该根据自己项目情况，选取不会出现的数值来替代。

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

#define MAXNUM 0x7fffffff

struct BiTreeNode {                                                //定义树节点
    int dat;
    struct BiTreeNode *lchild;                                    //左子树指针
    struct BiTreeNode *rchild;                                    //右子树指针
};

/*
将二叉树的前序遍历存入数组，末尾空位置放置0x7fffffff
*/
void creatBiTree(struct BiTreeNode** head, int a[], int length, int index) {
    static int count;
    count = index;

    if (count >= length) {
        return;
    }
    if (length <= 0 || a[count] == MAXNUM) {
        *head = NULL;
        return;
    }

    (*head) = (struct BiTreeNode *)malloc(sizeof(struct BiTreeNode));
    (*head)->dat = a[count];
    creatBiTree(&((*head)->lchild), a, length, count + 1);
    creatBiTree(&((*head)->rchild), a, length, count + 1);
}

void preOrdV(struct BiTreeNode *head) {                                //二叉树的前序遍历
    if (head == NULL) {
        return;
    }
    printf("%d ", head->dat);
    preOrdV(head->lchild);
    preOrdV(head->rchild);
}

void inOrdV(struct BiTreeNode *head) {                            //二叉树中序遍历
    if (head == NULL) {
        return;
    }
    inOrdV(head->lchild);
    printf("%d ", head->dat);
    inOrdV(head->rchild);
}

void postOrdV(struct BiTreeNode *head) {                        //后续遍历二叉树
    if (head == NULL) {
        return;
    }
    postOrdV(head->lchild);
    postOrdV(head->rchild);
    printf("%d ", head->dat);
}

int main() {
    struct BiTreeNode* head = NULL;
    int TreeNum[] = { 1, 2, 4, MAXNUM , 7, MAXNUM, MAXNUM, MAXNUM, 3, 5, MAXNUM, MAXNUM, 6, 8, MAXNUM, MAXNUM, MAXNUM };
    creatBiTree(&head, TreeNum, sizeof(TreeNum) / sizeof(int), 0);
    preOrdV(head);
    printf("\n");
    inOrdV(head);
    printf("\n");

    return 0;
}

我们来验证一下：

 

转载于:https://my.oschina.net/u/3464640/blog/983667