遍历二叉树 数据结构（C语言）

建立二叉树时按先序输入的结点序列为： abc000de0f00g00。

1. 建立二叉树的二叉链表表示，非递归后序遍历二叉树。
2. 建立二叉树的三叉链表表示，无栈非递归后序遍历二叉树。

下面是建立二叉树的二叉链表表示，并使用非递归后序遍历二叉树的代码：

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

typedef char ElementType;

typedef struct TreeNode *BinaryTree;
struct TreeNode {
    ElementType data;
    BinaryTree left;
    BinaryTree right;
};

BinaryTree CreateBinaryTree(char *str) {
    BinaryTree t;
    char c = *str;
    if (c == '\0') return NULL;

    t = (BinaryTree)malloc(sizeof(struct TreeNode));
    t->data = c;
    t->left = CreateBinaryTree(str + 1);
    t->right = CreateBinaryTree(str + 1 + strlen(t->left));

    return t;
}

void NonRecursivePostOrder(BinaryTree t) {
    BinaryTree stack[100];
    int top = -1;
    BinaryTree p = t;

    while (p != NULL || top >= 0) {
        while (p != NULL) {
            stack[++top] = p;
            p = p->left;
        }

        if (top > 0) {
            if (stack[top - 1]->right == NULL) {
                p = stack[--top];
                printf("%c ", p->data);
                while (top >= 0 && stack[top]->right == p) {
                    p = stack[top--];
                    printf("%c ", p->data);
                }
            }
            if (top >= 0) p = stack[top]->right;
        }
        else p = NULL;
    }
}

int main() {
    char str[] = "abc000de0f00g00";
    BinaryTree t = CreateBinaryTree(str);

    NonRecursivePostOrder(t);
    printf("\n");

    return 0;
}

下面是建立二叉树的三叉链表表示，并使用无栈非递归后序遍历二叉树的代码：

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

typedef char ElementType;

typedef struct TreeNode *BinaryTree;
struct TreeNode {
    ElementType data;
    BinaryTree left;
    BinaryTree right;
    BinaryTree middle;
};

BinaryTree CreateBinaryTree(char *str) {
    BinaryTree t;
    char c = *str;
    if (c == '\0') return NULL;

    t = (BinaryTree)malloc(sizeof(struct TreeNode));
    t->data = c;
    t->left = CreateBinaryTree(str + 1);
    t->middle = CreateBinaryTree(str + 1 + strlen(t->left));
    t->right = CreateBinaryTree(str + 1 + strlen(t->left) + strlen(t->middle));
    return t;
}
void NonRecursivePostOrder(BinaryTree t) {
    BinaryTree p = t;
    BinaryTree q = NULL;
    while (p != NULL) {
        while (p->left != NULL) {
            p->left->right = p;
            p = p->left;
        }

        while (p->right == NULL || p->right == q) {
            printf("%c ", p->data);
            q = p;
            if (p->middle != NULL) {
                p = p->middle;
                break;
            }
            p = p->right;
        }
        if (p->right != NULL) {
            p->right->left = p;
            p = p->right;
        }
    }
}
int main() {
    char str[] = "abc000de0f00g00";
    BinaryTree t = CreateBinaryTree(str);
    NonRecursivePostOrder(t);
    printf("\n");

    return 0;
}

希望这些代码能帮到你！

// Q1054302.cpp : Defines the entry point for the console application.
//
#include<stdio.h>
#include<stdlib.h>
typedef struct treeNode//定义
{
    int data;
    treeNode *left;
    treeNode *right;
} treenode, *TreeNode;
void pre(TreeNode node)//前序遍历
{
    if(node==NULL)
        return ;
    printf("%d ", node->data);
    pre(node->left);
    pre(node->right);
}
void mid(TreeNode node)//中序遍历
{
    if(node==NULL)
        return ;
    mid(node->left);
    printf("%d ", node->data);
    mid(node->right);
}
void beh(TreeNode node)//后序遍历
{
    if(node==NULL)
        return ;
    beh(node->left);
    beh(node->right);
    printf("%d ", node->data);
}
void tree(TreeNode one)//定义一个现成的二叉树
{
    one->data=3;
    one->left=(treenode*)malloc(sizeof(treenode));
        one->left->data=9;
        one->left->left=NULL;
        one->left->right=NULL;
    one->right=(treenode*)malloc(sizeof(treenode));
        one->right->data=20;
        one->right->left=(treenode*)malloc(sizeof(treenode));
            one->right->left->data=15;
            one->right->left->left=NULL;
            one->right->left->right=NULL;
        one->right->right=(treenode*)malloc(sizeof(treenode));
            one->right->right->data=7;
            one->right->right->left=NULL;
            one->right->right->right=NULL;
}
int main()//主方法
{
    TreeNode  one;
    one=(treenode*)malloc(sizeof(treenode));
    tree(one);
    printf("该二叉树的前序遍历为:\n");
    pre(one);
    printf("\n该二叉树的中序遍历为:\n");
    mid(one);
    printf("\n该二叉树的后序遍历为:\n");
    beh(one);
}

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

#define MAXSIZE 100

typedef struct BiTreeNode
{
    char data;
    struct BiTreeNode *left;
    struct BiTreeNode *right;
}BiTreeNode,*BiTree;

void CreateBiTree(BiTree *T)
{
    char val;
    scanf("%c",&val);

    if(val == '#')
        *T = NULL;

    else
    {
        *T = (BiTree)malloc(sizeof(BiTreeNode));
        (*T)->data = val;
        CreateBiTree(&(*T)->left);
        CreateBiTree(&(*T)->right);
    }
}

void PreOrderTravel(BiTree T)
{
    if(T==NULL)
        return;
    printf("%c ",T->data);
    PreOrderTravel(T->left);
    PreOrderTravel(T->right);
}

void TailOrderTravel(BiTree T)
{
    if(T==NULL)
        return;
    TailOrderTravel(T->left);
    TailOrderTravel(T->right);
    printf("%c ",T->data);
}

int main()
{
 
    printf("请输入测试代码：\n");
    BiTree T;
    T=(BiTree)malloc(sizeof(BiTreeNode));
 
    printf("请将二叉树按照先序方式依次输入结点的值(空结点为#):\n");
    CreateBiTree(&T);
 
    printf("先序方式遍历结果：\n");
    PreOrderTravel(T);
    printf("\n");
 
    printf("后序方式遍历结果：\n");
    TailOrderTravel(T);
    printf("\n");
    return 0;
}

望采纳，谢谢

chatgpt可以解决你的问题[🐩]

三叉链表就是比二叉链表的结点多存储一个指向本结点双亲的指针，其他没啥区别。

// Q1054302.cpp : Defines the entry point for the console application.
//
#include<stdio.h>
#include<stdlib.h>
typedef struct treeNode//定义
{
    int data;
    treeNode *left;
    treeNode *right;
} treenode, *TreeNode;
void pre(TreeNode node)//前序遍历
{
    if(node==NULL)
        return ;
    printf("%d ", node->data);
    pre(node->left);
    pre(node->right);
}
void mid(TreeNode node)//中序遍历
{
    if(node==NULL)
        return ;
    mid(node->left);
    printf("%d ", node->data);
    mid(node->right);
}
void beh(TreeNode node)//后序遍历
{
    if(node==NULL)
        return ;
    beh(node->left);
    beh(node->right);
    printf("%d ", node->data);
}
void tree(TreeNode one)//定义一个现成的二叉树
{
    one->data=3;
    one->left=(treenode*)malloc(sizeof(treenode));
        one->left->data=9;
        one->left->left=NULL;
        one->left->right=NULL;
    one->right=(treenode*)malloc(sizeof(treenode));
        one->right->data=20;
        one->right->left=(treenode*)malloc(sizeof(treenode));
            one->right->left->data=15;
            one->right->left->left=NULL;
            one->right->left->right=NULL;
        one->right->right=(treenode*)malloc(sizeof(treenode));
            one->right->right->data=7;
            one->right->right->left=NULL;
            one->right->right->right=NULL;
}
int main()//主方法
{
    TreeNode  one;
    one=(treenode*)malloc(sizeof(treenode));
    tree(one);
    printf("该二叉树的前序遍历为:\n");
    pre(one);
    printf("\n该二叉树的中序遍历为:\n");
    mid(one);
    printf("\n该二叉树的后序遍历为:\n");
    beh(one);
}