`

数据结构之——二叉树

阅读更多

最近开始重新温习一下大学数据结构的一些算法,也重新梳理一下自己的思路和想法。

先从二叉树开始。每周一期,希望能分享给大家,如有问题及时给予指正,谢谢大家。

 

二叉树的基本概念:

 

       二叉树是有限元素的集合,该集合或者为空,或者由一个称为根的元素及两个不想交,被分别称为左子树和右子树的二叉树组成。 二叉树是有序的,若将其左右子树颠倒,就成为另一颗不同的二叉树。

 

二叉树的相关概念

 

  • 结点的度:结点所拥有的子树的个数称为该结点的度。
  • 叶结点:度为0的结点称为叶结点,或者称为终端结点。
  • 分枝结点:度不为0的结点称为分支结点,或者称为非终端结点。一棵树的结点除叶结点外,其余的都是分支结点。
  • 左孩子、右孩子、双亲:树中一个结点的子树的根结点称为这个结点的孩子。这个结点称为它孩子结点的双亲。具有同一个双亲的孩子结点互称为兄弟。
  • 路径、路径长度。如果一棵树的一串结点n1,n2,…,nk有如下关系:结点ni是ni+1的父结点(1≤i<k),就把n1,n2,…,nk称为一条由n1至nk的路径。这条路径的长度是k-1。

  • 祖先、子孙:在树中,如果有一条路径从结点M到结点N,那么M就称为N的祖先,而N称为M的子孙。
  • 结点的层数:规定树的根结点的层数为1,其余结点的层数等于它的双亲结点的层数加1。
  • 树的深度:树中所有结点的最大层数称为树的深度。
  • 树的度:树中各结点度的最大值称为该树的度。
  • 满二叉树:在一棵二叉树中,如果所有分支结点都存在左子树和右子树,并且所有叶子结点都在同一层上,这样的一棵二叉树称作满二叉树。如图1.0所示,(a)图就是一棵满二叉树,(b)图则不是满二叉树,因为,虽然其所有结点要么是含有左右子树的分支结点,要么是叶子结点,但由于其叶子未在同一层上,故不是满二叉树。

                 
      (a) 一棵满二叉树                                               (b) 一棵非满二叉树

图1.0 满二叉树和非满二叉树示意图

 

  • 完全二叉树:一棵深度为k的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。完全二叉树的特点是:叶子结点只能出现在最下层和次下层,且最下层的叶子结点集中在树的左部。显然,一棵满二叉树必定是一棵完全二叉树,而完全二叉树未必是满二叉树。如图1.1所示(a)为一棵完全二叉树,(b)和图1.0(b)都不是完全二叉树。

                      

           (a) 一棵完全二叉树                                    (b) 一棵非完全二叉树

图1.1 完全二叉树和非完全二叉树示意图

 

二叉树的主要性质

 

  • 一棵非空二叉树的第i层上最多有2i-1个结点(i≥1)。
  • 一棵深度为k的二叉树中,最多具有2k-1个结点。
  • 对于一棵非空的二叉树,如果叶子结点数为n0,度数为2的结点数为n2,则有:n0=n2+1。
  • 具有n个结点的完全二叉树的深度k为[log2n]+1。
  • 对于具有n个结点的完全二叉树,如果按照从上至下和从左到右的顺序对二叉树中的所有结点从1开始顺序编号,则对于任意的序号为i的结点,有:

        (1)如果i>1,则序号为i的结点的双亲结点的序号为i/2(“/”表示整除);如果i=1,则序号为i的结点是根结点,无双亲结点。

        (2)如果2i≤n,则序号为i的结点的左孩子结点的序号为2i;如果2i>n,则序号为i的结点无左孩子。 

(3)如果2i+1≤n,则序号为i的结点的右孩子结点的序号为2i+1;如果2i+1>n,则序号为i的结点无右孩子。 此外,若对二叉树的根结点从0开始编号,则相应的i号结点的双亲结点的编号为(i-1)/2,左孩子的编号为2i+1,右孩子的编号为2i+2。

 

二叉树的存储

 

  • 顺序存储结构:所谓二叉树的顺序存储,就是用一组连续的存储单元存放二叉树中的结点。一般是按照二叉树结点从上至下、从左到右的顺序存储。

  • 链式存储结构:用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系。通常有下面两种形式。 1、二叉链表存储。2、三叉链表存储。

二叉树的遍历方法

 

  • A、先序遍历(DLR) 先序遍历的递归过程为:若二叉树为空,遍历结束。否则,

(1)访问根结点;

(2)先序遍历根结点的左子树;

(3)先序遍历根结点的右子树。

 

  • B、中序遍历(LDR) 中序遍历的递归过程为:若二叉树为空,遍历结束。否则,

(1)中序遍历根结点的左子树;

(2)访问根结点;

(3)中序遍历根结点的右子树。

 

  • C、后序遍历(LRD) 后序遍历的递归过程为:若二叉树为空,遍历结束。否则,

(1)后序遍历根结点的左子树;

(2)后序遍历根结点的右子树。

(3)访问根结点;

对于图图1.0(b)所示的二叉树,按先序遍历所得到的结点序列为:G D B E F C A

 

  • D、层次遍历 所谓二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。对于图6.3(b)所示的二叉树,按层次遍历所得到的结果序列为: A B C D E F G 

  • 大小: 2.6 KB
  • 大小: 1.7 KB
  • 大小: 1.9 KB
  • 大小: 1.4 KB
分享到:
评论

相关推荐

    数据结构——二叉树c语言源码

    数据结构——二叉树c语言源码,数据结构——二叉树c语言源码

    数据结构实验——二叉树

    以二叉链表作存储结构,试编写前序、中序、后序遍历二叉树的算法。

    数据结构实验——二叉树的建立和遍历.zip

    1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...

    数据结构实验——二叉树相关操作

    本人本科期间数据结构二叉树的实验 1、建立二叉树的存储结构 2、先序、中序、后序遍历二叉树(要求任选某一种用非递归算法完成) 3、查询二叉树中某个结点 4、统计二叉树中叶子结点的个数 5、求二叉树的深度 6、要求...

    数据结构程序——二叉树

    在计算机科学领域,数据结构是组织和管理大量数据的关键技术之一。其中,二叉树是一种基本且重要的数据结构,尤其在计算机科学的算法设计中扮演着核心角色。本篇文章将深入探讨二叉树的定义、特性、操作以及如何用...

    数据结构——二叉树

    该文件包括二叉树的头文件(BitTree开头)和堆栈的头文件(Seq开头),另外还实现了编写按层次顺序(同一层自左至右)遍历二叉树的算法、后序递归遍历计算二叉树的深度的算法、判断给定二叉树是否为完全二叉树(通过...

    数据结构实验报告——二叉树

    ### 数据结构实验报告——二叉树 #### 实验概述与目的 本次实验的主题是围绕“二叉树”这一核心概念展开。二叉树作为一种重要的非线性数据结构,在计算机科学中有着广泛的应用,例如在搜索算法、排序算法、编译器...

    数据结构——二叉树的实现.zip

    这个压缩包文件"数据结构——二叉树的实现.zip"显然包含了关于二叉树实现的详细内容,特别是二叉链表和左子右兄弟两种不同的实现方法。 首先,我们来探讨二叉链表的实现。二叉链表是最基础的二叉树存储方式,每个...

    广工数据结构实验——平衡二叉树

    本实验“广工数据结构实验——平衡二叉树”着重探讨了一种特殊类型的数据结构,即平衡二叉树。平衡二叉树是二叉搜索树(Binary Search Tree, BST)的一个变体,它通过保持树的高度平衡来确保查找、插入和删除操作的...

    数据结构——二叉树(c++).doc

    数据结构——二叉树(c++).doc

    数据结构实验——二叉树的存储与遍历

    (1)采用链式存储结构建立二叉树,并按先序输入二叉树的结点序列。建立时按先序输入的结点序列为:a b c # # # d e # f # # g # # (2)二叉树的建立采用递归方式实现,先序遍历、中序遍历、后序遍历均采用非递归方式...

    数据结构——二叉树的生成与遍历

    数据结构,实现二叉树的生成与遍历的算法。包含利用先序、中序、后序遍历二叉树算法,二叉树基本操作。(注意没有左子树或右子树时用@或#作为结束符号)

    数据结构——二叉树有关操作程序

    (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现先序遍历、中序遍历、后序...

    数据结构——二叉树 c语言

    二叉树的基本操作 包括 先序建立,深度优先遍历,广度优先遍历

    数据结构课程设计——二叉树

    在数据结构课程设计中,二叉树是一种重要的非线性数据结构,它的概念和操作对于理解和应用计算机科学至关重要。二叉树由节点组成,每个节点最多有两个子节点,分别称为左孩子和右孩子。二叉树可以被用来模拟多种问题...

    c# 数据结构——二叉树——bool运算

    鉴于逻辑表达式中只存在“|”(二元)、“&” (二元)和“~” (一元)三种逻辑运算符,可以采用二叉树的结构存储逻辑表达式,方便表达式的计算。 使用基于栈的逻辑表达式解析和树结构生成方法。 依次读取表达式并...

    数据结构——创建二叉树

    "数据结构——创建二叉树" 在计算机科学中,二叉树是一种重要的数据结构,广泛应用于各个领域。以二叉链表为存储结构,实现二叉树的创建、遍历算法是数据结构课程的基础知识点。本文将详细介绍二叉树的逻辑特点、...

    数据结构——二叉树的四种遍历

    二叉树作为数据结构的一种,是程序设计中常见的基础概念。本文将深入探讨二叉树的四种遍历方法,这对于理解数据结构和算法至关重要,特别是对于初学者来说。 二叉树是由节点构成的层次结构,每个节点最多有两个子...

    数据结构——二叉树 线索化二叉树 C语言

    中序线索二叉树,反方向进行中序遍历(要求非递归,顺前驱进行)。 (1)建立二叉树; (2) 按先序、中序、后序输出二叉树; (3)复制二叉树; (4)在字符模式下画出无缺陷的二叉树

Global site tag (gtag.js) - Google Analytics