数据结构初阶：二叉树

树概念及结构

树的概念

注意：树形结构中，子树之间不能有交集，否则就不是树形结构

 树的相关概念

节点的度：一个节点含有的子树的个数称为该节点的度； 如上图：A的为6

叶节点或终端节点：度为0的节点称为叶节点； 如上图：B、C、H、I...等节点为叶节点

树的表示

typedef int DataType ;

struct Node

{

struct Node * _firstChild1 ; // 第一个孩子结点

struct Node * _pNextBrother ; // 指向其下一个兄弟结点

DataType _data ; // 结点中的数据域

};

 树在实际中的运用（表示文件系统的目录树结构）

 二叉树概念及结构

概念

从上图可以看出：

注意：对于任意的二叉树都是由以下几种情况复合而成的：

 现实中的二叉树：

特殊的二叉树：

二叉树的性质

二叉树的存储结构 

顺序结构存储就是使用 数组来存储 ，一般使用数组 只适合表示完全二叉树，因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储，关于堆我们后面的章节会专门讲解。二叉树顺序存储在物理上是一个数组，在逻辑上是一颗二叉树。

typedef int BTDataType ;

// 二叉链

struct BinaryTreeNode

{

struct BinTreeNode * _pLeft ; // 指向当前节点左孩子

struct BinTreeNode * _pRight ; // 指向当前节点右孩子

BTDataType _data ; // 当前节点值域

}

// 三叉链

struct BinaryTreeNode

{

struct BinTreeNode * _pParent ; // 指向当前节点的双亲

struct BinTreeNode * _pLeft ; // 指向当前节点左孩子

struct BinTreeNode * _pRight ; // 指向当前节点右孩子

BTDataType _data ; // 当前节点值域

} ；

二叉树的顺序结构及实现

二叉树的顺序结构

堆的概念及结构