C语言二叉树中序遍历的递归和迭代实现

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

typedef struct TreeNode { int data; struct TreeNode* Lsubtree; struct TreeNode* Rsubtree; } TNode;

typedef struct StackNode { TNode* data; struct StackNode* next; } StackNode;

typedef struct Stack { StackNode* top; } Stack;

void InitStack(Stack* s) { s->top = NULL; }

int EmptyStack(Stack* s) { return (s->top == NULL); }

void PushStack(Stack* s, TNode* data) { StackNode* new_node = (StackNode*)malloc(sizeof(StackNode)); new_node->data = data; new_node->next = s->top; s->top = new_node; }

TNode* PopStack(Stack* s) { if (EmptyStack(s)) { return NULL; } TNode* data = s->top->data; StackNode* temp = s->top; s->top = s->top->next; free(temp); return data; }

void Access(int data) { printf("%d ", data); }

void InOrder(TNode* tree) { if (tree != NULL) { InOrder(tree->Lsubtree); Access(tree->data); InOrder(tree->Rsubtree); } }

void InOrderIterative(TNode* tree) { TNode* p = tree; Stack S; InitStack(&S); do { while (p != NULL) { PushStack(&S, p); p = p->Lsubtree; } if (!EmptyStack(&S)) { p = PopStack(&S); Access(p->data); p = p->Rsubtree; } } while (!EmptyStack(&S) || p != NULL); }

int main() { TNode* root = (TNode*)malloc(sizeof(TNode)); root->data = 1; root->Lsubtree = (TNode*)malloc(sizeof(TNode)); root->Lsubtree->data = 2; root->Lsubtree->Lsubtree = NULL; root->Lsubtree->Rsubtree = NULL; root->Rsubtree = (TNode*)malloc(sizeof(TNode)); root->Rsubtree->data = 3; root->Rsubtree->Lsubtree = (TNode*)malloc(sizeof(TNode)); root->Rsubtree->Lsubtree->data = 4; root->Rsubtree->Lsubtree->Lsubtree = NULL; root->Rsubtree->Lsubtree->Rsubtree = NULL; root->Rsubtree->Rsubtree = (TNode*)malloc(sizeof(TNode)); root->Rsubtree->Rsubtree->data = 5; root->Rsubtree->Rsubtree->Lsubtree = NULL; root->Rsubtree->Rsubtree->Rsubtree = NULL;

printf("Recursive InOrder Traversal: ");
InOrder(root);
printf("\n");

printf("Iterative InOrder Traversal: ");
InOrderIterative(root);
printf("\n");

return 0;

}