（普通）树的非递归顺序遍历

Question

通常为二叉树定义顺序。让我们假设顺序对于（普通）树是“扩展”的。如果树是单个节点，则该节点是树的顺序遍历。如果树T是具有T1，T2，…，的树。。。，Tk子树和r作为根，然后按T1的顺序，然后按r的顺序，然后按T2，T3，…，的顺序遍历。。，Tk是T的顺序遍历。
T以左子右同级表示形式给出。C中节点的数据结构为：

struct node {
   int data;
   struct node *left-child;
   struct node *right-sibling;
}

树用指向根的指针表示。根不能有正确的同级<问题是要找到一种算法来按顺序遍历树。不允许递归。（递归算法很简单）
我试图将算法调整为二叉树，普通树<让我们考虑下面的树：

          1
      /   |   \
     2    3    4

这棵树的顺序是2 1 3 4。
如果我们考虑相应的二叉树：

           1
        /
       2
         \
           3
             \
               4

我们可以看到这个二叉树的顺序是2 3 4 1。我们可以看到普通树的顺序和二叉树之间没有对应关系。
我不知道如何按顺序遍历普通树。
到目前为止我所做的：
绕着树走是我们从根开始，逆时针方向移动，并尽可能靠近树的节点。
对于有序，我们第一次通过叶子时列出它，但第二次通过它时列出内部节点。
这是绕树散步的代码。这是快速黑客，所以我开放的建议和改进。

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

typedef struct tree_node {
  int data;
  struct tree_node *left_child;
  struct tree_node *right_sibling;
} tree_node;


typedef struct stack_node {
  tree_node *data;
  struct stack_node *next;
} stack_node;


void pop( stack_node **p_s )
{
  if( *p_s == NULL ) {
    printf("Error: The stack is empty\n");
  }
  else {
    stack_node *tmp = *p_s;
    *p_s = (*p_s)->next;
    free( tmp );
  }
}

tree_node *top( stack_node *s )
{
  return s->data;
}

void push( tree_node *p_n, stack_node **p_s )
{
  stack_node *tmp = malloc( sizeof( stack_node ) );
  tmp->data = p_n;
  tmp->next = *p_s;
  *p_s = tmp;
}

tree_node *read_tree( void )
{
  printf("Does this tree is empty (y/n):");
  int c = getchar();
  int c1;
  while(( c1 = getchar() ) != '\n' && c1 != EOF );
  if( c == 'y' ) return NULL;
  else {
    tree_node *tmp = malloc( sizeof( tree_node ) );
    tree_node *root = tmp;
    root->right_sibling = NULL;
    stack_node *s = malloc( sizeof( stack_node ) );
    s->data = root;
    s->next = NULL; //Initialize the stack;
    int num_nod;
  state1:
    tmp = top( s );
    printf("Input the data for the node:");
    scanf("%d", &(tmp->data) );
    printf("How many children does this node have (0 for none):");
    scanf("%d", &num_nod);
    if( num_nod == 0 ) {
      tmp->left_child = NULL;
      goto state2;
    }
    else {
      tree_node *tmp2 = malloc( sizeof( tree_node ) );
      push( tmp2, &s );
      tmp->left_child = tmp2;
      for( int i = 1; i < num_nod; i++ ) {
    tmp2->right_sibling = malloc( sizeof( tree_node ) );
    tmp2 = tmp2->right_sibling;
      }
      tmp2->right_sibling = NULL;
      goto state1;
    }
    state2: if( root == top( s ) ) return root;
      tree_node *tmp2 = top( s );
      tmp2 = tmp2->right_sibling;
      pop( &s );
      if( tmp2 == NULL )
    goto state2;
      else {
    push( tmp2, &s );
    goto state1;
      }
  }
}

void walk( tree_node *t )
{
  if( t == NULL ) return;
  stack_node *s = malloc( sizeof( stack_node ) );
  s->data = t;
  s->next = NULL; //Initialize the stack;
  tree_node *tmp;
  tree_node *tmp2;
  tree_node *tmp3;
  printf("%d ", t->data );//We have visited the root, so print it.
  state1:
  tmp = top( s );
  tmp2 = tmp->left_child;
  if( tmp2 == NULL ) {
    goto state2;
  }
  else {
    push( tmp2, &s );
    printf("%d ", tmp2->data );
    goto state1;
  }
  state2:
  tmp = top( s );
  tmp2 = tmp->right_sibling;
  if( tmp == t ) {
    return;
  }
  pop( &s );
  tmp3 = top( s );
  printf("%d ", tmp3->data );
  if( tmp2 == NULL ) goto state2;
  else {
    push( tmp2, &s );
    printf("%d ", tmp2->data );
    goto state1;
 }
} 

int main()
{
  tree_node *t = read_tree();
  walk( t );
}

我们可以通过以下方式实现有序算法。我们可以将指向它们的指针存储在列表中，而不是在walk（）函数中列出节点。然后我们可以分析列表中的内部节点，并在它们第二次出现在列表中时列出它们。但是，我不喜欢这个算法。它占用了太多的内存，而且速度很慢。欢迎任何想法。

Answer 1

我想我已经找到了答案：

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

typedef struct tree_node {
  int data;
  struct tree_node *left_child;
  struct tree_node *right_sibling;
} tree_node;


typedef struct stack_node {
  tree_node *data;
  struct stack_node *next;
} stack_node;


void pop( stack_node **p_s )
{
  if( *p_s == NULL ) {
    printf("Error: The stack is empty\n");
  }
  else {
    stack_node *tmp = *p_s;
    *p_s = (*p_s)->next;
    free( tmp );
  }
}

tree_node *top( stack_node *s )
{
  return s->data;
}

void push( tree_node *p_n, stack_node **p_s )
{
  stack_node *tmp = malloc( sizeof( stack_node ) );
  tmp->data = p_n;
  tmp->next = *p_s;
  *p_s = tmp;
}

tree_node *read_tree( void )
{
  printf("Does this tree is empty (y/n):");
  int c = getchar();
  int c1;
  while(( c1 = getchar() ) != '\n' && c1 != EOF );
  if( c == 'y' ) return NULL;
  else {
    tree_node *tmp = malloc( sizeof( tree_node ) );
    tree_node *root = tmp;
    root->right_sibling = NULL;
    stack_node *s = malloc( sizeof( stack_node ) );
    s->data = root;
    s->next = NULL; //Initialize the stack;
    int num_nod;
  state1:
    tmp = top( s );
    printf("Input the data for the node:");
    scanf("%d", &(tmp->data) );
    printf("How many children does this node have (0 for none):");
    scanf("%d", &num_nod);
    if( num_nod == 0 ) {
      tmp->left_child = NULL;
      goto state2;
    }
    else {
      tree_node *tmp2 = malloc( sizeof( tree_node ) );
      push( tmp2, &s );
      tmp->left_child = tmp2;
      for( int i = 1; i < num_nod; i++ ) {
    tmp2->right_sibling = malloc( sizeof( tree_node ) );
    tmp2 = tmp2->right_sibling;
      }
      tmp2->right_sibling = NULL;
      goto state1;
    }
    state2: if( root == top( s ) ) return root;
      tree_node *tmp2 = top( s );
      tmp2 = tmp2->right_sibling;
      pop( &s );
      if( tmp2 == NULL )
    goto state2;
      else {
    push( tmp2, &s );
    goto state1;
      }
  }
}

void nr_inorder( tree_node *t )
{
  if( t == NULL ) return;
  stack_node *s = malloc( sizeof( stack_node ) );
  s->data = t;
  s->next = NULL; //Initialize the stack;
  tree_node *tmp;
  tree_node *tmp2;
  tree_node *tmp3;
  state1:
  tmp = top( s );
  tmp2 = tmp->left_child;
  if( tmp2 == NULL ) { //tmp is a leaf so print it
    printf("%d ", tmp->data );
    goto state2;
  }
  else {
    push( tmp2, &s );
    goto state1;
  }
  state2:
  tmp = top( s );
  tmp2 = tmp->right_sibling;
  if( tmp == t ) {
    return;
  }
  pop( &s );
  tmp3 = top( s );
  if( (tmp3->left_child)->right_sibling == tmp2 ) /* This is the whole trick.
  Basically it states if we are visiting tmp3 for the second time then ... */
    printf("%d ", tmp3->data );
  if( tmp2 == NULL ) goto state2;
  else {
    push( tmp2, &s );
    goto state1;
 }
} 

int main()
{
  tree_node *t = read_tree();
  nr_inorder( t );
}  

这是一个快速破解，我不知道这是否是正确的答案。欢迎提出任何建议和改进。我在几棵树上试过，顺序是正确的。

Answer 2

没有递归的树的有序遍历的标准机制是使用额外的堆栈集合/数据结构。

interwebz提供了这个问题的解决方案，例如，这里有一个youtube视频：https://www.youtube.com/watch?v=kqdtyJPeJ8g