二叉树
2020-05-02 16:00:33来源:博客园 阅读 ()
二叉树
每个结点最多有两个孩子,其余结构和树的结构一样。
1. 二叉树特点
二叉树的特点有:
- 每个结点最多有两棵子树,所以二叉树中不存在度大于2的结点。
- 左子树和右子树是有顺序的,次序不能任意颠倒。
- 即使树中某结点只有一棵子树,也要区分它是左子树还是右子树。
二叉树有五种基本形态:
- 空二叉树;
- 只有一个根节点;
- 根节点只有左子树;
- 根节点只有右子树;
- 根节点既有左子树又有右子树。
2. 特殊二叉树
-
斜树。所有结点只有左子树(或右子树)的二叉树称为左斜树(右斜树)。
-
满二叉树。所有结点(除了叶子结点)都存在左子树和右子树,且所有叶子结点均在同一层上。
满二叉树的特点有:
- 叶子只能出现在最下一层;
- 非叶子结点的度一定为
2
; - 在同样深度的二叉树中,满二叉树的结点个数最多,叶子数最多。
-
完全二叉树。对一棵具有
n
个结点的二叉树按层序编号,如果编号为i(1≤i≤n)
的结点与同样深度的满二叉树中编号为i
的结点在二叉树中位置完全相同,这个二叉树为完全二叉树。图
完全二叉树的特点:
- 叶子结点只能出现最下两层;
- 最下层的叶子一定集中在左部连续位置;
- 倒数二层,若有叶子结点,一定都在右部连续位置;
- 如果结点度为
1
,则该结点只有左孩子,即不存在只有右子树的情况; - 同样结点数的二叉树,完全二叉树的深度最小。
2. 二叉树的性质
- 在二叉树的第
i
层上至多有\(2^{i-1} (i≥1)\)?个结点。 - 深度为
k
的二叉树至多有\(2^k-1 (k≥1)\)个结点。 - 对任何一棵二叉树
T
,如果其终端结点数为\(n_0\),度为2
的结点数为\(n_2\),则\(n_0=n_2+1\)。 - 具有
n
个结点的完全二叉树的深度为\([log_2n]+1\)([x]
表示不大于x
的最大整数)。 - 对于具有
n
个结点的完全二叉树,其结点按照层序编号,对任意结点\(i (1≤i≤n)\)有:- 如果\(i=1\),则结点
i
是二叉树的根,无双亲;如果\(i≥1\),则其双亲结点为\([i/2]\)。 - 如果\(2i>n\),则结点
i
无左孩子(结点i
为叶子结点);否则其左孩子是结点2i
。 - 如果\(2i+1>n\),则结点
i
无右孩子;否则其右孩子是结点\(2i+1\)。
- 如果\(i=1\),则结点
3.二叉树遍历
遍历二叉树的方法:
-
先序遍历
- 首先对根节点进行访问
- 然后访问左子树
- 最后访问右子树
DLR
模式
2.中序遍历
- 首先访问左子树
- 后访问根节点
- 最后访问右子树
LDR
模式
-
后序遍历
- 首先访问左子树
- 然后访问右子树
- 最后访问根节点
LRD
模式
//先序遍历DLR
void PreorderTraverse(BTNode<T> *p) //p为二叉树的根节点,以下同是
{
if (p != NULL)
{
this->Visit(p);
this->PreorderTraverse(p->lchild);
this->PreorderTraverse(p->rchild);
}
}
//中序遍历LDR
void InorderTraverse(BTNode<T> *p)
{
if (p != NULL)
{
this->InorderTraverse(p->lchild);
this->Visit(p);
this->InorderTraverse(p->rchild);
}
}
//后序遍历LRD
void Postordertraverse(BTNode<T> *p)
{
if (p != NULL)
{
this->Postordertraverse(p->lchild);
this->Postordertraverse(p->rchild);
this->Visit();
}
}
4. 二叉树遍历的应用
//统计叶子结点的数目
int GetNumOfLeaf(BTNode<T> *p)
{
int number = 0;
if (p == NULL)
number = 0;
else if (p->lchild == NULL && p->rchild == NULL)
number = 1;
else
number = this->GetNumOfLeaf(p->lchild) + this->GetNumOfLeaf(p->rchild);
return number;
}
//计算二叉树的高度
int GetHeight(BTNode<T> *p)
{
int height = 0;
if (p == NULL)
height = 0;
else if (p->lchild == NULL && p->rchild == NULL)
height = 1;
else
{
int lheight = this->GetHeight(p->lchild) + 1;
int rheight = this->GetHeight(p->rchild) + 1;
height = lheight > rheight ? lheight : rheight;
}
return height;
}
5. 中序线索化二叉树
? 原理:
? 为了节省资源空间,将空闲的指针域给利用起来,将此指针域设为该结点的前驱或后继指针
- 如果该结点的左指针域为空,则将此指针域指向该结点的前驱;
- 如果该结点的右指针域为空,则将此指针域指向该结点的后继;
- 为了辨别该结点的左右指针域的指向,需要在结点中加入两个布尔变量
Ltag
和Rtag
。如果Ltag=0
或Rtag=0
则表明该结点的左或右孩子存在;否则,指向前驱或后继指针。
? 实现:
- 首先遍历整个二叉树
BinTree
,先序,中序,后序都可
if(BinTree!=NULL)
{
Inordertraverse(BinTree->lchild);
dosomething;
Inordertraverse(BinTree->rchild);
}
- 判断当前结点的左孩子是否存在,若存在则让
BinTree->Ltag=0
;
? 否则BinTree->Ltag=1;BinTree->lchild=pre;
(pre
为当前结点的前驱结点,就是遍历的上一个结点)
? 3. 判断前驱结点pre
的右孩子是否存在,若存在则让BinTree->Rtag=0
;
? 否则pre->Rtag=1;pre->rchild=BinTree
;
? 4. 令前驱结点pre
始终保持在当前结点的上一个结点,即:pre=BinTree
;
? 代码实现:
if(BinTree->lchild==NULL)
{
BinTree->Ltag=1;
BinTree->lchild=pre;
}
if(pre!=NULL&&pre->rchild==NULL)
{
pre->Rtag=1;
pre->rchild=BinTree;
}
pre=BinTree;
中序线索二叉树查找某个结点p
的前驱结点pre
- 根据中序遍历方法
LDR
可知,结点p
的前驱结点应是p
的左子树; - 如果该结点的左孩子标志点
p->Ltag=1
;则该结点的前驱为pre=p->lchild
; - 如果该结点的左孩子存在即
p->Ltag=0
;
? 根据中序遍历的定义可知,结点p
的前驱结点应是p
的左子树的“最下右孩子”;
? 用代码可表示为:
q=p->lchild;
while(q->Rtag==0)
{
q=q->rchild;
}
pre=q;
? 中序线索二叉树查找某个结点p
的后继结点next
,方法原理同上。
中序线索二叉树的插入和删除操作
? 插入操作:
? 向二叉树中结点p
的右孩子插入结点r
,即p->rchild=r
;
? 1. 首先遍历二叉树,找到结点p
-
- 如果结点
p
的右孩子不存在,即p->Rtag=1
; - 则
p
的后继变为r
,r
的后继变为p
原来的后继p->rchild
,r
的前驱为p
- 即:
r->Ltag=1;r->lchild=p;r->Rtag=1;r->rchild=p->rchild;p->rchild=r
;注意顺序不能变
- 如果结点
-
- 如果结点
p
的右孩子存在,即p->Rtag=0
; - 则将结点
r
变为p
结点的右孩子,原来p
的右孩子变为r
的右孩子 - 则
p
的后继将变为r
,p
为r
的前驱 r
的后继变为右子树“最下端左孩子”
- 如果结点
? 代码实现:
if(p->Rtag==1)
{
BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:1,lchild:p,rchild:p->rchild);
p->rchild=r;
p->Rtag=0;
}
else
{
BTNode<T> *r=new BTNode<T>(Data:data,Ltag:1,Rtag:0,lchild:p,rchild:p->rchild);
p->rchild=r;
BTNode<T> *q=r->rchild;
while(q->Ltag==0)
{
q=q->lchild;
}
q->lchild=r;
}
? 删除操作和插入操作类似相同,方法和原理同上。
6. 哈夫曼树
? 哈夫曼树是指带权路径最小的二叉树。
? 给定一定的带权叶子结点,构造哈夫曼树:
? 1. 在这些结点中寻找两个权最小的叶子结点,这两个结点与\(N_1\)结点组成一棵树,\(N_1\)结点的权变为两个结点的和;
? 2. 将\(N_1\)结点和其它叶子结点放在一起,在其中找到两个权最小的树,组成一棵新树;
? 3. 注意在组成新树时,将权相对较小的值作为左孩子;
? 4. 以此类推,重复上述的步骤,最终将得到哈夫曼树。
? 根据以上的构造可以得到,哈夫曼树只有度为2
的结点和叶子结点,故当哈夫曼树有n
个叶子结点时,其总结点数为2n-1
。
? 哈夫曼树存储结构:
? | weight | parent | lchild | rchild |
? 权重 双亲 左孩子 右孩子
? 叶子结点的左孩子和右孩子均为空。
? 哈夫曼树的应用:
? 哈夫曼编码:前缀编码,前缀编码容易区分,不易相重;缩短编码长度,便于传输 常用于压缩文件编码
原文链接:https://www.cnblogs.com/cqy-wt1124/p/12819472.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:图
- 二叉搜索树_BST 2020-05-30
- 二叉排序树 2020-05-02
- 二叉堆(3)SkewHeap 2020-02-20
- 二叉堆(2)LeftistHeap 2020-02-19
- 二叉树(5)HuffmanTree 2020-02-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash