c - 从节点打印值

Question

我正在尝试检查一个“位串”，它给出了二叉树的方向。我遇到的问题是当节点到达末尾(空)时打印节点的值，然后返回到顶部，直到“位字符串”中的某个字符在末尾被命中。

所以字符串:

char * directions = "RRLRRLRLLRLRRS";

将从根开始，然后向右>右>左>右(假设击中了叶子)，然后它将回到根并遍历右>左>右>左>左(然后切换回每次找到叶子时都会找到根，然后一旦碰到“S”，它就会停止遍历。

我现在拥有的代码现在尝试从它最后命中的节点中获取值以进行调试，并且它不会打印任何内容。如何解决这个问题？

(顺序只是帮助确定它在树中的位置)

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

typedef struct Node {
  int order;
  char value;
  struct Node * left;
  struct Node * right;
} Node;

Node * insert(Node * node, char value, int order){
  if(node == NULL){
    node = (Node *)malloc(sizeof(Node));
    node->value = value;
    node->order = order;
    node->left = NULL;
    node->right = NULL;
    return node;
  }
  if(order > node->order){
    node->right = insert(node->right, value, order);
  }
  else if(order < node->order){
    node->left = insert(node->left, value, order);
  }
  else {
    return;
  }
  return node;
}

int main(){


  Node * root = NULL;
  char * directions = "RRLRRLRLLRLRRS";
  int length = (int)strlen(directions);
  int i;

  root = insert(root, -1, 6);
  root = insert(root, -1, 4);
  root = insert(root, -1, 2);
  root = insert(root, 32, 1);
  root = insert(root, 114, 3);
  root = insert(root, 108, 5);
  root = insert(root, -1, 12);
  root = insert(root, -1, 8);
  root = insert(root, 111, 7);
  root = insert(root, -1, 10);
  root = insert(root, 101, 9);


  /* basics to see values at this point */
  i = 0;
  while(directions[i] != 'S'){
    if(directions[i] == 'L'){
      printf(root->value);
      root = root->left;
    }
    else if(directions[i] == 'R'){
      printf(root->value);
      root = root->right;     
    }
    i++;
  }

  return 0
}

Answer 1

如果我尝试按原样运行，您的代码段会出错，因为您在命中叶节点后不会“重置”根。我修改了 printf 语句以打印出 Node 结构的实际 int 字段，并添加了一个 if-else 来测试遍历中的当前节点是否是叶子:

  ...

  Node * origRoot = root;

  i = 0;
  while(directions[i] != 'S'){
    if(directions[i] == 'L'){
      printf("%d\n", root->order);
      if(root->left == NULL)
        root = origRoot;   
      else      
        root = root->left;
    }
    else if(directions[i] == 'R'){
      printf("%d\n", root->order);
      if(root->right == NULL)
        root = origRoot;   
      else      
        root = root->right;           
    }
    i++;
  }

  ...

我在这里提供了可视化并逐步执行代码:gist.github.com/liangricha/10337524