迭代Inorder遍历

这里是我的函数迭代inorder遍历。但是，当我执行它时，我得到了分段错误。我正在使用堆栈进行遍历。在给定的程序中，我还有一个递归函数用于inorder遍历来检查我的create（）函数是否正在工作。迭代Inorder遍历

我正在将节点推向堆栈并移动到节点的左侧，然后我弹出堆栈中的节点并打印它，并通过执行 root=root->rlink向右移动。

#include <stdio.h> 
#include <stdlib.h> 
typedef struct node 
{ 
int data; 
struct node *llink; 
struct node *rlink; 
}Node; 
typedef struct Stack 
{ 
Node *a[10]; 
int top; 
}stack; 
void push(stack *s,Node *root) 
{ 
if(s->top==9) 
    printf("FULL"); 
else 
{ 
    s->top++; 
    s->a[s->top]=root; 
} 
} 
Node *pop(stack *s) 
{ 
    if(s->top==-1) 
     printf("Empty"); 
    return s->a[s->top--]; 
} 
void inorder(Node *root) 
{ 
    stack s; 
    s.top=-1; 
    int flag=1; 
    while(flag) 
    { 
    if(s.top!=9) 
    { 
     push(&s,root); 
     root=root->llink; 
    } 
    else{ 
     if(s.top!=-1) 
     { 
      root=pop(&s); 
      printf("%d",root->data); 
      root=root->rlink; 
     } 
     else 
      flag=0; 
    } 
    } 
} 
void inor(Node *root) 
{ 
if(root!=NULL) 
{ 
inor(root->llink); 
printf("%d",root->data); 
inor(root->rlink); 
} 
} 
Node *create(Node *root,int key) 
{ 
if(root==NULL) 
{ 
root=(Node *)malloc(sizeof(Node)); 
root->data=key; 
root->rlink=root->llink=NULL; 
} 
else 
{ 
if(key>root->data) 
{ 
    root->rlink=create(root->rlink,key); 
} 
else if(key<root->data) 
{ 
root->llink=create(root->llink,key); 
} 
} 
return root; 
} 
int main() 
{ 
    Node *h=NULL; 
    h=create(h,5); 
    h=create(h,1); 
    h=create(h,3); 
    h=create(h,8); 
    h=create(h,12); 
    h=create(h,51); 
    inorder(h); 
    //inor(h); 
}

来源

2016-11-13 Sagar Goyal

你有使用调试器立即找出哪一行导致了赛格故障和跟踪程序的执行？ – kaylum

确保您使用换行符终止诊断打印消息（或使用'fflush（stdout）;'） - 否则，如果代码崩溃，您可能永远看不到该消息，从而给您提供有关崩溃发生位置的错误印象。 –

@kaylum是啊，我做到了，但我不能弄明白 –

如确诊我的主要comment，问题是，你的代码并没有停止向左穿越时是朝着这一方向没有进一步的节点。解决方法是简单的：

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

typedef struct node 
{ 
    int data; 
    struct node *llink; 
    struct node *rlink; 
} Node; 

typedef struct Stack 
{ 
    Node *a[10]; 
    int top; 
} stack; 

static 
void push(stack *s, Node *root) 
{ 
    if (s->top == 9) 
     printf("FULL\n"); 
    else 
    { 
     s->top++; 
     s->a[s->top] = root; 
    } 
} 

static 
Node *pop(stack *s) 
{ 
    if (s->top == -1) 
     printf("Empty\n"); 
    return s->a[s->top--]; 
} 

static 
void inorder(Node *root) 
{ 
    stack s; 
    s.top = -1; 
    int flag = 1; 
    while (flag) 
    { 
     //printf("I: %p\n", (void *)root); 
     if (s.top != 9 && root != 0) 
     { 
      push(&s, root); 
      root = root->llink; 
     } 
     else 
     { 
      if (s.top != -1) 
      { 
       root = pop(&s); 
       printf(" %d", root->data); 
       root = root->rlink; 
      } 
      else 
       flag = 0; 
     } 
    } 
} 

static 
void inor(Node *root) 
{ 
    if (root != NULL) 
    { 
     inor(root->llink); 
     printf(" %d", root->data); 
     inor(root->rlink); 
    } 
} 

static 
Node *create(Node *root, int key) 
{ 
    if (root == NULL) 
    { 
     root = (Node *)malloc(sizeof(Node)); 
     root->data = key; 
     root->rlink = root->llink = NULL; 
    } 
    else 
    { 
     if (key > root->data) 
     { 
      root->rlink = create(root->rlink, key); 
     } 
     else if (key < root->data) 
     { 
      root->llink = create(root->llink, key); 
     } 
    } 
    return root; 
} 

int main(void) 
{ 
    int nodes[] = { 37, 2, 19, 9, 7, 41 }; 
    enum { NUM_NODES = sizeof(nodes)/sizeof(nodes[0]) }; 
    Node *h = NULL; 
    h = create(h, 5); 
    h = create(h, 1); 
    h = create(h, 3); 
    h = create(h, 8); 
    h = create(h, 12); 
    h = create(h, 51); 
    printf("Recursive:\n"); 
    inor(h); 
    putchar('\n'); 
    printf("Iterative:\n"); 
    inorder(h); 
    putchar('\n'); 

    for (int i = 0; i < NUM_NODES; i++) 
    { 
     h = create(h, nodes[i]); 
     printf("Iterative:\n"); 
     inorder(h); 
     putchar('\n'); 
    } 
}

我用static的功能，因为我的默认编译器选项需要的功能被宣布或使用之前定义的，并且可以在不预先声明的定义仅static功能：

gcc -O3 -g -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes -Wold-style-definition it37.c -o it37

你可以自己决定是否对你很重要（但我注意到除了这个文件之外，没有其他文件需要访问这些函数，所以'信息隐藏'暗示函数应该是static）。

输出示例：

Recursive: 
1 3 5 8 12 51 
Iterative: 
1 3 5 8 12 51 
Iterative: 
1 3 5 8 12 37 51 
Iterative: 
1 2 3 5 8 12 37 51 
Iterative: 
1 2 3 5 8 12 19 37 51 
Iterative: 
1 2 3 5 8 9 12 19 37 51 
Iterative: 
1 2 3 5 7 8 9 12 19 37 51 
Iterative: 
1 2 3 5 7 8 9 12 19 37 41 51

来源

2016-11-13 06:34:35

如上评论给出的“根”在你的代码总是得到左节点的分配的地址，当叶节点达到它在它和你有“NULL”值不能访问null，这就是为什么你的代码失败并会给你分段错误的原因。

反正这里是我的代码解决您的错误

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


typedef struct node 
{ 
    int data; 
    struct node *llink; 
    struct node *rlink; 
}Node; 


typedef struct Stack 
{ 
    Node *a[10]; 
    int top; 
}stack; 

void push(stack *s,Node *root); 
Node *pop(stack *s); 
void inorder(Node *root); 



void push(stack *s,Node *root) 
{ 
    if(s->top==9) 
    { 
     printf("FULL"); 
    } 
    else 
    { 
     s->top++; 
     s->a[s->top]=root; 
    } 
} 


Node *pop(stack *s) 
{ 
    if(s->top==-1) 
    { 
     printf("Empty"); 
     return NULL; 
    } 

    return s->a[s->top--]; 
} 
void inorder(Node *root) 
{ 
    stack *s;// took it as a pointer so that i could use it easily 
    s=(stack *)malloc(sizeof(stack)); 
    s->top=-1;//initialized to -1 because we increment top then insert at location indicated by top 
    int flag=1; 
    bool traverse_left=true; 

    while(flag) 
    { 
     if(root->llink!=NULL && traverse_left)//if left link available go left 
     { 
      push(s,root); 
      root=root->llink; 
     } 
     else if((root->llink==NULL&&root->rlink!=NULL)||(root->llink!=NULL && !traverse_left)) 
     { 
      printf("%d ",root->data); 
      root=root->rlink; 
      traverse_left=true; 
     } 
     else if(root->llink==NULL&&root->rlink==NULL) 
     { 
      printf("%d ",root->data); 
      if(root->llink==NULL&&root->rlink==NULL&&s->top==-1) 
      { 
       flag=0; 
      } 
      else 
      { 
       root=pop(s); 
      } 
      traverse_left=false; 
     } 


    } 
} 


void inor(Node *root) 
{ 
    if(root!=NULL) 
    { 
     inor(root->llink); 
     printf("%d",root->data); 
     inor(root->rlink); 
    } 
} 

Node *create(Node *root,int key) 
{ 
    if(root==NULL) 
    { 
     root=(Node *)malloc(sizeof(Node)); 
     root->data=key; 
     root->rlink=root->llink=NULL; 
    } 

    else 
    { 
     if(key>root->data) 
     { 
      root->rlink=create(root->rlink,key); 
     } 
     else if(key<root->data) 
     { 
      root->llink=create(root->llink,key); 
     } 
    } 

return root; 
} 
int main() 
{ 
    Node *h=NULL; 

    h=create(h,5); 
    h=create(h,1); 
    h=create(h,3); 
    h=create(h,8); 
    h=create(h,12); 
    h=create(h,51); 

    inorder(h); 
    //inor(h); 
}

在这个程序中，每当我们走了左节点我把节点栈之前，我们转移到左节点
如果堆栈包含左节点，则遍历回来，这意味着我们已经遍历了它的左树，所以我弹出它并开始遍历它的右子树
如果一个节点的左和右指针为空我从弹出堆栈中的节点，并开始遍历它的右子树

如果你有关于这个答案请评论有任何怀疑。

来源

2016-11-16 17:13:24

序遍历：左，父母，右

使用堆栈迭代遍历的核心思想是：

往左（也推入堆栈），直到找到null。
运行while循环直到堆栈为空。每次弹出顶部元素时，将其添加到结果列表中。然后，如果右边的孩子存在，去右边的孩子（也推入堆栈），然后向左（也推入堆栈），直到null找到。所以基本上第1步的代码将被复制到while循环中。

代码如下所示：

class Node { 
    int key; 
    Node left, right; 

    public Node() {} 

    public Node(int key) { 
     this.key = key; 
    } 
} 
public List<Integer> inOrderIterative() { 
    List<Integer> list = new ArrayList<>(); 
    Stack<Node> nodeStack = new Stack<>(); 
    Node current = root; 
    nodeStack.push(current); 
    while (null != current.left) { 
     current = current.left; 
     nodeStack.push(current); 
    } 

    while(!nodeStack.empty()) { 
     current = nodeStack.pop(); 
     list.add(current.key); 

     if (null != current.right) { 
      current = current.right; 
      nodeStack.push(current); 
      while (null != current.left) { 
       current = current.left; 
       nodeStack.push(current); 
      } 
     } 
    } 

    return list; 
}

来源

2018-01-30 14:08:23

迭代Inorder遍历

回答

相关问题