文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 论数据结构中二叉树的链式存储
侵权投诉

论数据结构中二叉树的链式存储

数据结构 二叉树

2010年8月

第16卷第3期安庆师范学院学报(自然科学版)JournalofAnqingTeachersCollege(NaturalScienceEdition)Aug.2010Vol.16No.3

论数据结构中二叉树的链式存储

刘 影

(安徽电子信息职业技术学院软件学院,安徽蚌埠233000)

摘 要:二叉树是树型结构中的重点研究对象。二叉树的操作是以二叉树的存储为基础,其存储主要包括顺序存

储和链式存储,常用的是链式存储。目前研究者对二叉树的链式存储缺少一个全面、系统的分析。因此本文对二叉树的

动态链式存储和静态链式存储进行了全面的介绍,并对其进行了分析研究。

关键词:二叉树;动态链式存储;静态链式存储

中图分类号:TP311.12 文献标识码:A 文章编号:1007-4260(2010)03-0053-04

0 引 言

在计算机领域中,树型结构是一类非常重要的非线性结构,其中二叉树最为常用,对二叉树的操作和存储比树相对简单。二叉树的存储一般采用顺序存储和链式存储。顺序存储是将一棵二叉树的结点存放于一组地址连续的存储单元中,这种存储结构对完全二叉树而言,既简单又节省存储空间。但对于一般二叉树,尤其对于单支结点较多的二叉树很不适合,由于对其存储也必须按完全二叉树的形式存储二叉树中的结点,从而造成存储空间的浪费。因此,二叉树一般采用链式存储结构。二叉树的链式存储结构分为两种,一种是动态链式存储,另一种是静态链式存储。二叉树的动态链式存储是采用链表的形式存储二叉树,一般采用二叉链表和三叉链表。二叉树的静态存储是用一个数组存储二叉树的各个结点,数组中不仅保存每个结点的信息,还存储该结点左、右孩子在数组中的地址信息。下面分别对二叉树的动态链式存储和静态链式存储进行分析研究。

1 二叉树的动态链式存储

二叉树的动态链式存储有两种形式,一是二叉链表,即链表中每个结点由三个域组成:数据域、左孩子指针和右孩子指针。二为三叉链表,即在二叉链表的基础上,增加了一个指向双亲结点的指针。

1.1 二叉链表存储

二叉链表的结点类型定义如下,结点结构如图1所示。图2为一棵一般的二叉树,图3为图2采用二叉链表存储的结构示意图。

typedefstructnode

{

datatypedata;

structnode*lchild,*rchild;

}BiTNodeT

论数据结构中二叉树的链式存储

;

datatype为结点的数据类型,本文中均采用字符型。具体使用时需在程序中将datatype替换为char,或者在程序头部添加语句/#definedatatypechar0(本文定义与算法均采用C语言编写)。

利用二叉链表建立二叉树的一种算法如下:图1 二叉链表结点的存储结构

*收稿日期:2009-12-06,,,,网络安全研究。

第1页

热门文档

相关文档

  • 数据结构C语言版 二叉树的顺序存储表示和实现

    数据结构C语言版 二叉树的顺序存储表示和实现_经管营销_专业资料。数据结构C语言版 二叉树的顺序存储表示和实现/* 数据结构 C 语言版 二叉树的顺序存储表示和...

  • 数据结构-二叉树的存储结构和遍历

    二叉树的顺序存储顺序存储是用一组连续的存储单元存放数据 顺序存储要求数据是线性结构 二叉树是非线性结构 如何把二叉树转换为线性结构,而且保持 结点之间的父/子...

  • 建立二叉树,并对树进行操作数据结构课程设

    二叉树的建立链式存储结构,前序遍历,求叶 子结点的个数计算,中序遍历,后序遍历,深度求解。 1)二叉树的建立:定义二叉树的链式存储结构,输入数据生成二叉树。 ...

  • 数据结构树和二叉树

    数据结构树和二叉树_电脑基础知识_IT/计算机_专业...论 在二叉链表中,查找结点都要从根结点开始 进行...针对不同的树结构和不同的算法,常用的链式存储结构...

  • 数据结构二叉树存储代码

    #include <stdio.h> #include <stdlib.h> /*二叉树的链式存储表示*/ typedef char DataType; /*应由用户定义DataType的实际类型*/ typedef struct node { ...

  • 数据结构 树和二叉树代码

    数据结构 树和二叉树代码_计算机软件及应用_IT/计算机_专业资料。树和二叉树...(3) 假设二叉树采用链式存储结构进行存储,编写一个算法,输出一个二叉树的 所有...

  • 数据结构二叉树练答案

    数据结构二叉树练答案_计算机软件及应用_IT/计算机_专业资料。树和二叉树 自测...(应 2i-1) (√)9.用二叉链表法(link-rlink)存储包含 n 个结点的二叉树,...

  • 数据结构 树 考试习题

    数据结构 树 考试习题_理学_高等教育_教育专区。数据结构考试内容...在二叉树的链式存储结构中,结点类型定义如下: typedef struct node { ElemType ...

  • 《数据结构(Java)》树和二叉树

    《数据结构(Java)》树和二叉树_文学研究_人文社科_专业资料。《数据结构》...二叉树的链式存储结构 二叉树的链式存储结构是用指针建立二叉树中结点之间的关系...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email