作者：冯老师,华清远见嵌入式学院讲师。

一、二叉树的第一种实现

下面程序实现的是一个完全二叉树，其中树形结构的结点为1，2，……，n.

typedef char dtype;
        typedef struct node
        {
            dtype data;
            struct node * left;
            struct node * right;
        }bitree;
        bitree * bitree_create(int i, int n)
        {
            bitree * r;
            if ((r = (bitree *)malloc(sizeof(bitree))) == NULL)
            {
                printf("malloc failed\n");
                return NULL;
            }
            r->data = http://www.mamicode.com/i;
            r->left = 2*i <= n ? bitree_create(2*i, n) : NULL;
            r->right = 2*i + 1 <= n ? bitree_create(2*i+1, n) : NULL;
            return r;
        }

调用程序如下：

if ((r = bitree_create(1, 8)) == NULL)
        return 0;

二、二叉树的第二种实现

由于第一个程序树形结构的结点固定为1，2，……，n. 若想让其结点数据，为用户需要的数值，可以做如下调整：

typedef char dtype;
        typedef struct node
        {
            dtype data;
            struct node * left;
            struct node * right;
        }bitree;
        bitree * bitree_create(int i, int n, dtype a[])
        {
            bitree * r;
            if ((r = (bitree *)malloc(sizeof(bitree))) == NULL)
            {
                printf("malloc failed\n");
                return NULL;
            }
            r->data = http://www.mamicode.com/a[i];
            r->left = 2*i <= n ? bitree_create(2*i, n, a) : NULL;
            r->right = 2*i + 1 <= n ? bitree_create(2*i+1, n, a) : NULL;
            return r; }

调用程序如下：

dtype a[] = {‘ ‘, ‘A‘, ‘B‘, ‘C‘};
        char s[] = {‘d‘, ‘c‘, ‘f‘};
        if ((r = bitree_create(1, sizeof(a)/sizeof(dtype)-1, a)) == NULL)
        return 0;

即把结点在树中的编号，作为了一个数组的下标，而数组元素的内容，是由用户来定义的。这样建立的完全二叉树，就比第一种更灵活。

三、二叉树的第三种实现

上面两种方法，建立的都是完全二叉树，若想建立任意形状的树，可以参考下面的程序

bitree * bitree_create()
        {
        bitree * r;
        
        char ch;
        
        scanf("%c", &ch);
        if (ch == ‘#‘)
        return NULL;
        
        if ((r = (bitree *)malloc(sizeof(bitree))) == NULL)
        {
        printf("malloc failed\n");
        return r;
        }
        
        r->data = http://www.mamicode.com/ch;
        r->left = bitree_create();
        r->right = bitree_create();
        
        return r;
        }

调用程序如下：

bitree * r = NULL;
        if ((r = bitree_create()) == NULL)
        return 0;

执行程序时，得按树形结构的先序形式来输入。比如，若想建立上面所示的树，执行程序时得输入：

ABC##DE#G##F###

该程序利用了，把树节点没有的左或右孩子，用#来表示，这样作为递归的终止条件，就可以创建任意形状的树了。

四、二叉树的第四种实现

由于上面的程序树形结构的结点固定为字符行的变量. 若想让其结点数据，为用户需要的数值，可以做如下调整：

bitree * bitree_create2(dtype b[])
        {
        bitree * r;
        
        int ch;
        
        scanf("%d", &ch);
        if (ch == 4)
        return NULL;
        
        if ((r = (bitree *)malloc(sizeof(bitree))) == NULL)
        {
        printf("malloc failed\n");
        return r;
        }
        
        r->data = http://www.mamicode.com/b[ch];
        r->left = bitree_create2(b);
        r->right = bitree_create2(b);
        
        return r;
        }

调用程序如下：

dtype b[] = {‘ ‘, ‘A‘, ‘B‘, ‘C‘, ‘D’, ‘E’, ‘F’, ‘G’, ‘#‘};
        if ((r = bitree_create2(b)) == NULL)
        return 0;

执行程序时，把树形结构中出现的结点，事先放到b数组中，到了相应结点的输入，只需要输入其在b数组中对应值的下标即可，比如，还建立第三种方法的树，应该输入：

1 2 3 8 8 4 5 8 7 8 8 6 8 8 8

文章来源：华清远见嵌入式学院，原文地址：http://www.embedu.org/Column/Column899.htm

更多相关嵌入式免费资料查看华清远见讲师博文>>

二叉树的四种实现