数据结构之树与二叉树
寜静致逺 Lv3

树的定义

树是一种非线性的数据结构。它是若干结点(A,B,C等都是结点)的集合,是由唯一的根(结点A)和若干棵互不相交的子树(如B,E,F,K,L这5个结点组成的树就是一棵子树)组成的。树的结点数目可以为0,当为0时,这棵树称为空树。

树的基本术语

节点的度:树中某个节点的子树的个数。

树的度:树中各节点的度的最大值。

分支节点:度不为零的节点。

叶子节点:度为零的节点。

路径:i->j;路径长度:路径经过节点数目减1。

孩子节点:某节点的后继节点;双亲节点:该节点为其孩子节点的双亲节点(父母节点);兄弟节点:同一双亲的孩子节点;子孙节点:某节点所有子树中的节点;祖先节点:从树节点到该节点的路径上的节点。

节点的层次:根节点为第一层(以此类推);树的高度:树中节点的最大层次。

有序树:树中节点子树按次序从左向右安排,次序不能改变;无序树:与之相反

森林:互不相交的树的集合。

二叉树的定义

1.每个结点最多只有两颗子树,即二叉树中结点的度只能为0,1,2。
2.子树有左右顺序之分,不能颠倒。

二叉树的主要性质

非空二叉树上叶子结点数等于双分支结点数加1

所有结点的分支数等于单分支结点数加上双分支结点数的两倍。

总分支数=总结点数-1

度为m的树中第i层最多有m^(i-1)个节点; 二叉树的第i层上最多有2^(i-1)个结点。

高度(或深度)为k的二叉树最多有2^k -1(k>=1)个结点.换句话说,满二叉树中前k层的结点个数为2^k -1。

几种特殊的二叉树

斜树:所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

满二叉树:在一棵二叉树中。如果所有分支结点都存在左子树和右子树,并且所有叶子都在同一层上,这样的二叉树称为满二叉树。

满二叉树的特点有:

1)叶子只能出现在最下一层。出现在其它层就不可能达成平衡。

2)非叶子结点的度一定是2。

3)在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。

完全二叉树:对一颗具有n个结点的二叉树按层编号,如果编号为i(1<=i<=n)的结点与同样深度的满二叉树中编号为i的结点在二叉树中位置完全相同,则这棵二叉树称为完全二叉树。

二叉树的遍历



前序遍历:

中序遍历:

后序遍历:

树的遍历


二叉树的遍历算法

二叉树深度优先遍历的递归实现

先序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
void preorder(BTNode *p)
{
if(p!=NULL)
{
Visit(p)
//假设访问函数Visit ()已经定义过,
//其中包含了对结点p的各种访问操作,
//如可以打印出p对应的数值。
preorder(p->lchild);
preorder(p->rchild);
}
}

中序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
void inorder(BTNode *p)
{
if(p!=NULL)
{
preorder(p->lchild);
Visit(p)
//假设访问函数Visit ()已经定义过,
//其中包含了对结点p的各种访问操作,
//如可以打印出p对应的数值。
preorder(p->rchild);
}
}

后序遍历:

1
2
3
4
5
6
7
8
9
10
11
12
void postorder(BTNode *p)
{
if(p!=NULL)
{
preorder(p->lchild);
preorder(p->rchild);
Visit(p)
//假设访问函数Visit ()已经定义过,
//其中包含了对结点p的各种访问操作,
//如可以打印出p对应的数值。
}
}

已知前序遍历序列为A,B,C,D,E,F,中序遍历序列为C,B,A,E,D,F,则后序遍历序列为:

前序:A,B,C,D,E,F
中序:C,B,A,E,D,F
先看前序遍历序列,则知道A为根结点,再看中序遍历序列,C,B,A,E,D,F ,A左边的为左子树,A右边的为右子树
再看前序序列,B为根节点,又因为中序系列中C在B的左边,所以C为B的左子树,再看前序序列,D为根节点,再看中序序列(只需看A的右边),E,D,F, 显然E为D的左子树,F为D的右子树。
则后序遍历序列为CBEFDA

已知后序遍历序列为D,E,C,B,H,G,F,A,中序遍历序列为B,D,C,E,A,F,H,G,则前序遍历序列为:

后序:D,E,C,B,H,G,F,A
中序:B,D,C,E,A,F,H,G
先看后序遍历序列,则知道A为根结点,再看中序遍历序列,B,D,C,E为A的左子树部分,F,H,G为A的右子树部分,再看后序序列,F为根节点,因为H,G在F的右边,所以,H,G,为F的又子树,再看后序序列,G为根结点,再看中序序列,H在G的左边,所有,H为G的左子树,再看后序序列,B为根结点,再看中序序列,则知DCE为B的右子树部分,再看后序序列,C为根结点,再看中序序列(DCE),知D为C的左子树,E为C的右子树。
则前序遍历序列为:A,B,C,D,E,F,G,H

二叉树遍历算法的改进

二叉树深度优先遍历的非递归实现

……

赫夫曼树和赫夫曼编码

赫夫曼树又叫作最优二叉树,它的特点是带权路径最短。

关于几个路径的概念:

1.路径:路径是指从树中一个结点到另一个结点的分支所构成的路线。
2.路径长度:路径长度是指路径上的分支数目。
3.树的路径长度:树的路径长度是指从根到每个结点的路径长度之和。
4.带权路径长度:结点具有权值,从结点到根之间的路径长度乘以结点的权值,就是该结点的带权路径长度。
5.树的带权路径长度(WPL):树的带权路径长度是指树中所有叶子结点的带权路径长度之和。

构造哈夫曼树

频率表(权值) A:60, B:45, C:13 D:69 E:14 F:5 G:3

第一步:找出字符中最小的两个,小的在左边,大的在右边,组成二叉树。在频率表中删除此次找到的两个数,并加入此次最小两个数的频率和。

F和G最小,因此如图,从字符串频率计数中删除F与G,并返回G与F的和 8给频率表

重复第一步:


频率表 A:60, B:45, C:13 D:69 E:14 FG:8

最小的是 FG:8与C:13,因此如图,并返回FGC的和:21给频率表。


重复第一步:


频率表 A:60 B: 45 D: 69 E: 14 FGC: 21

如图


重复第一步


频率表 A:60 B: 45 D: 69 FGCE: 35


重复第一步


频率表 A:60 D: 69 FGCEB: 80


重复第一步


频率表 AD:129 FGCEB: 80

添加 0 和 1,规则左0 右1

频率表 A:60, B:45, C:13 D:69 E:14 F:5 G:3

每个 字符 的 二进制编码 为(从根节点 数到对应的叶子节点,路径上的值拼接起来就是叶子节点字母的应该的编码)

字符 编码
A 10
B 01
C 0011
D 11
E 000
F 00101
G 00100

那么当我想传送 ABC时,编码为 10 01 0011

  • 本文标题:数据结构之树与二叉树
  • 本文作者:寜静致逺
  • 创建时间:2021-01-16 18:43:16
  • 本文链接:https://hujiahao6.gitee.io/2021/01/16/树与二叉树/
  • 版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
 评论