树与二叉树
目录
树
树的定义：具有相同特性的n个结点（数据元素）的有限集合;
（递归的定义方式）
1. 若n=0，则称为空树 。
2. 否则：存在唯一的根(root)结点;
3. 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T[1], T[2], …, T[m]，其中每一个子集本身又是一棵符合本定义的树，称为根root的子树。
树的特点以及相关概念：
特点：
层次（树型）结构，一对多
- 一个数据元素若有直接前驱，只能有一个直接前驱
- 一个数据元素若有直接后继，可以有多个直接后继
相关概念：
- 结点：数据元素+若干指向子树的分支
- 结点的度(图论中的出度)：分支的个数，子树的个数
- 树的度：树中所有结点的度的最大值
- 叶子结点：度为零的结点
- 分支结点：度大于零的结点
- 结点路径：由从根到该结点所经分支和结点构成
- 结点的层次：设根结点的层次为1，每个结点的层次值为其父结点的层次值+1
- 树的深度(书高)：树中叶子结点所在的最大层次
- 森林：是m（m≥0）棵互不相交的树的集合
- 任何一棵非空树是一个二元组 Tree = （root，F）
- 其中：root为根节点，F为子树森林
二叉树
二叉树的定义
二叉树：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(有左右之分)
二叉树的五种基本形态：
- 空树
- 只含有根节点
- 左右子树均存在
- 只有左子树(右子树为空树)
- 只有右子树(左子树为空树)
二叉树的性质
性质：
- 二叉树的第 i层上至多有2(i-1)个结点(i≥1)。
- 深度为k的二叉树上至多含2(k-1)个结点(k≥1)。达到最多的时候，就是满二叉树。
- *对任何一棵二叉树，若它含有n0个叶子结点、n2个度为 2的结点，则必存在关系式n0=n2+1。
- *具有 n 个结点的完全二叉树的深度为: [ [\log_2 n] + 1 ]
两类特殊的二叉树
满二叉树 1. 满二叉树：指的是深度为k且含有2k-1个结点的二叉树。 2. 特点：二叉树的每一层都具有最多结点数。 3. 层次编号：从根节点开始，自上而下，自左到右，从1开始给树中每个结点编号。完全二叉树
1. 完全二叉树：树中所含的 n个结点和满二叉树中编号为 1 至 n 的结点一一对应。
2. 特点：结点没有左孩子一定没有右孩子；**度为1的结点最多有一个
**
二叉树–存储结构
二叉树可以采用：
- 顺序存储表示：数据元素的存储位置体现逻辑关系
- 链式存储表示：指针体现逻辑关系
二叉树的顺序存储表示
一维数组存放二叉树的每个结点；
每个结点在数组中存放的位置（下标）为高度相同的满二叉树中对应结点的层次编号
1.顺序存储结构适合存放完全二叉树,顺序存储结构存放单支树浪费存储
2.每个结点对应的数组元素的下标（即存放位置）--表示逻辑关系
二叉树的链式存储表示
二叉链表
结点结构 [lchild,data,rchild]
特点：二叉链表找子孙结点容易，找祖先结点麻烦。
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild; //左右子树根结点地址
} BiTNode, *BiTree;
三叉链表
结点结构：[parent,lchild,data,rchild]
特点：三叉链表找子孙结点容易，找祖先结点也容易。
typedef struct TriTNode {
char data;
struct TriTNode *lchild, *rchild; //左右子树根结点地址
struct TriTNode *parent; //双亲结点地址
} TriTNode, *TriTree;
双亲数组
结点结构:[data,parent,LRTag]
特点：双亲数组存放二叉树，一个数组元素存放二叉树中一个结点，存放结点的值、其双亲的存放位置（在数组中的下标），以及他是其双亲的左还是右孩子。
双亲数组不是二叉树的顺序存储结构，而是链式存储结构！它不是通过存放位置表示逻辑关系，而是需要通过parent这个“指针”明确父子关系.
#define MAX_TREE_SIZE 100 // 二叉树的最大结点数
typedef struct BPTNode {
ElemType data;//结点的值
int parent; //双亲结点的位置
char LRTag; //左孩子、右孩子的标记
} BPTNode;
typedef struct BPTree{
BPTNode nodes[MAX_TREE_SIZE];
int n，r; //n为树中结点数，r为根结点位置
} BPTree;
说明：双亲数组表示法不能保证二叉树的根结点一定存放于下标为“0”的第一个数组元素。在一些应用中，初始时无法确定根结点，随着逻辑关系的分析，一步步最后确定根结点，这样无法在建立双亲数组确保根结点一定会放在下标为“0”处.
遍历二叉树
遍历：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。
“访问”的含义可以很广，如：对结点进行处理、输出结点的信息等。
约定：左子树先于右子树访问
二叉树的遍历分成三种，按照根节点的访问先后分为：
- 先序遍历（先根遍历）：先访问根节点，然后访问左子树， 最后访问右子树。
- 中序遍历（中根遍历）：先访问左子树，然后访问根节点， 最后访问右子树。
- 后序遍历（后根遍历）：先访问左子树，然后访问右子树，
最后访问根节点.
先序遍历：ABDCEF
中序遍历：BDACFE
后序遍历：DBFECA
先（根）序的遍历算法
先序遍历（递归定义 递归结束的条件就是：空树 ）
- 若二叉树为空树，则空操作；
- 否则，（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。
先序遍历的递归算法：
//先序遍历 递归访问每一个结点
void xxbl(BiTree T){
if(T){//递归调用的结束条件
printf("%c",T->data);//访问结点
xxbl(T->lchild);//遍历左子树
xxbl(T->rchild);//遍历右子树
}
}
中（根）序的遍历算法
- 若二叉树为空树，则空操作；
- 否则，（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。
中序遍历的递归算法：
void zxbl(BiTree T)
{
if (T) {
zxbl(T->lchild);
printf(“%c”,T->data);
zxbl(T->rchild);
}
}
后（根）序的遍历算法
- 若二叉树为空树，则空操作；
- 否则，（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。
void hxbl(BiTree T)
{
if(T){
hxbl(T->lchild);
hxbl(T->rchild);
printf(“%c”,T->data);
}
}
遍历二叉树——相关结论
■ 树中结点均不相同
■ 先序+中序 唯一确定一棵二叉树
■ 后序+中序 唯一确定一棵二叉树
例：先序 abdjcefhi 中序 djbaechfi
解：先序 a(根) bdj(左) c e fhi(右) 中序 djb(左) a(根) ec hfi(右)
应用
二叉树存放表达式
． 二叉树存放表达式 ：
波兰式： +dj/e+hi ．
中缀表示: dj+e/(h+i) ．
逆波兰式: dj*ehi+/+
求二叉树的高
//求二叉树的高
typedef struct TreeNode{
int data;//数据域
TreeNode *RChild;//右孩子指针
TreeNode *LChild;//左孩子指针
}TreeNode, *BiTree;
int Get_Height(TreeNode* node) {
if (node == NULL) return 0;//终止条件：如果为空节点，返回0，表示高度为0
int Left_Height = Get_Height(node->LChild);//递归求左子树高度
int Right_Hegiht = Get_Height(node->RChild);//递归求右子树高度
int Tree_Height = 1 + (Left_Height > Right_Hegiht?Left_Height:Right_Hegiht);//计算树高
return Tree_Height;
}
二叉树的建立
以先序序列定义一棵二叉树：输入所要建立的二叉树的先序序列，建立二叉链表。
在输入的二叉树的先序序列中，加入空树明确表示"#"。
按先序遍历序列建立二叉树的二叉链表
已知先序 序列为：ABC##DE##F###
二叉树的建立的算法：
//二叉树的建立的算法(按先序遍历序列建立)
void CreateBiTree(BiTree &T) {
scanf(“%c”,&ch);
if (ch==‘# ’) T = NULL;
else {
T = (BiTNode *)malloc(sizeof(BiTNode))；
T->data = ch; // 生成根结点
CreateBiTree(T->lchild); // 构造左子树
CreateBiTree(T->rchild); // 构造右子树
}
}