二叉树的递归创建

beyes

使用递归方法创建二叉树，然后使用中序遍历方式将二叉树的结点输出来。

测试代码：

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

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
};

typedef struct tree treenode;
typedef treenode *btree;

btree createbtree (int *data, int pos)
{
    btree newnode;
   
    if (data[pos] == 0 || pos > 15)
        return NULL;
    else {
         newnode = (btree) malloc (sizeof (treenode));
        newnode->data = data[pos];

        /*创建左子树的递归调用*/
        newnode->left = createbtree (data, 2 * pos);   
        newnode->right = createbtree (data, 2 * pos + 1);

        return (newnode);
    }
}

void printbtree (btree ptr)
{
    if (ptr != NULL) {
        printbtree (ptr->left);
        printf ("[%2d]", ptr->data);
        printbtree (ptr->right);
    }
}

int main()
{
    btree root = NULL;
    int i;       
    int data[16] = {0, 5, 4, 6, 2, 0, 0, 8, 1, 3, 0, 0, 0, 0, 7, 9};
   
    root = createbtree (data, 1);

    printf ("数组的结点内容 \n");
    for (i = 1; i < 16; i++)
        printf ("[%2d]", data[i]);
   
      printf ("\n");
      printf ("树的结点内容 \n");
      printbtree (root);
      printf ("\n");
   
}

运行及输出：

beyes@linux-beyes:~/C/structer/BinaryTree> ./recu_create.exe
数组的结点内容
[ 5][ 4][ 6][ 2][ 0][ 0][ 8][ 1][ 3][ 0][ 0][ 0][ 0][ 7][ 9]
树的结点内容
[ 1][ 2][ 3][ 4][ 5][ 6][ 7][ 8][ 9]

递归创建流程图：

另外一棵右子树没画出来。
先是分配了各个结点，直到无结点可建时，才递归返回建立起各个结点间的连接。有红色数字标号的箭头表示建立指针链接的顺序。