C语言后序字符串构建二叉树时根节点为空的问题解决

尝试用后序表示法的输入字符串构建二叉树，读取字符串后把'\0'前的最后一个字符传给convertToTreeFromPost函数，但执行完后输出前序遍历结果时，发现树的根节点还是指向NULL，该怎么解决？

原代码如下：

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

// 创建节点结构
typedef struct nodo
{
  char data;
  struct nodo *left;
  struct nodo *right;
} nodeType, *node;

// 创建二叉树结构
typedef struct arbol
{
  node root;
} treeType, *tree;

// 创建节点（左右指针初始化为NULL）
node createNode( char data_ );
// 创建树
tree createTree();

// 中序遍历输出
void writeInOrder( node node_ );
// 前序遍历输出
void writePreOrder( node node_ );
// 后序遍历输出
void writePostOrder( node node_ );

// 后序字符串转二叉树：首次调用需传入树根节点和字符串最后一个有效字符
char* convertToTreeFromPost( node node_, char* elemento );

int main(void) {

  tree newTree = createTree();

  char input[1000];
  
  printf("Ingrese el arbol en notacion PostFijo\n");

  fgets( input, sizeof( input ), stdin );

  int inputSize = strlen(input);

  
  char* lastElement = &input[inputSize - 2];

  char* pierdase = convertToTreeFromPost( newTree -> root, lastElement );

  printf("\nEl arbol en PreOrden es: \n");
  
  writePreOrder( newTree -> root );
  
  return 0;
}

node createNode( char data_ )
{
  node newNode = (node) malloc( sizeof( nodeType ) );
  newNode -> data = data_;
  newNode -> left = NULL;
  newNode -> right = NULL;

  return newNode;
}

tree createTree()
{
  tree newTree = (tree) malloc( sizeof( treeType ) );
  newTree -> root = NULL;

  return newTree;
}

void writeInOrder( node node_ )
{
  if( node_ != NULL )
  {
    writeInOrder( node_ -> left );
    printf("%c", node_ -> data );
    writeInOrder( node_ -> right );
  }
  else
  {
    printf("#");
  }
}

void writePreOrder( node node_ )
{
  if( node_ != NULL )
  {
    printf("%c", node_ -> data );
    writePreOrder( node_ -> left );
    writePreOrder( node_ -> right );
  }
  else
  {
    printf("#");
  }
}

void writePostOrder( node node_ )
{
  if( node_ != NULL )
  {
    writePostOrder( node_ -> left );
    writePostOrder( node_ -> right );
    printf("%c", node_ -> data );
  }
  else
  {
    printf("#");
  }
}

char* convertToTreeFromPost( node node_, char* elemento )
{
  if( (*elemento) != '#' )
  {
    node_ = createNode( (*elemento) );
    elemento = (elemento - 1);
    elemento = convertToTreeFromPost( node_ -> right, elemento );

    if( (*elemento) != '#' )
    {
      elemento = convertToTreeFromPost( node_ -> left, elemento );
      return elemento;
    }
    else if( (*elemento) == '#' )
    {
      elemento = (elemento - 1);
      return elemento;
    }
  }
  else if( (*elemento) == '#' )
  {
    
    elemento = (elemento - 1);
    
    if( (*elemento) != '#' )
    {
      return elemento;
    }
    else if( (*elemento) == '#' )
    {
      return elemento;
    }
  } 
}

问题根源与解决步骤 #

1. 指针传递错误（核心问题） #

原函数convertToTreeFromPost的参数node node_是值传递，函数内部修改node_的指向只会改变局部变量，根本影响不到外部的newTree->root。必须改成指针的指针才能修改外部节点的指向。

2. 递归逻辑漏洞 #

原函数处理空节点#的逻辑混乱，递归时的指针偏移规则不统一，导致子节点无法正确关联到父节点。后序遍历的顺序是左-右-根，从后往前读字符串的顺序是根-右-左，所以递归时要先构建右子树，再构建左子树。

3. 输入处理瑕疵 #

fgets会把换行符读入字符串，原代码inputSize - 2的处理不够稳妥，最好先把换行符替换成\0，再取最后一个有效字符。

修改后的完整代码 #

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

// 创建节点结构
typedef struct nodo
{
  char data;
  struct nodo *left;
  struct nodo *right;
} nodeType, *node;

// 创建二叉树结构
typedef struct arbol
{
  node root;
} treeType, *tree;

// 创建节点（左右指针初始化为NULL）
node createNode( char data_ );
// 创建树
tree createTree();

// 中序遍历输出
void writeInOrder( node node_ );
// 前序遍历输出
void writePreOrder( node node_ );
// 后序遍历输出
void writePostOrder( node node_ );

// 后序字符串转二叉树：改为指针的指针，确保能修改外部节点
char* convertToTreeFromPost( node *node_, char* elemento );

int main(void) {

  tree newTree = createTree();

  char input[1000];
  
  printf("Ingrese el arbol en notacion PostFijo\n");

  fgets( input, sizeof( input ), stdin );
  // 去掉末尾的换行符，避免干扰
  input[strcspn(input, "\n")] = '\0';
  
  int inputSize = strlen(input);
  // 直接取最后一个有效字符
  char* lastElement = &input[inputSize - 1];

  char* pierdase = convertToTreeFromPost( &newTree->root, lastElement );

  printf("\nEl arbol en PreOrden es: \n");
  
  writePreOrder( newTree->root );
  
  return 0;
}

node createNode( char data_ )
{
  node newNode = (node) malloc( sizeof( nodeType ) );
  newNode->data = data_;
  newNode->left = NULL;
  newNode->right = NULL;

  return newNode;
}

tree createTree()
{
  tree newTree = (tree) malloc( sizeof( treeType ) );
  newTree->root = NULL;

  return newTree;
}

void writeInOrder( node node_ )
{
  if( node_ != NULL )
  {
    writeInOrder( node_->left );
    printf("%c", node_->data );
    writeInOrder( node_->right );
  }
  else
  {
    printf("#");
  }
}

void writePreOrder( node node_ )
{
  if( node_ != NULL )
  {
    printf("%c", node_->data );
    writePreOrder( node_->left );
    writePreOrder( node_->right );
  }
  else
  {
    printf("#");
  }
}

void writePostOrder( node node_ )
{
  if( node_ != NULL )
  {
    writePostOrder( node_->left );
    writePostOrder( node_->right );
    printf("%c", node_->data );
  }
  else
  {
    printf("#");
  }
}

char* convertToTreeFromPost( node *node_, char* elemento )
{
    // 遇到#表示空节点，置空后回退一个字符
    if (*elemento == '#') {
        *node_ = NULL;
        return elemento - 1;
    }
    // 创建当前节点
    *node_ = createNode(*elemento);
    elemento--;
    // 先构建右子树（后序从后往前读是根-右-左）
    elemento = convertToTreeFromPost(&(*node_)->right, elemento);
    // 再构建左子树
    elemento = convertToTreeFromPost(&(*node_)->left, elemento);
    return elemento;
}

内容的提问来源于stack exchange，提问作者Andrés Felipe Muñoz Aguilar