【数据结构——树和二叉树】

目录：

• 【数据结构——树和二叉树】
• 一、树和二叉树的定义
• • （一）树的定义
  • （二）基本术语
  • （三）二叉树的定义
  • • 1、二叉树的定义
    • 2、二叉树的基本特点
• 二、二叉树的性质和存储结构
• • （一）二叉树的性质
  • （二）二叉树的存储结构
  • • 1、顺序存储结构
    • 2、链式存储结构

一、树和二叉树的定义

（一）树的定义

树是n个结点的有限集，它或为空树（n=0）;或为非空树

（二）基本术语

（三）二叉树的定义

1、二叉树的定义

二叉树是n（n>=0）个结点所构成的集合，他或为空树（n=0）,或为非空树，对于非空树：T
（1）有且只有一个称之为根的结点；
（2）除根结点之外的其余结点分为两个互不相交的子集T1和T2，分别称为T的左子树和右子树，且T1和T2本身都是二叉树。

2、二叉树的基本特点

（1）结点的度小于等于2；
（2）有序树（子树有左右之分，且其次序不能任意颠倒）

二、二叉树的性质和存储结构

（一）二叉树的性质

满二叉树：一棵深度为K且有2的K次方-1个结点的二叉树。（特点：每层都充满了结点）

完全二叉树：深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应。

（二）二叉树的存储结构

1、顺序存储结构

实现：按完全二叉树的结点层次编号，依次存放二叉树中的数据元素。
特点：
（1）结点间关系蕴含在其存储位置中；
（2）浪费空间，适于存满二叉树和完全二叉树。

结点i:
双亲结点：【i/2】
左儿子：2i
右儿子：2i + 1

#define MAXTSIZE 100 //二叉树的最大结点数
typedef TElemType SqBiTree[MAXTSIZE];//0号单元存储根结点
SqBiTree bt;

2、链式存储结构

（1）二叉链表

typedef struct BiNode
{ 
	TElemType data;   //数据域
	struct BiNode* lchild, * rchild;   //左右孩子指针
}BiNode,*BiTree;   //二叉树结点
BiTree root;

在n个结点的二叉链表中，有n+1个空指针域

（2）三叉链表

typedef struct TriTNode
{ 
	TElemType data;   //数据域
	struct TriTNode* lchild,* parent * rchild;   //左右孩子指针
}TriTNode,*TriTree;   //二叉树结点