首页 > 其他分享 >广义表转二叉树

广义表转二叉树

时间：2022-10-15 23:13:12浏览次数：53  
标签：node Node return 表转 Tree tree 二叉树 广义 stack

前序遍历和中序遍历 & 后序遍历和中序遍历可以还原出唯一的二叉树，而前序遍历和后序遍历不行（满二叉树时貌似可以，但只有一个根节点和一个子孩子时一定不行）

//输入：
A(B(, D), C(E))
//输出：
preorder: A B D C E
inorder: B D A E C
postorder: D B E C A

自定义栈

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

typedef struct Node {
    char data;
    Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree;

typedef struct Stack {
    Node **data;
    int size, length;
} Stack;

Node *getNewNode(char data);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
Tree *build_tree(const char *str);
void preorder_node(Node *node);
void preorder(Tree *tree);
void inorder_node(Node *node);
void inorder(Tree *tree);
void postorder_node(Node *node);
void postorder(Tree *tree);

Stack *init_stack(int size);
void clear_stack(Stack *stack);
int push(Stack *stack, Node *val);
Node *top(Stack *stack);
int empty(Stack *stack);
int pop(Stack *stack);

int main() {
    char str[1000] = {0};
    scanf("%[^\n]s", str);
    getchar(); //读走scanf遗留下的'\n'（惯常操作）
    Tree *tree = build_tree(str);
    preorder(tree);
    inorder(tree);
    postorder(tree);
    clear_tree(tree);
    return 0;
}

Node *getNewNode(char data) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

Tree *getNewTree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->length = 0;
    return tree;
}

void clear_node(Node *node) {
    if (node == NULL) return;
    clear_node(node->lchild);
    clear_node(node->rchild);
    free(node);
    return;
}

void clear_tree(Tree *tree) {
    if (tree == NULL) return;
    clear_node(tree->root);
    free(tree);
    return;
}

//结构操作：广义表转二叉树
Tree *build_tree(const char *str) {
    Tree *tree = getNewTree();
    Stack *stack = init_stack(strlen(str));
    Node *node = NULL;
    int flag = 0;
    while (str[0]) {
        switch (str[0]) {
            case '(':
                push(stack, node);
                flag = 0;
                break;
            case ')':
                pop(stack);
                break;
            case ',':
                flag = 1;
                break;
            case ' ':
                break;
            default:
                node = getNewNode(str[0]);
                if (empty(stack)) {
                    tree->root = node;
                } else if (flag == 0) {
                    top(stack)->lchild = node;
                } else {
                    top(stack)->rchild = node;
                }
                tree->length += 1;
                break;
        }
        str++;
    }
    clear_stack(stack);
    return tree;
}

//结构操作：前序遍历的递归操作
void preorder_node(Node *node) {
    if (node == NULL) return;
    printf("%c ", node->data);
    preorder_node(node->lchild);
    preorder_node(node->rchild);
    return;
}

//结构操作：用前序遍历的方式输出所有元素
void preorder(Tree *tree) {
    if (tree == NULL) return;
    printf("preorder: ");
    preorder_node(tree->root);
    printf("\n");
    return;
}

//结构操作：中序遍历的递归操作
void inorder_node(Node *node) {
    if (node == NULL) return;
    inorder_node(node->lchild);
    printf("%c ", node->data);
    inorder_node(node->rchild);
    return;
}

//结构操作：用中序遍历的方式输出所有元素
void inorder(Tree *tree) {
    if (tree == NULL) return;
    printf("inorder: ");
    inorder_node(tree->root);
    printf("\n");
    return;
}

//结构操作：后序遍历的递归操作
void postorder_node(Node *node) {
    if (node == NULL) return;
    postorder_node(node->lchild);
    postorder_node(node->rchild);
    printf("%c ", node->data);
    return;
}

//结构操作：用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
    if (tree == NULL) return;
    printf("postorder: ");
    postorder_node(tree->root);
    printf("\n");
    return;
}

Stack *init_stack(int size) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->data = (Node **)malloc(sizeof(Node *) * size);
    stack->size = size;
    stack->length = 0;
    return stack;
}

void clear_stack(Stack *stack) {
    if (stack == NULL) return;
    free(stack->data);
    free(stack);
    return;
}

int push(Stack *stack, Node *val) {
    if (stack == NULL) return 0;
    if (stack->length == stack->size) return 0;
    stack->data[stack->length++] = val;
    return 1;
}

Node *top(Stack *stack) {
    return stack->data[stack->length - 1];
}

int empty(Stack *stack) {
    return stack->length == 0;
}

int pop(Stack *stack) {
    if (stack == NULL) return 0;
    if (empty(stack)) return 0;
    stack->length -= 1;
    return 1;
}

系统栈(递归)

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

typedef struct Node {
    char data;
    Node *lchild, *rchild;
} Node;

typedef struct Tree {
    Node *root;
    int length;
} Tree;

typedef struct Stack {
    Node **data;
    int size, length;
} Stack;

Node *getNewNode(char data);
Tree *getNewTree();
void clear_node(Node *node);
void clear_tree(Tree *tree);
char *build_recur(char *str, Node *last_node, Tree *tree);
Tree *build_tree(char *str);
void preorder_node(Node *node);
void preorder(Tree *tree);
void inorder_node(Node *node);
void inorder(Tree *tree);
void postorder_node(Node *node);
void postorder(Tree *tree);

int main() {
    char str[1000] = {0};
    scanf("%[^\n]s", str);
    getchar(); //读走scanf遗留下的'\n'（惯常操作）
    Tree *tree = build_tree(str);
    preorder(tree);
    inorder(tree);
    postorder(tree);
    clear_tree(tree);
    return 0;
}

Node *getNewNode(char data) {
    Node *node = (Node *)malloc(sizeof(Node));
    node->data = data;
    node->lchild = node->rchild = NULL;
    return node;
}

Tree *getNewTree() {
    Tree *tree = (Tree *)malloc(sizeof(Tree));
    tree->root = NULL;
    tree->length = 0;
    return tree;
}

void clear_node(Node *node) {
    if (node == NULL) return;
    clear_node(node->lchild);
    clear_node(node->rchild);
    free(node);
    return;
}

void clear_tree(Tree *tree) {
    if (tree == NULL) return;
    clear_node(tree->root);
    free(tree);
    return;
}

//结构操作：广义表转二叉树之递归
char *build_recur(char *str, Node *last_node, Tree *tree) {
    Node *node = NULL;
    int flag = 0;
    while (str[0]) {
        switch (str[0]) {
            case '(':
                str = build_recur(++str, node, tree);
                flag = 0;
                break;
            case ')':
                return str;
            case ',':
                flag = 1;
                break;
            case ' ':
                break;
            default:
                node = getNewNode(str[0]);
                if (last_node == NULL) {
                    tree->root = node;
                } else if (flag == 0) {
                    last_node->lchild = node;
                } else {
                    last_node->rchild = node;
                }
                tree->length += 1;
                break;
        }
        str++;
    }
    return str;
}

//结构操作：广义表转二叉树
Tree *build_tree(char *str) {
    Tree *tree = getNewTree();
    build_recur(str, tree->root, tree);
    return tree;
}

//结构操作：前序遍历的递归操作
void preorder_node(Node *node) {
    if (node == NULL) return;
    printf("%c ", node->data);
    preorder_node(node->lchild);
    preorder_node(node->rchild);
    return;
}

//结构操作：用前序遍历的方式输出所有元素
void preorder(Tree *tree) {
    if (tree == NULL) return;
    printf("preorder: ");
    preorder_node(tree->root);
    printf("\n");
    return;
}

//结构操作：中序遍历的递归操作
void inorder_node(Node *node) {
    if (node == NULL) return;
    inorder_node(node->lchild);
    printf("%c ", node->data);
    inorder_node(node->rchild);
    return;
}

//结构操作：用中序遍历的方式输出所有元素
void inorder(Tree *tree) {
    if (tree == NULL) return;
    printf("inorder: ");
    inorder_node(tree->root);
    printf("\n");
    return;
}

//结构操作：后序遍历的递归操作
void postorder_node(Node *node) {
    if (node == NULL) return;
    postorder_node(node->lchild);
    postorder_node(node->rchild);
    printf("%c ", node->data);
    return;
}

//结构操作：用后序遍历的方式输出所有元素
void postorder(Tree *tree) {
    if (tree == NULL) return;
    printf("postorder: ");
    postorder_node(tree->root);
    printf("\n");
    return;
}

总结：

  1. 栈操作之压栈 = 调用函数
  2. 栈操作之出栈 = 函数返回
  3. 栈操作之访问栈顶元素 = 将栈顶元素作为参数传入下一层函数

标签：node,Node,return,表转,Tree,tree,二叉树,广义,stack
From： https://www.cnblogs.com/Kelvin-Wu/p/16795302.html

相关文章

  • 数据结构：二叉树
    定义特点每个节点最多有两棵子树，所以二叉树中不存在度大于2的节点。左子树和右子树是有区别的，次序不能颠倒。即使某个节点只有1个子节点，也是有左右之分的。特殊的......
  • 114. 二叉树展开为链表
    题目描述给你二叉树的根结点root，请你将它展开为一个单链表：展开后的单链表应该同样使用TreeNode，其中right子指针指向链表中下一个结点，而左子指针始终为null。展......
  • 二叉树（存储结构，三种遍历方式，构建树）——C语言描述
    二叉树（存储结构，三种遍历方式，构建树）——C语言描述目录二叉树（存储结构，三种遍历方式，构建树）——C语言描述0测试用例框架1定义2特殊二叉树3二叉树的性质4二叉树存储结构5......
  • 226. 翻转二叉树
    题目描述解题思路二叉树的题一般都有对应的模板，我们做题时可以参考对应模板二叉树解题的思维模式分两类：1、是否可以通过遍历一遍二叉树得到答案？如果可以，用一个trav......
  • 617. 合并二叉树
    /***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(......
  • 124.二叉树的最大路径和
    路径被定义为一条从树中任意节点出发，沿父节点-子节点连接，达到任意节点的序列。同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点，且不一定经过根节点......
  • 图的广度优先搜索和二叉树的层序遍历其实差不多
    图的广度优先搜索和二叉树的层序遍历其实差不多，不同的是在图中没有根节点，你可以随便选择一个节点，当作起始节点，和二叉树的一样入队，访问，出队，判断顶点是否有邻接顶点，如果有邻......
  • 94. 二叉树的中序遍历 (easy)
     递归：左根右 /***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nul......
  • 计算二叉树的最大宽度
    求非空二叉树的宽度算法思想：层序遍历二叉树，并用两个队列A,B交替存储结点，当队列A中元素为空时队列B就存储了下一层的所有结点，同理，队列B为空时队列A也就存储了下一层的所有......
  • 代码随想录 | 进阶二叉树
    二叉树的构造默认如下：/***Definitionforabinarytreenode.*publicclassTreeNode{*intval;*TreeNodeleft;*TreeNoderight;*......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99