数据结构与算法~树

博主： Xherlock
发布时间：2021 年 12 月 17 日
511 次浏览
暂无评论
4717字数
分类：数据结构与算法

# 树和二叉树

## 树（Tree）

### 定义

n个结点的有限集（空或非空）

对于非空树

* 有且仅有一个称之为根的结点
* 除根结点外其余结点可分为m个互不相交的有限集，每个集合本身又是一棵树，称为根的子树（SubTree）

### 基本术语

## 二叉树

基本定义与树差不多

不同点

* 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）
* 二叉树有左右之分，其次序不能颠倒

选择二叉树而不是普通树运算原因：

* 二叉树结构最简单，规律性最强
* 所有树都能转为唯一对应的二叉树，不失一般性

### 性质

* 在第i层上之多有2$^{i-1}$个结点，至少1个
* 深度为k的二叉树至多有2$^{k}$-1个结点，至少k个
* 若2度的结点有n$_{2}$个，则叶子数n$_{0}$=n$_{2}$+1

### 特殊形态二叉树

满二叉树：深度为k且有2$^{k}$-1个结点的二叉树（每层都充满了结点）

完全二叉树：深度为k，有n个结点的二叉树，当且仅当每一个结点都与深度为k的满二叉树中编号从1-n的结点一一对应（最后一层叶子不满，且集中在左边）

满是完全二叉树的一个特例

一棵完全二叉树有n个结点，则叶结点的数为[(n+1)/2]（向下取整），当n为奇数时，由完全二叉树的性质，n$_{1}$（度为1的结点）为1，n$_{0}$=(n+1)/2；n为偶数时，n$_{1}$为0，n$_{0}$=n/2

* 具有n个结点的完全二叉树的深度必为[log$_{2}$n]+1
* 对完全二叉树，若从上至下、从左至右编号，则编号为i的结点，其左孩子编号必为2i，有孩子编号必为2i+1，双亲编号必为i/2

### 顺序存储

按照满二叉树的结点层次编号，依次存放二叉树中的数据元素

### 链式存储

用链表来表示二叉树，通常时链表每个结点由三个域组成，数据与和左右指针域，指针域分别存储该结点左右孩子所在链结点的存储地址

#### 二叉链

存放了左孩子和右孩子的指针

n个结点的二叉链中有n+1个空指针域（除根结点外每个结点都有且仅有1个双亲，所以有n-1个结点的链域存放指针）

#### 三叉链

多存放了个双亲指针

### 遍历二叉树（递归法）

按某条搜索路线遍访每个结点且不重复（插入、删除、修改、查找、排序等）

遍历规则：先左后右

* DLR：先序遍历，先根再左后右
* LDR：中序遍历，先左再根后右
* LRD：后序遍历，先左再右后根

三种方法访问路径相同，只是访问结点的时机不同

由二叉树的前序序列和中序序列、或者后序序列和中序序列均能唯一地确定一棵二叉树，但前序序列和后序序列却无法唯一确定

### 二叉树建立

~~~c
void CreateBiTree(BiTree &T）{
    cin>>ch;
    if (ch==’#’)   
        T=NULL;  	//递归结束，建空树
    else{
        T=new BiTNode;  
        T-＞data=ch; 	//生成根结点
        CreateBiTree(T-＞lchild);  //递归创建左子树
        CreateBiTree(T-＞rchild); //递归创建右子树
    }					
}						
~~~

### 求二叉树结点总数

~~~c
int NodeCount(BiTree T){
    if(T == NULL ) 
        return 0;  			  
    else 
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} 
~~~

### 求二叉树叶子结点总数

~~~c
int LeafCount(BiTree T){
    if(T==NULL) 	//如果是空树返回0
        return 0;
    if (T->lchild == NULL && T->rchild == NULL)
        return 1; //如果是叶子结点返回1
    else 
        return LeafCount(T->lchild) + LeafCount(T->rchild);
}
~~~

### 求二叉树深度

~~~c
int Depth(BiTree T)
{
    if(T==NULL)
        return 0;
    else
    {
        m = Depth(T->lchild);
        n = Depth(T->rchild);
        if(m > n)
            return (m+1);
        else
            return (n+1);
    }
}
~~~

### 线索化二叉树

利用二叉链表空闲区存放当前结点的直接前驱和后继等线索，加快查找速度

* 若结点有左子树，则lchild指向其左孩子，否则指向其直接前驱（即线索）
* 若结点有右子树，则rchild指向其右孩子，否则指向其直接后继（即线索）
* 增加两个标志域LTag和RTag

若LTag=0，lchild指向其左孩子

若LTag=1，lchild指向其前驱

若RTag=0，lchild指向其右孩子

若RTag=1，lchild指向其后继

## 树和森林

### 树的存储结构

* 双亲表示法
* 孩子表示法
* 孩子兄弟法
  ~~~C
  typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild, *nextsibling;
  } CSNode,*CSTree;
  ~~~

### 森林和二叉树转换

森林：F={T$_{1}$, T$_{2}$, ……T$_{m}$}	二叉树B=(root, LB, RB)

森林=》二叉树

* 若F为空，即m=0，则B为空树
* 若F非空，则B的根root即为森林中的第一棵树的根ROOT(T~1~),B的左子树LB是从T~1~中根结点的子树森林F$_{1}$={T$_{11}$, T$_{12}$, ……T$_{1m}$}转换而成的二叉树，右子树RB是从森林F'={T$_{2}$, T$_{3}$, ……T$_{m}$}转换而成的二叉树

二叉树=》森林

## 哈夫曼树及其应用

### 哈夫曼树

* 路径：由一结点到另一结点间的分支所构成
* 路径长度：路径上的分支数目
* 带权路径长度：结点到根的路径长度于结点上权的乘积
* 树的带权路径长度：树中所有叶子结点的带权路径长度之和

$$
  WPL=\sum_{k=1}^nw_kl_k

$$
* 哈夫曼树：带权路径长度最小的树

![image-20211217193922858.png](http://xherlock.top/usr/uploads/2021/12/2900830699.png)

哈夫曼树构造：使权大的结点靠近根

操作：对权值的合并、删除、替换总是合并当前值最小的两个

### 应用

哈夫曼编码的构造：概率大的字符用短码，小的用长码，构造哈夫曼树

![image-20211217194744779.png](http://xherlock.top/usr/uploads/2021/12/3074901170.png)

~~~c
typedef  struct
{  
    int weght;
    int parent,lch,rch;
}*HuffmanTree;
~~~

~~~c
void CreatHuffmanTree (HuffmanTree HT,int n){
    if(n<=1)
        return;
    m=2*n-1;
    HT=new HTNode[m+1];//0号单元未用，HT[m]表示根结点   
    for(i=1;i<=m;++i)
    {
        HT[i].lch=0;
        HT[i].rch=0;
        HT[i].parent=0;
    }
    for(i=1;i<=n;++i)
        cin>>HT[i].weight;  
}
~~~

最后修改：2021 年 12 月 19 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

网络安全风险管理
浏览次数: 535
计组复习1~一、二、四单元
浏览次数: 434
推荐工具软件和浏览器插件
浏览次数: 620
XSS-labs Less 11-16
浏览次数: 432
Reverse（二）
浏览次数: 547

数据结构与算法~树

Xherlock • 2021 年 12 月 17 日

# 树和二叉树

## 树（Tree）

### 定义

n个结点的有限集（空或非空）

对于非空树

* 有且仅有一个称之为根的结点
* 除根结点外其余结点可分为m个互不相交的有限集，每个集合本身又是一棵树，称为根的子树（SubTree）

### 基本术语

## 二叉树

基本定义与树差不多

不同点

* 二叉树每个结点至多只有两棵子树（即二叉树中不存在度大于2的结点）
* 二叉树有左右之分，其次序不能颠倒

选择二叉树而不是普通树运算原因：

* 二叉树结构最简单，规律性最强
* 所有树都能转为唯一对应的二叉树，不失一般性

### 性质

* 在第i层上之多有2$^{i-1}$个结点，至少1个
* 深度为k的二叉树至多有2$^{k}$-1个结点，至少k个
* 若2度的结点有n$_{2}$个，则叶子数n$_{0}$=n$_{2}$+1

### 特殊形态二叉树

满二叉树：深度为k且有2$^{k}$-1个结点的二叉树（每层都充满了结点）

满是完全二叉树的一个特例

### 顺序存储

按照满二叉树的结点层次编号，依次存放二叉树中的数据元素

### 链式存储

用链表来表示二叉树，通常时链表每个结点由三个域组成，数据与和左右指针域，指针域分别存储该结点左右孩子所在链结点的存储地址

#### 二叉链

存放了左孩子和右孩子的指针

n个结点的二叉链中有n+1个空指针域（除根结点外每个结点都有且仅有1个双亲，所以有n-1个结点的链域存放指针）

#### 三叉链

多存放了个双亲指针

### 遍历二叉树（递归法）

按某条搜索路线遍访每个结点且不重复（插入、删除、修改、查找、排序等）

遍历规则：先左后右

* DLR：先序遍历，先根再左后右
* LDR：中序遍历，先左再根后右
* LRD：后序遍历，先左再右后根

三种方法访问路径相同，只是访问结点的时机不同

由二叉树的前序序列和中序序列、或者后序序列和中序序列均能唯一地确定一棵二叉树，但前序序列和后序序列却无法唯一确定

### 二叉树建立

### 求二叉树结点总数

~~~c
int NodeCount(BiTree T){
    if(T == NULL ) 
        return 0;  			  
    else 
        return NodeCount(T->lchild)+NodeCount(T->rchild)+1;
} 
~~~

### 求二叉树叶子结点总数

### 求二叉树深度

### 线索化二叉树

利用二叉链表空闲区存放当前结点的直接前驱和后继等线索，加快查找速度

若LTag=0，lchild指向其左孩子

若LTag=1，lchild指向其前驱

若RTag=0，lchild指向其右孩子

若RTag=1，lchild指向其后继

## 树和森林

### 树的存储结构

* 双亲表示法
* 孩子表示法
* 孩子兄弟法
  ~~~C
  typedef struct CSNode{
  ElemType data;
  struct CSNode *firstchild, *nextsibling;
  } CSNode,*CSTree;
  ~~~

### 森林和二叉树转换

森林：F={T$_{1}$, T$_{2}$, ……T$_{m}$}	二叉树B=(root, LB, RB)

森林=》二叉树

二叉树=》森林

## 哈夫曼树及其应用

### 哈夫曼树

$$
  WPL=\sum_{k=1}^nw_kl_k

$$
* 哈夫曼树：带权路径长度最小的树

![image-20211217193922858.png](http://xherlock.top/usr/uploads/2021/12/2900830699.png)

哈夫曼树构造：使权大的结点靠近根

操作：对权值的合并、删除、替换总是合并当前值最小的两个

### 应用

哈夫曼编码的构造：概率大的字符用短码，小的用长码，构造哈夫曼树

![image-20211217194744779.png](http://xherlock.top/usr/uploads/2021/12/3074901170.png)

~~~c
typedef  struct
{  
    int weght;
    int parent,lch,rch;
}*HuffmanTree;
~~~

发表评论 取消回复

数据结构与算法~树

发表评论取消回复