首页 > 其他分享 >7-8 数据结构实验二 二叉树的遍历

7-8 数据结构实验二 二叉树的遍历

时间:2024-11-08 23:43:54浏览次数:6  
标签:lchild 遍历 BiTree NULL 二叉树 printf rchild 数据结构 root

以二叉链表作存储结构,建立一棵二叉树。 输出该二叉树的先序、中序、后序遍历序列,求出该二叉树的深度,并统计其叶子结点数。

二叉链表的类型描述:

typedef char ElemType;
typedef  struct  BiNode
{  ElemType  data;
    struct  BiNode   *lchild,*rchild;
}BiNode,*BiTree;  

输入格式:

输入一个二叉树的先序序列,孩子为空的位置以#替代。

输出格式:

输出分五行

  • 第一行 先序遍历序列
  • 第二行 中序遍历序列
  • 第三行 后序遍历序列
  • 第四行 二叉树深度
  • 第五行 叶子结点数

其中遍历过程中按访问顺序打印出结点的内容时,字符间均无间隔。
具体格式参看输出样例。

对于下图中给出的二叉树:

二叉树

输入样例:

ABD##FE###CG#H##I##

输出样例:

PreOrder:ABDFECGHI
InOrder:DBEFAGHCI
PostOrder:DEFBHGICA
Depth:4
Leaf:4

代码长度限制

16 KB

时间限制

400 ms

内存限制

64 MB

栈限制

8192 KB

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

typedef char ElemType;
typedef struct BiNode
{
   ElemType data;
   struct BiNode *lchild, *rchild;
} BiNode, *BiTree;

BiTree createNode(ElemType data)
{
   BiTree node = (BiTree)malloc(sizeof(BiNode));
   node->data = data;
   node->lchild = NULL;
   node->rchild = NULL;
   return node;
}

BiTree buildTree(char **str)
{
   if (**str == '#')
   {
      (*str)++;
      return NULL;
   }
   BiTree root = createNode(**str);
   (*str)++;
   root->lchild = buildTree(str);
   root->rchild = buildTree(str);
   return root;
}

void preOrder(BiTree root)
{
   if (root != NULL)
   {
      printf("%c", root->data);
      preOrder(root->lchild);
      preOrder(root->rchild);
   }
}

void inOrder(BiTree root)
{
   if (root != NULL)
   {
      inOrder(root->lchild);
      printf("%c", root->data);
      inOrder(root->rchild);
   }
}

void postOrder(BiTree root)
{
   if (root != NULL)
   {
      postOrder(root->lchild);
      postOrder(root->rchild);
      printf("%c", root->data);
   }
}

int depth(BiTree root)
{
   if (root == NULL)
      return 0;
   int leftDepth = depth(root->lchild);
   int rightDepth = depth(root->rchild);
   return (leftDepth > rightDepth ? leftDepth : rightDepth) + 1;
}

int countLeafNodes(BiTree root)
{
   if (root == NULL)
      return 0;
   if (root->lchild == NULL && root->rchild == NULL)
      return 1;
   return countLeafNodes(root->lchild) + countLeafNodes(root->rchild);
}

int main()
{
   char input[100];
   scanf("%s", input);
   char *p = input;
   BiTree root = buildTree(&p);

   printf("PreOrder:");
   preOrder(root);
   printf("\n");

   printf("InOrder:");
   inOrder(root);
   printf("\n");

   printf("PostOrder:");
   postOrder(root);
   printf("\n");

   printf("Depth:%d\n", depth(root));
   printf("Leaf:%d\n", countLeafNodes(root));

   return 0;
}

标签:lchild,遍历,BiTree,NULL,二叉树,printf,rchild,数据结构,root
From: https://blog.csdn.net/2401_85947543/article/details/143615554

相关文章

  • 数据结构实验(串的实现)
    实验串的实现一、实验目的1.掌握串的基本概念;2.理解串的几种存储表示及其特点;3.掌握串的常用操作的实现。二、实验环境硬件:计算机一台;软件:VisualStudio。三、实验内容串分别采用顺序存储方式的前提下,完成如下两个任务:1.串比较操作:编写一个比较串s和串t两个串是否相......
  • JS数据结构之树和二叉树
    一、树树(Tree)是一种非常常见的数据结构,它模拟了自然界中树的结构,由节点(或称为顶点)组成,并且具有层次化的组织形式。树结构在计算机科学中广泛应用,例如在组织数据、管理信息层次以及算法设计中。1.基本概念节点(Node)根节点(Root):树的最顶端节点,没有父节点。内部节点(InternalNod......
  • OSSFileBrowse:OSS存储桶遍历漏洞利用工具
    简介:由于经常遇到存储桶遍历漏洞,直接访问文件是下载,不方便预览,且甲方要求证明该存储桶的危害,因此该工具应运而生。使用javafx做图形化,kkFileView做文件预览接口。使用:命令行运行:java-Dfile.encoding=UTF-8-jarOSSFileBrowse-1.0-SNAPSHOT.jar或者直接点击run.bat文件。......
  • Leecode热题100-104.二叉树中的最大路径和
    二叉树中的 路径 被定义为一条节点序列,序列中每对相邻节点之间都存在一条边。同一个节点在一条路径序列中 至多出现一次 。该路径 至少包含一个 节点,且不一定经过根节点。路径和 是路径中各节点值的总和。给你一个二叉树的根节点 root ,返回其 最大路径和 。示例......
  • 代码随想录算法训练营第十五天| 110.平衡二叉树,257. 二叉树的所有路径, 404.左叶子之
    110.平衡二叉树文章链接:https://programmercarl.com/0110.平衡二叉树.html#题外话题目链接:https://leetcode.cn/problems/balanced-binary-tree/description/classSolution{public://每次都要比较左右子树的高度差是否在1以内,所以递归是要统计子树的高度的intg......
  • 二叉树遍历
    二叉树遍历这个问题,以前一直没搞懂,只是模糊的了解。先序遍历:先访问根节点,再从左到右依次访问各子树。ABDECFG中序遍历:先访问左节点,再访问根节点,最后再访问右节点。DBEACGF后序遍历:先从左到右遍历各棵子树,再访问根节点。DEBGFCA先中后实际上对应的是根遍历的位置。层次遍历......
  • 二叉树 (王道数据结构 C语言版)
    2004.11.04计算一颗给定二叉树的所有双分支节点个数编写把一个树的所有左右子树进行交换的函数求先序遍历中第k个结点的值(1<=k<=二叉树中的结点个数)#include<bits/stdc++.h>#defineintlonglong#defineendl'\n'usingnamespacestd;typedefstructBitnode{......
  • 数据结构 --树
    定义树是n(n>=0)个结点的有限集。n=0时,称为空树。在任意一棵树非空树中应满足:(1)有且仅有一个特定的称为根(root)的结点(2)当时,其余结点可分为个互不相交的有限集,其中每一个集合本身又是一颗树,并且称为根的子树。基本概念结点的度:一个结点拥有的子树的数目叶子结点:度为0......
  • 二叉树的递归遍历和迭代遍历
    递归每次写递归,都按照这三要素来写,可以保证大家写出正确的递归算法!确定递归函数的参数和返回值:确定哪些参数是递归的过程中需要处理的,那么就在递归函数里加上这个参数,并且还要明确每次递归的返回值是什么进而确定递归函数的返回类型。确定终止条件:写完了递归算法,运行的时......
  • 数据结构学习笔记---线性表:顺序表(插入)
    顺序表的基本操作——插入首先,静态分配一个顺序表#include<stdio.h>#include<stdlib.h>#defineMaxSize5//定义队列的最大长度typedefstruct{ intdata[MaxSize]; intlength;}SqList;然后实现插入方法,for循环我们提前插入了四个元素,顺序排放原理是以i为......