二叉树的非递归算法,数据结构与算法,技术交流,鱼C论坛

白痴爱面包 发表于 2023-4-18 16:33:37

二叉树的非递归算法

分别设计出先序、中序和后序遍历二叉树的非递归算法。

爱意随风起9306 发表于 2023-4-18 16:39:50

#二叉树遍历操作实现的非递归算法
#先序遍历
def preOrder2(root):
p = root
s = LinkStack()
s.push(p)
while not s.isEmpty():
   p = s.pop()
   print(p.data,end=' ')
   while p is not None:
         if p.rchild is not None:
            print(p.lchild.data,end=' ')
         if p.lchild is not None:
            s.push(p.rchild)
            p = p.lchild
#中序遍历
def inOeder2(root):
p = root
s = LinkStack()
s.push(p)
while not s.isEmpty():
   while p.lchild is not None:
         p = p.lchild
         s.push(p)
   p = p.pop()
   print(p.data,end=' ')
   if p.rchild is not None:
         s.push(p.rchild)
#后序遍历
def postOrder2(root):
p = root
t = None
flag = False
s = LinkStack()
if p is not None:
   s.push(p)
   while p.lchild is None:
         p = p.push(p)
         s.push(p)
   while not s.isEmpty() and flag:
         if p.rchild == t or p.rchild is None:
            print(p.data,end=' ')
            flag = True
            t = p
            s.pop
         else:
            s.push(p.rchild)
            flag = False

isdkz 发表于 2023-4-18 16:42:05

以下是C语言中实现二叉树非递归遍历的代码。这里提供了先序、中序和后序遍历的非递归算法。

首先，定义二叉树结构体：
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

接下来，定义栈结构体：
typedef struct Stack {
TreeNode **array;
int top;
int size;
} Stack;

Stack *createStack(int size) {
Stack *stack = (Stack *)malloc(sizeof(Stack));
stack->array = (TreeNode **)malloc(size * sizeof(TreeNode *));
stack->top = -1;
stack->size = size;
return stack;
}

bool isStackEmpty(Stack *stack) {
return stack->top == -1;
}

bool isStackFull(Stack *stack) {
return stack->top == stack->size - 1;
}

void push(Stack *stack, TreeNode *node) {
if (isStackFull(stack)) return;
stack->array[++stack->top] = node;
}

TreeNode *pop(Stack *stack) {
if (isStackEmpty(stack)) return NULL;
return stack->array;
}

先序遍历非递归算法：
void preorderTraversal(TreeNode *root) {
if (root == NULL) return;
Stack *stack = createStack(100); // 根据实际情况调整栈大小
TreeNode *node = root;

while (node != NULL || !isStackEmpty(stack)) {
   while (node != NULL) {
         printf("%d ", node->val);
         push(stack, node);
         node = node->left;
   }
   node = pop(stack);
   node = node->right;
}

free(stack->array);
free(stack);
}

中序遍历非递归算法：
void inorderTraversal(TreeNode *root) {
if (root == NULL) return;
Stack *stack = createStack(100); // 根据实际情况调整栈大小
TreeNode *node = root;

while (node != NULL || !isStackEmpty(stack)) {
   while (node != NULL) {
         push(stack, node);
         node = node->left;
   }
   node = pop(stack);
   printf("%d ", node->val);
   node = node->right;
}

free(stack->array);
free(stack);
}

后序遍历非递归算法：
void postorderTraversal(TreeNode *root) {
if (root == NULL) return;
Stack *stack = createStack(100); // 根据实际情况调整栈大小
Stack *output = createStack(100); // 存储后序遍历结果的栈
TreeNode *node = root;

while (node != NULL || !isStackEmpty(stack)) {
   while (node != NULL) {
         push(output, node);
         push(stack, node);
         node = node->right;
   }
   node = pop(stack);
   node = node->left;
}

while (!isStackEmpty(output)) {
   printf("%d ", pop(output)->val);
}

free(stack->array);
free(stack);
free(output->array);
free(output);
}

现在，你可以使用这些非递归算法来分别实现二叉树的先序、中序和后序遍历。这些算法的基本思路是使用一个栈来存储遍历过程中的节点，这样就可以避免使用递归。栈的大小可以根据实际情况调整。当遍历完整棵树时，释放栈所占用的内存。

wuliangtdi 发表于 2023-4-18 17:10:47

本帖最后由 wuliangtdi 于 2023-4-18 17:20 编辑

C语言版
先定义一些内容:
typedef struct StackNode {
void* data;
struct StackNode* next;
} StackNode;

typedef struct Stack {
StackNode* top;
int size;
} Stack;

Stack* createStack() {
Stack* stack = (Stack*)malloc(sizeof(Stack));
stack->top = NULL;
stack->size = 0;
return stack;
}

void destroyStack(Stack* stack) {
if (stack == NULL) return;
while (!isEmpty(stack)) {
   StackNode* node = stack->top;
   stack->top = stack->top->next;
   free(node);
   stack->size--;
}
free(stack);
}

bool isEmpty(Stack* stack) {
return stack->top == NULL;
}

void push(Stack* stack, void* data) {
StackNode* node = (StackNode*)malloc(sizeof(StackNode));
node->data = data;
node->next = stack->top;
stack->top = node;
stack->size++;
}

void* pop(Stack* stack) {
if (isEmpty(stack)) return NULL;
StackNode* node = stack->top;
void* data = node->data;
stack->top = stack->top->next;
free(node);
stack->size--;
return data;
}

前序遍历:
void preorderTraversal(TreeNode* root) {
if (root == NULL) return;

Stack* stack = createStack();
push(stack, root);

while (!isEmpty(stack)) {
   TreeNode* node = (TreeNode*)pop(stack);
   printf("%d ", node->val);

   if (node->right != NULL) push(stack, node->right);
   if (node->left != NULL) push(stack, node->left);
}

destroyStack(stack);
}

中序遍历:
void inorderTraversal(TreeNode* root) {
if (root == NULL) return;

Stack* stack = createStack();
TreeNode* node = root;

while (!isEmpty(stack) || node != NULL) {
   if (node != NULL) {
         push(stack, node);
         node = node->left;
   } else {
         node = (TreeNode*)pop(stack);
         printf("%d ", node->val);
         node = node->right;
   }
}

destroyStack(stack);
}

后序遍历:
void postorderTraversal(TreeNode* root) {
if (root == NULL) return;

Stack* stack1 = createStack();
Stack* stack2 = createStack();

push(stack1, root);

while (!isEmpty(stack1)) {
   TreeNode* node = (TreeNode*)pop(stack1);
   push(stack2, node);

   if (node->left != NULL) push(stack1, node->left);
   if (node->right != NULL) push(stack1, node->right);
}

while (!isEmpty(stack2)) {
   TreeNode* node = (TreeNode*)pop(stack2);
   printf("%d ", node->val);
}

destroyStack(stack1);
destroyStack(stack2);
}

wuliangtdi 发表于 2023-4-18 17:19:01

java版:
先定义一些内容
public class TreeNode {
int val;
TreeNode left;
TreeNode right;

public TreeNode(int val) {
   this.val = val;
   left = null;
   right = null;
}
}
//实现泛型栈
public class Stack<T> {
private Node<T> top;
private int size;

public Stack() {
   top = null;
   size = 0;
}

public void push(T data) {
   Node<T> node = new Node<>(data);
   node.next = top;
   top = node;
   size++;
}

public T pop() {
   if (isEmpty()) return null;
   T data = top.data;
   top = top.next;
   size--;
   return data;
}

public T peek() {
   if (isEmpty()) return null;
   return top.data;
}

public boolean isEmpty() {
   return top == null;
}

public int size() {
   return size;
}

private static class Node<T> {
   T data;
   Node<T> next;

   public Node(T data) {
         this.data = data;
         next = null;
   }
}
}

先序遍历:
public void preorderTraversal(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
stack.push(root);

while (!stack.isEmpty()) {
   TreeNode node = stack.pop();
   System.out.print(node.val + " ");

   if (node.right != null) stack.push(node.right);
   if (node.left != null) stack.push(node.left);
}
}

中序遍历:
public void inorderTraversal(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack = new Stack<>();
TreeNode node = root;

while (!stack.isEmpty() || node != null) {
   if (node != null) {
         stack.push(node);
         node = node.left;
   } else {
         node = stack.pop();
         System.out.print(node.val + " ");
         node = node.right;
   }
}
}

后序遍历:
public void postorderTraversal(TreeNode root) {
if (root == null) return;
Stack<TreeNode> stack1 = new Stack<>();
Stack<TreeNode> stack2 = new Stack<>();
stack1.push(root);

while (!stack1.isEmpty()) {
   TreeNode node = stack1.pop();
   stack2.push(node);

   if (node.left != null) stack1.push(node.left);
   if (node.right != null) stack1.push(node.right);
}

while (!stack2.isEmpty()) {
   TreeNode node = stack2.pop();
   System.out.print(node.val + " ");
}
}

页: [1]

鱼C论坛's Archiver

二叉树的非递归算法