C#与数据结构--二叉树的遍历

二叉树的存储结构

二叉树的存储可分为两种:顺序存储结构和链式存储结构。

1.顺序存储结构

把一个满二叉树自上而下、从左到右顺序编号,依次存放在数组内,可得到图6.8(a)所示的结果。设满二叉树结点在数组中的索引号为i,那么有如下性质。

(1)如果i = 0,此结点为根结点,无双亲。

(2)如果i > 0,则其双亲结点为(i -1) / 2 。(注意,这里的除法是整除,结果中的小数部分会被舍弃。)

(3)结点i的左孩子为2i + 1,右孩子为2i + 2。

(4)如果i > 0,当i为奇数时,它是双亲结点的左孩子,它的兄弟为i + 1;当i为偶数时,它是双新结点的右孩子,它的兄弟结点为i – 1。

(5)深度为k的满二叉树需要长度为2 k-1的数组进行存储。

通过以上性质可知,使用数组存放满二叉树的各结点非常方便,可以根据一个结点的索引号很容易地推算出它的双亲、孩子、兄弟等结点的编号,从而对这些结点进行访问,这是一种存储二叉满二叉树或完全二叉树的最简单、最省空间的做法。

为了用结点在数组中的位置反映出结点之间的逻辑关系,存储一般二叉树时,只需要将数组中空结点所对应的位置设为空即可,其效果如图6.8(b)所示。这会造成一定的空间浪费,但如果空结点的数量不是很多,这些浪费可以忽略。

一个深度为k的二叉树需要2 k-1个存储空间,当k值很大并且二叉树的空结点很多时,最坏的情况是每层只有一个结点,再使用顺序存储结构来存储显然会造成极大地浪费,这时就应该使用链式存储结构来存储二叉树中的数据。


1.链式存储结构

二叉树的链式存储结构可分为二叉链表和三叉链表。二叉链表中,每个结点除了存储本身的数据外,还应该设置两个指针域left和right,它们分别指向左孩子和右孩子(如图6.9(a)所示)。

当需要在二叉树中经常寻找某结点的双亲,每个结点还可以加一个指向双亲的指针域parent,如图6.9(b)所示,这就是三叉链表。


图6.10所示的是二叉链表和三叉链表的存储结构,其中虚线箭头表示parent指针所指方向。


二叉树还有一种叫双亲链表的存储结构,它只存储结点的双亲信息而不存储孩子信息,由于二叉树是一种有序树,一个结点的两个孩子有左右之分,因此结点中除了存放双新信息外,还必须指明这个结点是左孩子还是右孩子。由于结点不存放孩子信息,无法通过头指针出发遍历所有结点,因此需要借助数组来存放结点信息。图6.10(a)所示的二叉树使用双亲链表进行存储将得到图6.11所示的结果。由于根节点没有双新,所以它的parent指针的值设为-1。


双亲链表中元素存放的顺序是根据结点的添加顺序来决定的,也就是说把各个元素的存放位置进行调换不会影响结点的逻辑结构。由图6.11可知,双亲链表在物理上是一种顺序存储结构。

二叉树存在多种存储结构,选用何种方法进行存储主要依赖于对二叉树进行什么操作来确定。而二叉链表是二叉树最常用的存储结构,下面几节给出的有关二叉树的算法大多基于二叉链表存储结构。

时间: 2024-10-28 12:00:57

C#与数据结构--二叉树的遍历的相关文章

举例讲解C语言程序中对二叉树数据结构的各种遍历方式_C 语言

二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF  2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后

UVa 11234 Expressions:二叉树 层次遍历 广搜

题目链接: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=103&page=show_problem&problem=2175 题目类型: 数据结构, 二叉树 题目大意: 一般情况下,都是中缀操作符, 如x+y.然后题目给出了一种后缀操作符的形式, 变成 x y +. 进行后缀操作可以用栈模拟,使用push,pop, 过程和经典的"括号匹配"差不

[算法系列之二]二叉树各种遍历

[简介] 树形结构是一类重要的非线性数据结构,其中以树和二叉树最为常用. 二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作"左子树"(left subtree)和"右子树"(right subtree).二叉树常被用作二叉查找树和二叉堆或是二叉排序树.二叉树的每个结点至多只有二棵子树(不存在度大于2的结点),二叉树的子树有左右之分,次序不能颠倒.二叉树的第i层至多有2的 i -1次方个结点:深度为k的二叉树至多有2^(k) -1个结点:对任何一棵二叉树T,

算法-求助,数据结构二叉树问题

问题描述 求助,数据结构二叉树问题 试编写算法,求给定二叉树上从根结点到叶子结点的一条其路径长度等于树的深度减一的路径(即列出从根结点到该叶子结点的结点序列),若这样的路径存在多条,则输出路径终点(叶子结点)在"最左"的一条. 解决方案 ?? #define null 0???#include "stdio.h"???typedef char datatype;?? typedef struct tn? {datatype data;?? struct tn lc,

java 数据结构二叉树的实现代码_java

1. 二叉树接口 public interface BinaryTreeInterface<T> { public T getRootData(); public int getHeight(); public int getNumberOfRoot(); public void clear(); public void setTree(T rootData); // 用rootData设置树 public void setTree(T rootData,BinaryTreeInterface

一步一步写算法(之二叉树深度遍历)

原文:一步一步写算法(之二叉树深度遍历) [ 声明:版权所有,欢迎转载,请勿用于商业用途.  联系信箱:feixiaoxing @163.com]     深度遍历是软件开发中经常遇到的遍历方法.常用的遍历方法主要有下面三种:(1)前序遍历:(2)中序遍历:(3)后序遍历.按照递归的方法,这三种遍历的方法其实都不困难,前序遍历就是根-左-右,中序遍历就是左-根-右,后续遍历就是左-右-根.代码实现起来也不复杂.     1)前序遍历 void preorder_traverse(TREE_NOD

c语言-求助关于二叉树层次遍历

问题描述 求助关于二叉树层次遍历 向各位前辈求助..... 小弟研究二叉树层次遍历三天了,始终不能结合队列写出可执行的代码....真心求教....万分感谢.....!!!! void Printbylevel(BTree T) { BNode *tmp = T; CircleQueue *q = malloc(sizeof(CircleQueue)); Init(q); if(T == NULL) { return ;//根节点为空,返回-1 } else { InQueue(q, tmp);/

数据结构——二叉树

1 基本定义 ①二叉树是n(n>=0)个结点的有限集,当n=0时,二叉树为空.当n>0时,二叉树是由一个根节点及至多两颗子树组成,且左右子树都是二叉树.    不同于树,二叉树中的结点要区分左子树和右子树,即使只有一颗子树,左单子树不同于右单子树. ②树的一些基本术语: 结点:包含了数据元素及若干个指向其子树的分支. 结点的度:结点的子树数目或分支个数. 树的度:在树中取各结点的度的最大值. 结点的路径:从根结点到该结点所经分支和结点构成的结点的路径. 结点的层次:设根结点的层次为1,则其子树

数据结构二叉树问题求助

问题描述 数据结构二叉树问题求助 设只含根结点的二叉树的高度为0,则高度为k的二叉树的最大结点数为(),最小结点数为() 答案是(2^k+1)-1和k+1.我做出来的是(2^k)-1和k 求帮忙算一下哪个是对的,谢谢了 解决方案 带入法计算就可以了.跟节点高度为0,比如高度为1,最大就有3个,最小两个.一看你的答案就错了. 解决方案二: ?? #define null 0???#include "stdio.h" ???typedef char datatype;?? typedef