【二叉树->链表】二叉树结构转双向线性链表结构(先序遍历)

时间:2022-09-28 09:37:40

二叉树存储结构属于非线性链表结构,转化成线性链表结构,能简化操作和理解。然而由非线性转线性需要对整个树遍历一次,不同的遍历方式转化结果页不一样。下面以先序为例。

方法一:

递归法。递归遍历二叉树,因为是双向链表,需要记录当前遍历元素的上一个元素。

方法二:

使用栈。先将遍历元素入栈,遍历完成后,出栈并连接成链表。

struct tree_node;
struct tree_node{
struct tree_node *lc;
struct tree_node *rc;
char data;
};
typedef struct tree_node treenode; void pre_create_tree(treenode **T){ //递归法
char datatemp; fflush(stdin);
datatemp=getchar(); if(datatemp=='*'){
*T=NULL;
}
else{
if((*T=(treenode*)malloc(sizeof(treenode)))==NULL){
exit(0);
}
else{
(*T)->data=datatemp;
(*T)->lc = (*T)->rc = NULL;
pre_create_tree(&(*T)->lc);
pre_create_tree(&(*T)->rc);
}
}
} struct mytlist{
struct mytlist* front;
struct mytlist* next;
char data;
};
typedef struct mytlist tlist;
static tlist *cur_front=NULL;
static tlist **cur_next;
void pre_tree2list(treenode *tree, tlist** tlist_head){ //传递函数参数tlist_front必须传入NULL
tlist* tlist_temp=NULL;
if(tree==NULL){
*tlist_head = NULL;
return;
}
if((tlist_temp=(tlist*)malloc(sizeof(tlist)))==NULL){
printf("malloc failed\n");
exit(0);
}
else{
tlist_temp->front = cur_front;
*tlist_head = tlist_temp;
tlist_temp->data = tree->data;
cur_front = *tlist_head;
cur_next = &(*tlist_head)->next;
pre_tree2list(tree->lc, cur_next);
pre_tree2list(tree->rc, cur_next);
}
} void visit_tlist(tlist* tlist_head){
while(tlist_head){
printf("%c ", tlist_head->data);
tlist_head = tlist_head->next;
}
} int main(void)
{
treenode *mytree=NULL;
tlist *mytlist=NULL; pre_create_tree(&mytree);
pre_tree2list(mytree, &mytlist);
visit_tlist(mytlist); printf("\n"); system("pause");
return 0;
}

测试样例:

/*先序为DLR(D:根节点,L:左子树,R:右子树)

  a

  / \

 b   c

 / \   / \

d * * e

*/

//先序序列为abdce,输入为abd***c*e**(*表示空格,代表空树)

对于一般树的情况,使用孩子兄弟表示法,将一般树表示成二叉树(结点存储结构为:指向本结点第一个孩子的指针,数值,指向同层下一个兄弟的指针),再由这个二叉树即可转换为线性链表结构。

对于森林的情况,将森林的每一棵树的根结点视为兄弟,再次使用孩子兄弟表示法转换成一般树结构。

【二叉树->链表】二叉树结构转双向线性链表结构(先序遍历)的更多相关文章

  1. python算法:LinkedList(双向线性链表)的实现

    LinkedList是一个双向线性链表,但是并不会按线性的顺序存储数据,而是在每一个节点里存到下一个节点的指针(Pointer).由于不必须按顺序存储,链表在插入的时候可以达到O(1)的复杂度,比另一 ...

  2. 【C++】双向线性链表容器的实现

    // 双向线性链表容器 #include <cstring> #include <iostream> #include <stdexcept> using name ...

  3. &lbrack;二叉树建树&rsqb;1119&period; Pre- and Post-order Traversals &lpar;30&rpar; &lpar;前序和后序遍历建立二叉树&rpar;

    1119. Pre- and Post-order Traversals (30) Suppose that all the keys in a binary tree are distinct po ...

  4. Java构造二叉树、树形结构先序遍历、中序遍历、后序遍历

    package com.example.demo; public class BTree { public int data; public BTree left; public BTree rigt ...

  5. C&plus;&plus;编程练习&lpar;8&rpar;----&OpenCurlyDoubleQuote;二叉树的建立以及二叉树的三种遍历方式&OpenCurlyDoubleQuote;(前序遍历、中序遍历、后续遍历)

    树 利用顺序存储和链式存储的特点,可以实现树的存储结构的表示,具体表示法有很多种. 1)双亲表示法:在每个结点中,附设一个指示器指示其双亲结点在数组中的位置. 2)孩子表示法:把每个结点的孩子排列起来 ...

  6. 二叉树 Java 实现 前序遍历 中序遍历 后序遍历 层级遍历 获取叶节点 宽度 ,高度,队列实现二叉树遍历 求二叉树的最大距离

    数据结构中一直对二叉树不是很了解,今天趁着这个时间整理一下 许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及其算法都较为简单,因此二叉树显 ...

  7. 前、中、后序遍历随意两种是否能确定一个二叉树?理由? &amp&semi;&amp&semi; 栈和队列的特点和区别

    前序和后序不能确定二叉树理由:前序和后序在本质上都是将父节点与子结点进行分离,但并没有指明左子树和右子树的能力,因此得到这两个序列只能明确父子关系,而不能确定一个二叉树. 由二叉树的中序和前序遍历序列 ...

  8. 【LeetCode】145&period; 二叉树的后序遍历

    145. 二叉树的后序遍历 知识点:二叉树:递归:Morris遍历 题目描述 给定一个二叉树的根节点 root ,返回它的 后序 遍历. 示例 输入: [1,null,2,3] 1 \ 2 / 3 输 ...

  9. &lpar;原&rpar;neuq oj 1022给定二叉树的前序遍历和后序遍历确定二叉树的个数

    题目描述 众所周知,遍历一棵二叉树就是按某条搜索路径巡访其中每个结点,使得每个结点均被访问一次,而且仅被访问一次.最常使用的有三种遍历的方式: 1.前序遍历:若二叉树为空,则空操作:否则先访问根结点, ...

随机推荐

  1. Sublime Text的常用插件

    工欲善其事,必先利其器.好的插件会更多的帮助我们装逼. 最新感悟:也不要装太多的插件.有些无用的插件可以删除,有时反而臃肿.bloger下载官方最新稳定版st3 3126下载下来25M左右.安装十来个 ...

  2. C和CPP关于条件运算符的区别

    条件运算符形式: cond ? expr1 : expr2; 在C语言中执行过程是: 先对cond求值,值为真返回expr1的值,否则返回expr2的值.(右值) gcc测试结果: 在Cpp中如果两个 ...

  3. iOS-XMPP客户端

    首先我们自己做一个的IOS客户端程序 先看一下我们完成的效果图 首先下载xmppframework这个框架 点ZIP下载 接下来,用Xcode新建一个工程 将以下这些文件拖入新建工程中 加入frame ...

  4. ABBYY FineReader 12扫描界面介绍

    ABBYY FineReader 12OCR图文识别软件自身拥有着自己的扫描界面,一般在默认情况下,ABBYY FineReader 使用其自身的扫描界面.本文就解析了ABBYY FineReader ...

  5. ViewPage显示Fragment集合实现左右滑动并且出现tab栏--第三方开源--SlidingTabLayout和SlidingTabStrip实现

    注意:有关Fragment的方法和ViewPager的全部是android.support.v4包的,否则会报很多的错误 MainActivity: package com.zzw.fragmentt ...

  6. LeetCode&lowbar;Maximal Rectangle

    Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and ...

  7. web离线应用--applicationCache

    applicationCache是html5新增的一个离线应用功能 离线浏览: 用户可以在离线状态下浏览网站内容. 更快的速度: 因为数据被存储在本地,所以速度会更快. 减轻服务器的负载: 浏览器只会 ...

  8. vsto下开发wps插件

    我们要开发wps插件了.之前用vsto开发过word插件,我也讲过c#下如何开发wps插件(有点繁琐).如果采用c#从头再开发wps插件,那么开发出来的office加载项就会出现两个.我们要实现的wp ...

  9. Jquery Mobile 让错误提示可在后台控制显示内容

    在jquery.mobile-1.4.5.min.js的5254行找到下面代码 return $.proxy(function( xhr, textStatus, errorThrown ) { 然后 ...

  10. UVALive - 7041 The Problem to Slow Down You (回文树)

    https://vjudge.net/problem/UVALive-7041 题意 给出两个仅包含小写字符的字符串 A 和 B : 求:对于 A 中的每个回文子串,B 中和该子串相同的子串个数的总和 ...