设为首页收藏本站
切换到窄版

鱼C论坛

 找回密码
 立即注册
鱼C论坛»论坛 › 技术交流 › 数据结构与算法 › 二叉树的非递归算法
返回列表 发新帖
查看: 827|回复: 4

[已解决]二叉树的非递归算法

[复制链接]
白痴爱面包
发表于 2023-4-18 16:33:37 | 显示全部楼层 |阅读模式

马上注册，结交更多好友，享用更多功能^_^

您需要 登录 才可以下载或查看，没有账号？立即注册

x
分别设计出先序、中序和后序遍历二叉树的非递归算法。
最佳答案
月排行榜 / 总排行榜
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[stack->top--];
}

先序遍历非递归算法：
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);
}

现在，你可以使用这些非递归算法来分别实现二叉树的先序、中序和后序遍历。这些算法的基本思路是使用一个栈来存储遍历过程中的节点，这样就可以避免使用递归。栈的大小可以根据实际情况调整。当遍历完整棵树时，释放栈所占用的内存。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复

使用道具 举报

爱意随风起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
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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[stack->top--];
}

先序遍历非递归算法：
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);
}

现在，你可以使用这些非递归算法来分别实现二叉树的先序、中序和后序遍历。这些算法的基本思路是使用一个栈来存储遍历过程中的节点，这样就可以避免使用递归。栈的大小可以根据实际情况调整。当遍历完整棵树时，释放栈所占用的内存。
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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);
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

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;
        }
    }
}

[b]先序遍历:[b]
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 + " ");
    }
}
想知道小甲鱼最近在做啥？请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

返回列表 发新帖
高级模式
B Color Image Link Quote Code Smilies
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-11-21 19:06

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表