美文网首页
【数据结构】【C#】025-二叉树(BT):🌱存储结构

【数据结构】【C#】025-二叉树(BT):🌱存储结构

作者: lijianfex | 来源:发表于2018-11-09 14:31 被阅读12次

1、二叉树的定义

二叉树T:一个有穷的结点集合( 这个集合可以为空 )
若不为空,则它是由根结点和称为其左子树TL和右子树TR的 两个不相交的二叉树组成。
  • 二叉树具体五种基本形态 :
  • 二叉树的子树有左右顺序之分 :
  • 特殊二叉树 :

1、斜二叉树(Skewed Binary Tree):


2、完美二叉树(Perfect Binary Tree) 满二叉树(Full Binary Tree):

3、完全二叉树 (Complete Binary Tree) :

有n个结点的二叉树,对树中结点按 从上至下、从左到右顺序进行编号, 编号为i(1 ≤ i ≤ n)结点与满二叉树 中编号为 i 结点在二叉树中位置相同

下图不是完全二叉树:


2、二叉树几个重要性质

  • 一个二叉树第i 层的最大结点数为:2^( i-1 ) (i >=1)
  • 深度为k的二叉树有最大结点总数为: 2^ k-1 (k>=1)
  • 对任何非空二叉树 T,若n0表示叶结点的个数、n2是 度为2的非叶结点个数,那么两者满足关系n0 = n2 +1

3、二叉树的抽象数据类型定义

类型名称:二叉树
数据对象集:一个有穷的结点集合。 若不为空,则由根结点和其左、右二叉子树组成。

操作集: BT属于 BinTree, Item 属于ElementType,重要操作有:

1、Boolean IsEmpty( BinTree BT ): 判别BT是否为空;
2、void Traversal( BinTree BT ):遍历,按某顺序访问每个结点;
3、BinTree CreatBinTree( ):创建一个二叉树。

常用遍历方法:

  • void PreOrderTraversal( BinTree BT ):先序----根、左子树、右子树
  • void InOrderTraversal( BinTree BT ): 中序---左子树、根、右子树
  • void PostOrderTraversal( BinTree BT ):后序---左子树、右子树、根
  • void LevelOrderTraversal( BinTree BT ):层次遍历,从上到下、从左到右

4、二叉树的存储结构

1. 顺序存储结构 :


2. 链表存储 :

相关文章

  • 【数据结构】【C#】025-二叉树(BT):🌱存储结构

    1、二叉树的定义 二叉树T:一个有穷的结点集合( 这个集合可以为空 )若不为空,则它是由根结点和称为其左子树TL...

  • C# 实现二叉树的遍历算法

    C# 实现二叉树的遍历算法 数据结构 BiTreeNode: 树节点public char Value { get...

  • 无标题文章

    # 数据结构与算法之二叉树的存储结构 ``` #include typedef char Elemtype; ty...

  • IOS基础知识-算法与数据结构篇

    数据结构 通常可以分为四类: 数据结构的存储方式: 链表可分为: 什么是树 什么是二叉树 二叉树遍历 在二叉树的一...

  • 数据结构 - 概要

    数组 链表 堆/栈/队列 树 数据结构 - 二叉树数据结构 - 二叉查找树数据结构 - 平衡二叉树数据结构 - A...

  • 二叉树的顺序存储

    前言 顺序存储结构难些。因为树是一种一对多的数据结构,由于它的特殊性使用顺序存储结构也可以实现。 顺序存储二叉树:...

  • 孩子兄弟链存储结构

    二叉树的孩子兄弟链存储结构 数据结构的大作业实在是头疼,想了好久然后觉得孩子兄弟链存储结构比较合适 先放完整的代码...

  • 数据结构

    一. 数据结构的分类 集合结构 线性结构 树形结构 图形结构 二. 数据结构的存储 顺序存储结构 和 链式存储结构...

  • 面试基础复习

    1.数据结构的存储 数据结构的存储一般常用的有两种: 顺序存储结构 和 链式存储结构。顺序存储结构和链式存储结构的...

  • 2.什么是数据结构

    数据结构是计算机存储、组织数据的方式 线性结构:线性表(数组,链表,桟,队列,哈希表) 树形结构:二叉树,AV...

网友评论

      本文标题:【数据结构】【C#】025-二叉树(BT):🌱存储结构

      本文链接:https://www.haomeiwen.com/subject/bifoxqtx.html