二叉树的OJ练习（二）

通过前序遍历数组构建二叉树

题目：通过前序遍历的数组（ABD##E#H##CF##G##）构建二叉树

TreeNode* TreeCreat(char* a,int* pi)
{if(a[*pi] == '#'){(*pi)++;return NULL;    }TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));if(root == NULL){perror("malloc fail");exit(-1);}root->data = a[(*pi)++];root->left = TreeCreat(a,pi);root->right = TreeCreat(a,pi);return root; 
}

解释：

1、 pi表示数组下标，初始值为0，a表示前序遍历的数组

2、如果检测到数组中表示空的符号'#'，那么就下标继续向前走，然后返回空，证明这一条路已经走到头了

3、如果检测到的不是'#'，那么就为该结点开辟一个内存空间，同时做开辟失败的警告条件判断

4、开辟成功后向该内存空间中存放值，值的大小为a[(*pi)++]（先使用*pi然后pi才会++，即下标向前走）

5、由于是根->左->右的前序遍历，所以应该先递归左子树，当整棵树的左子树走到底的时候就会读取到'#'，然后就会返回NULL（由于我们已经知道了非空与空的位置，整个构建的过程就相当于一个填空的过程，所以我们再进行递归的时候，TreeCreat函数传递的是前序遍历数组a和数组下标pi的地址，而不是root->left和root->right，）

6、最后记得返回二叉树的根节点

 ~over~