专栏首页趣学算法数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

数据结构 第13讲 三元组 (F、C、L/R) 序列创建二叉树

/* 输入三元组 (F、C、L/R) 序列输入一棵二叉树的诸边(其中 F 表示双亲结点的标识,C 表示孩子结点标识,L/R 表示 C 为 F 的左孩子或右孩子), 且在输入的三元组序列中,C 是按层次顺序出现的。 设结点的标识是字符类型。F=NULL时 C 为根结点标识,若 C 亦为NULL,则表示输入结束。 试编写算法,由输入的三元组序列建立二叉树的二叉链表,并以先序、中序、后序序列输出。 */ /*测试数据 NULL A L A B L A C R B D R C E L C F R D G L F H L NULL NULL L

*/

解题思路:

1、首先创建二叉树结构体结点。

2、输入第一个数据,创建根结点入队。因为按层次输入的,因此要使用队列。

3、输入数据,队头元素出队,判断队头元素是否和输入数据中的父亲相等,如果相等,判断创建左孩子还是右孩子。创建后,孩子入队。再次输入数据,队头元素是否和输入数据中的父亲相等,如果相等,判断创建左孩子还是右孩子。创建后,孩子入队。(因为一个队头元素,可能有两个孩子,因此不能创建一个孩子就结束。)

4、循环,直到队列为空或者a,b为空停止,创建树成功。

5、输出先序、中序、后序序列。

#include <iostream>
 #include<cstring>
 #include<queue>
 using namespace std;
 struct biTnode
 {
     string data;
     biTnode *lChild,*rChild;
 };
  biTnode* T=NULL;
 void CreatebiTree(biTnode* &T)
 {
     string a,b,c;
     biTnode *node,*p;
     queue<biTnode*>q;
     cin>>a>>b>>c;
     if(a=="NULL" && b!="NULL")//创建根结点
     {
         node=new biTnode;
         node->data=b;
         node->lChild=node->rChild=NULL;
         T=node;
         q.push(T);
     }
     cin>>a>>b>>c;
     while(!q.empty()&&a!="NULL"&&b!="NULL")
     {
         p=q.front();
         q.pop();
         while(a==p->data)
         {
             node=new biTnode;
             node->data=b;
             node->lChild=node->rChild=NULL;
             if(c=="L")
             {
                 p->lChild=node;
                 cout<<p->data<<"'s lChild is "<<node->data<<endl;
             }
             else
             {
                 p->rChild=node;
                 cout<<p->data<<"'s rChild is "<<node->data<<endl;
             }
             q.push(node);
             cin>>a>>b>>c;
         }
     }
 }




 void preorder(biTnode* &T)
 {
     if(T)
     {
        cout<<T->data<<"  ";
        preorder(T->lChild);
        preorder(T->rChild);
     }
 }


 void inorder(biTnode* &T)
 {
     if(T)
     {
        inorder(T->lChild);
        cout<<T->data<<"  ";
        inorder(T->rChild);
     }
 }


 void posorder(biTnode* &T)
 {
     if(T)
     {
        posorder(T->lChild);
        posorder(T->rChild);
        cout<<T->data<<"  ";
     }
 }
 int main()
 {
     cout << "输入结点数据a,b,c(a为父亲,b为结点字符,c为‘L’左孩子或‘R’右孩子)" << endl;
     CreatebiTree(T);
     cout << "创建树成功!" << endl;
     cout << "先序遍历:" << endl;
     preorder(T);
     cout<<endl<< "中序遍历:" << endl;
     inorder(T);
     cout<<endl<< "后序遍历:" << endl;
     posorder(T);
     return 0;
 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 数据结构 第9讲 数组与广义表

    LOC(a00)表示第一个元素的存储位置,即基地址,LOC(aij)表示aij的存储位置。 授人以鱼不如授人以渔,告诉你记住公式,就像送你一条鱼,不如交给你捕...

    rainchxy
  • 数据结构 第15讲 一场说走就走的旅行——最短路径

    本内容来源于《趣学算法》,在线章节:http://www.epubit.com.cn/book/details/4825

    rainchxy
  • 数据结构 第3讲 顺序表

    顺序表是最简单的一种线性结构,逻辑上相邻的数据在计算机内的存储位置也是相邻的,可以快速定位第几个元素,中间不允许有空,所以插入、删除时需要移动大量元素。

    rainchxy
  • 就叫Spyfari吧!|数据爬取及可视化系列

    这是《数据爬取及可视化系列》的第四篇文章。 前3篇文章,可以查阅: 01基于位置的用户画像初探 02技能之谷歌Chrome爬虫 03 使用Echarts制作可视...

    mixlab
  • 实战干货:从零快速搭建自己的爬虫系统

    本文简要归纳了网页爬虫的基础知识,着重于利用现有组件,快速建立一套实际可用的网页爬取、分析系统。系统主要使用Python 作为开发语言,在 Linux 或 Ma...

    胖兔子兔胖
  • 抽象类与抽象方法

    在我们抽象实例对象的时候,有这样一种情况,往上层抽象时就会发现很难描述对象的属性和行为,比如“形状” ,其方法计算面积怎么计算?正方形知道怎么计算,长方形也知道...

    sr
  • 单链表实现LRU缓存淘汰算法

    LRU(Least recently used,最近最少使用)算法根据数据的历史访问记录来进行淘汰数据,其核心思想是如果数据最近被访问过,那么将来被访问的几率也...

    汐楓
  • 【CV中的特征金字塔】一,工程价值极大的ASFF

    今天为大家介绍一下2019年的一篇论文 《Learning Spatial Fusion for Single-Shot Object Detection》,这...

    BBuf
  • SQL学习笔记七之MySQL视图、触发器、事务、存储过程、函数

    视图是一个虚拟表(非真实存在),其本质是【根据SQL语句获取动态的数据集,并为其命名】,用户使用时只需使用【名称】即可获取结果集,可以将该结果集当做表来使用。

    Jetpropelledsnake21
  • 算法:快速排序(QuickSort)

    通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以...

    WEBJ2EE

扫码关注云+社区

领取腾讯云代金券