Итеративный обход номера

Question

Вот моя функция для итеративного обхода порядка. Но когда я его выполняю, я получаю ошибку сегментации. Я использую стек для обхода. В данной программе у меня также есть рекурсивная функция для обхода порядка, чтобы проверить, работает ли моя функция create().

Я нажимаю узел в стек и перемещаюсь влево от узла, после чего я вывожу узел из стека и печатаю его и направо, делая 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); 
} 

Answer 1

Как диагностируется в моей основной 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 

Answer 2

Как приведено в вышеупомянутых комментариях, «корень» в вашем коде всегда есть назначенный адрес левого узла и при достижении листового узла он имел значение «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); 
} 

• В этой программе каждый раз, когда мы идем на левый узел я положил этот узел в стека, прежде чем мы перешли на левый узел

• при прохождении назад, если стек содержит левый узел, это означает, что мы уже прошли левое дерево, поэтому я поплю его и начинаю пересекать его правое вспомогательное дерево.

• , если левые и правые указатели Узла являются нулем я выскочить узел из стека и начать обход его право поддерева дереву

Если у вас есть какие-либо сомнения относительно этого ответа, пожалуйста, комментария.

Answer 3

Симметричный обход: левый, родитель, право

Ключевая идея итерационного обхода с использованием стеки:

1. Идите налево (также надавите в стек) до null найдены.

2. Выполняйте цикл while до тех пор, пока стек не будет пустым. Каждый раз, когда pop pop element, добавьте его в список результатов. Тогда, если существует правильный ребенок, перейдите к правильному ребенку (также нажмите в стек), а затем идите влево (также нажмите в стек), пока не найдете 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; 
}