给定预序序列，用 C 语言构造一棵只有叶子的树

Question

我正在尝试构建一种特定类型的树，其中每个内部节点的数据都依赖于树的叶子。我有一个预购数组，pre[] = { 0,0,0,1,2,3,0,4,5}其中每个“0”代表一个内部节点，其他任何代表叶子。如果我要构建这棵树，它会是这样的：

         0
      /     \
     0       0
    / \     / \
   0   3   4   5
  / \
 1   2

我在递归调用时遇到问题，特别是在 while 循环中。在我完成创建带有数据“2”的节点之后，在我 return 根之后，我留在了它正上方的内部节点。这个内部节点将在 while 循环中继续运行并弄乱我的树。如果我决定在条件语句末尾的 while 循环中放置一个 return 根，那么构造将在填满树的左侧后停止。我该如何解决这个问题？

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3 #include <limits.h>
  4
  5 struct node
  6 {
  7         int data;
  8         int leafNode;
  9         struct node *left;
 10         struct node *right;
 11 };
 12
 14 struct node* newNode (int data){
 15         struct node* temp = (struct node *) malloc(sizeof(struct node));
 16         temp->data =data;
 17         temp->left = temp->right= NULL;
 18         return temp;
 19 }
 22 struct node* _constructTree( int pre[], int * preIndex, int low, int high, int size, int leaf){
 23         if (*preIndex >= size || low > high){
 24                 return NULL;}
 25
 26         printf("We are about to create this node: %d\n", pre[*preIndex]);
 27
 28         struct node* root = newNode(pre[*preIndex]);
 29         *preIndex = *preIndex + 1;
 30         if(leaf){
 31                 printf("Returning this leaf node: %d\n", pre[*preIndex - 1]);
 32                 return root;}
 33
 34
 35         if(low == high){
 36                 return root;}
 37
 38         while(low<high){
 39                 if(pre[*preIndex] == 0){
 40                 root->left = _constructTree(pre, preIndex, *preIndex, high, size, 0);}
 41
 42                 if(root->left == NULL){
 43                 root->left  = _constructTree(pre, preIndex, *preIndex, high, size, 1);
 44                 return root;
 45                 }
 46                 if(pre[*preIndex] != 0){
 47                 root->right = _constructTree(pre, preIndex, *preIndex, high, size, 1);
 48                 return root;
 49                 }
 50                 else{
 51                 root->right = _constructTree(pre,preIndex, *preIndex, high, size, 0);}
 52                         }
 53                 return root;
 54         }
 55 }
 56
 57 struct node * constructTree(int pre[], int size){
 58         int preIndex = 0;
 59         return _constructTree(pre, &preIndex, 0, size -1, size, 0);
 60         }
 61

Answer 1

这样的东西行不通吗（稍微总结了一下，但希望它能说明这个想法）？：

construct_tree(int pre[], int* index){
    root=pre[*index];
    *index++;
    if(root>0)return root;
    left=construct_tree(pre,index);
    right=construct_tree(pre,index);
    return root;
}

给定预序序列，用 C 语言构造一棵只有叶子的树

Constructing a tree in C with only leaves, given a pre order sequence

c

recursion

computer-science

binary-tree