电子商务网站有哪些和网址,wordpress安装后只显示英文站,找人做辅助的网站,编程网站哪个好第五章 树
5.1 树的基本概念 树是n#xff08;n≥0#xff09;个结点的有限集合#xff0c;n 0时#xff0c;称为空树。 空树——结点数为0的树 非空树——①有且仅有一个根节点 ②没有后继的结点称为“叶子结点”#xff08;或终端结点#xff09; ③有后继的结…第五章 树
5.1 树的基本概念 树是nn≥0个结点的有限集合n 0时称为空树。 空树——结点数为0的树 非空树——①有且仅有一个根节点 ②没有后继的结点称为“叶子结点”或终端结点 ③有后继的结点称为“分支结点”或非终端结点 ④除了根节点外任何一个结点都有且仅有一个前驱结点可以有0个或多个后继结点 在任何一棵非空树中应满足 有且仅有一个特定的称为根的结点。 当n 1时其余结点可分为mm0个互不相交的有限集合T1T2…Tm其中每个集合本身又是一棵树并且称为根结点的子树。 结点的度树中一个结点的孩子个数称为该结点的度。各结点的度的最大值是树的度。 度大于0的结点称为分支结点度为0的结点称为叶子结点。 结点的层次深度从上往下数。 结点的高度从下往上数。 树的高度深度树中结点的层数。 有序树逻辑上看树中结点的各子树从左至右是有次序的不能互换。 无序树逻辑上看树中结点的各子树从左至右是无次序的可以互换。 树中两个结点之间的路径是由这两个结点之间所经过的结点序列构成的而路径长度是路径上所经过的边的个数。 森林森林是mm≥0棵互不相交的树的集合。
5.1.2 树的常考性质
结点数 总度数 1度为 m 的树、m 叉树的区别
度为m的树m叉树的区别任意结点的度≤m最多m个孩子任意结点的度≤m最多m个孩子至少有一个结点度m有m个孩子允许所有结点的度都m一定是非空树至少有m1个结点可以是空树
度为 m 的树第 i 层至多有**m(i−1)m^{(i-1)}m(i−1)个结点i≥1m 叉树第 i 层至多有m(i−1)m^{(i-1)}m(i−1)**个结点i≥1。 高度为 h 的 m 叉树至多有mh−1m−1\frac{m^h-1}{m-1}m−1mh−1个结点。等比数列求和 高度为 h 的 m 叉树至少有 h 个结点高度为 h、度为 m 的树至少有hm-1个结点。 具有 n 个结点的 m 叉树的最小高度为⌈logm[n(m−1)1]⌉⌈log_m[n(m-1)1]⌉⌈logm[n(m−1)1]⌉
5.2 二叉树
5.2.1. 二叉树的定义 二叉树是 nn≥0个结点的有限集合 ①或者为空二叉树即 n 0。 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成左子树和右子树又分别是一棵二叉树。 二叉树的特点 ①每个结点至多只有两棵子树。 ②左右子树不能颠倒二叉树是有序树。——注意区别度为2的有序树 二叉树的五种状态 ①空二叉树 ②只有左子树 ③只有右子树 ④只有根节点 ⑤左右子树都有 5.2.2 几个特殊的二叉树
1、满二叉树
一棵高度为h且含有2h−12^h-12h−1个结点的二叉树称为满二叉树即 树中的每层都含有最多的结点。
特点 满二叉树的叶子结点都集中在二叉树的最下一层 不存在度为1的结点除了叶子结点外的每个节点的度都为2。 可以对满二叉树按照层序编号约定编号从根节点编号为1起自上而下自左向右。这样每个结点对应一个编号对于编号为i的结点若有双亲则其双亲为⌊i/2⌋若有左孩子则其左孩子为2i若有右孩子则其右孩子为2i1. 2、完全二叉树
高度为h有n个结点的二叉树当且仅当每个节点都与高度为h的满二叉树中编号为1~n的结点一一对应时称为完全二叉树。
其有如下特点
若i≤⌊n/2⌋则结点i为分支节点否则为叶子结点。只有最后两层可能有叶子结点。最多只有一个度为1的结点且该结点只有左孩子。按照层序编号后一旦出现某结点编号为i为叶子结点或只有左孩子则编号大于i的结点均为叶子结点。若n为奇数则每个分支节点都有左右孩子若n为偶数则编号最大的分支结点n/2只有左孩子没有右孩子。其余分支节点左右孩子都有。 满二叉树一定是完全二叉树完全二叉树不一定是满二叉树。 3、二叉排序树
一棵二叉树或者是空二叉树或者是具有如下性质的二叉树 左子树上的所有结点的关键字均小于根节点的关键字 右子树上的所有结点的关键字均大于根节点的关键字 左子树和右子树又各自是一颗二叉排序树。 二叉排序树可用于元素的排序、搜索。 4、平衡二叉树——胖胖的、丰满的树
树上的任一结点的左子树和右子树的深度之差不超过1.——平衡二叉树能有更高的搜索效率 5.2.3 二叉树的常考性质 设非空二叉树中度为0、1和2的结点个数分别为n0n_0n0、n1n_1n1和n2n_2n2则n0n21n_0n_21n0n21(叶子结点比二分支结点多一个) 推导过程假设树中结点总数为nnn则 ①nn0n1n2nn_0n_1n_2nn0n1n2 ②nn12n21nn_12n_21nn12n21(树的结点数总度数1) 二叉树第i层至多有2i−12^{i-1}2i−1个结点i≥1m叉树第i层至多有mi−1m^{i-1}mi−1个结点i≥1 高度为h的二叉树至多有2h−12^h-12h−1个结点满二叉树高度为h的m叉树至多有mh−1m−1\frac{m^h-1}{m-1}m−1mh−1个结点 具有n个n≥0结点的完全二叉树的高度h为⌊log2(n1)⌋\lfloor log_2(n1)\rfloor⌊log2(n1)⌋或⌈log2n⌉1\lceil log_2n\rceil1⌈log2n⌉1 推导过程 [外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-SeCmIHEo-1678084181984) 对于完全二叉树可以由结点数nnn推出度为0、1和2的结点个数n0n_0n0、n1n_1n1和n2n_2n2。 完全二叉树最多只有一个度为1的结点即n10n_10n10或1n0n21→n0n2n_0n_21\rightarrow n_0n_2n0n21→n0n2一定是奇数 ①若完全二叉树有2k偶数个结点则必有n11,n0k,n2k−1n_11, n_0k, n_2k-1n11,n0k,n2k−1 ②若完全二叉树有2k-1奇数个结点则必有n10,n0k,n2k−1n_10, n_0k, n_2k-1n10,n0k,n2k−1
5.2.4 二叉树的存储结构
1、顺序存储 包含的结点个数有上限 顺序存储完全二叉树定义一个长度为 MaxSize 的数组 t按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。让第一个位置空缺保证数组下标和结点编号一致。 根据二叉树的性质完全二叉树和满二叉树采用顺序存储比较合适树中结点的序号可以唯一反映结点之间的逻辑关系这样既能最大程度上的节省空间又能根据数组元素的下标来确定结点在二叉树中的位置以及结点间的关系。 几个重要常考的基本操作
结点i的左孩子2i2i2i结点i的右孩子2i12i12i1结点i的父节点⌊i/2⌋\lfloor i/2\rfloor⌊i/2⌋结点i的层次⌈log2(i1)⌉\lceil log_2(i1)\rceil⌈log2(i1)⌉或⌊log2i⌉1\lfloor log_2i\rceil1⌊log2i⌉1
若完全二叉树中共有n个结点则
判断i是否有左孩子——2i≤n?判断i是否有右孩子——2i1≤n?判断i是否是叶子/分支结点——i⌊n/2⌋\lfloor n/2\rfloor⌊n/2⌋?
顺序存储的结构描述如下
#define MaxSize 100
// 二叉树的顺序存储
struct TreeNode {ElemType data; // 结点中的数据元素bool isEmpty; // 结点是否为空
};
TreeNode t[MaxSize]; // 定义一个长度为MaxSize的数组t按照从上到下从左到右的顺序依次存储完全二叉树的各个节点
for(int i0;iMaxSize;i){ //初始化时所有结点标记为空t[i].isEmptytrue;
}而对于一般的二叉树而言若使用顺序存储则只能添加一些并不存在的空结点让每个结点与二叉树上的结点相对照再存储到一维数组的相应分量中。这样存在着空间的浪费不建议使用顺序存储。因此二叉树的顺序存储结构只适合存储完全二叉树。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-8tQTyDUY-1678084181985)(数据结构.assets/8736594932a24c0c8ee236c756dc3513.png)]
2、链式存储
为了解决存储一般二叉树的空间浪费问题一般二叉树的存储使用链式存储结构。使用链表结点来存储二叉树中的各个结点。在二叉树中结点的结构通常包括若干数据域以及若干指针域。 二叉链表的存储结构如下 其结构描述如下
typedef struct BiTNode {ElemType data; //数据域struct BiTNode *lchild, *rchild; //左、右孩子指针
} BiTNode, *BiTree;【重要】在含有n个结点的二叉链表中含有n1个空链域。 二叉树的链式存储实现
struct ElemType{int value;
}
typedef struct BiTNode{ElemType data;//数据域struct BiTNode *lchild,*rchild;//左、右孩子指针
}BiTNode,*BiTree;
//定义一棵空树
BiTree root NULL;
//插入根节点
root(BiTree)malloc(sizeof(BiTNode));
root-data{1};
root-lchild NULL;
root-rchild NULL;
//插入新节点
BiTNode *p(BiTNode *)malloc(sizeof(BiTNode));
p-data{2};
p-lchild NULL;
p-rchild NULL;
root-lchild p;为了找到指定结点的父结点一般要从根节点开始遍历可在BiTNode中设置一个新的指针存储父结点来解决此问题。 Tips: 根据实际需求决定要不要加父结点指针 5.3 二叉树的遍历与线索二叉树 二叉树的遍历类似 先序遍历前缀表达式 中序遍历中缀表达式需添加界限符 后序遍历后缀表达式 5.3.1 二叉树的遍历
遍历 按照某种次序把所有结点都访问一遍
层次遍历基于树的层次特性确定的次序规则
先/中/后序遍历基于树的递归特性确定的次序规则
二叉树的递归特性①要么是个空二叉树 ②要么就是由”根节点左子树右子树“组成的二叉树
1、先序遍历PreOrder
先序遍历的操作过程如下
若二叉树为空则什么都不做否则
访问根节点先序遍历左子树先序遍历右子树
根左右NLR
对应的递归算法如下
void PreOrder(BiTree T) {if (T NULL) return;visit(T); //访问根节点PreOrder(T-lchild); //递归遍历左子树PreOrder(T-rchild); //递归遍历右子树
}2、中序遍历InOrder
中序遍历的操作过程如下
若二叉树为空则什么也不做否则 中序遍历左子树; 访问根结点; 中序遍历右子树。
左根右LNR
对应的递归算法如下
void InOrder(BiTree T) {if (T NULL) return;InOrder(T-lchild); //递归遍历左子树visit(T); //访问根节点InOrder(T-rchild); //递归遍历右子树
}3、后序遍历PostOrder
后序遍历的操作过程如下
若二叉树为空则什么也不做否则 后序遍历左子树; 后序遍历后子树; 访问根结点;
左右根LRN
对应的递归算法如下
void PostOrder(BiTree T) {if (T NULL) return;PostOrder(T-lchild);//递归遍历左子树PostOrder(T-rchild);//递归遍历右子树visit(T); //访问根节点
}三种遍历方法空间复杂度O(h)
4、层序遍历
按照层序来进行遍历如下图所示 算法思想①初始化一个辅助队列
②根结点入队
③若队列非空则队头结点出队访问该结点并将其左、右孩子插入队尾如果有的话
④重复③直至队列为空
其示例如下 //链式队列结点
typedef struct LinkNode{BiTNode * data; //存指针而不是结点struct LinkNode *next;
}LinkNode;typedef struct{LinkNode *front,*rear;//队头队尾
}LinkQueue;//层序遍历
void LevelOrder(BiTree T){LinkQueue Q;InitQueue (Q); //初始化辅助队列BiTree p;EnQueue(Q,T); //将根节点入队while(!IsEmpty(Q)){ //队列不空则循环DeQueue(Q,p); //队头结点出队visit(p); //访问出队结点if(p-lchild!NULL)EnQueue(Q,p-lchild); //左孩子入队if(p-rchild!NULL)EnQueue(Q,p-rchild); //右孩子入队}
}5、由遍历序列构造二叉树 一个前序遍历序列可能对应多种二叉树形态。同理一个后序遍历序列、一个中序遍历序列、一个层序遍历序列也可能对应多种二叉树形态。 即若只给出一棵二叉树的 前/中/后/层序遍历序列 中的一种不能唯一确定一棵二叉树。 由二叉树的遍历序列构造二叉树 前序中序遍历序列后序中序遍历序列层序中序遍历序列 由 前序中序遍历序列 构造二叉树由前序遍历的遍历顺序根节点、左子树、右子树可推出根节点由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。 由 后序中序遍历序列 构造二叉树由后序遍历的遍历顺序左子树、右子树、根节点可推出根节点由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。 由 层序中序遍历序列 构造二叉树由层序遍历的遍历顺序层级遍历可推出根节点由根节点在中序遍历序列中的位置即可推出左子树与右子树分别有哪些结点。
示例 Key: 找到树的根节点并根据中序序列划分左右子树再找到左右子树根节点 5.3.2 线索二叉树
用土办法找到中序前驱
思路从根节点出发重新进行一次中序遍历指针q记录当前访问的结点指针pre记录上一个被访问的结点 ①当qp时pre为前驱
②当prep时q为后继
缺点找前驱、后继很不方面遍历操作必须从根开始 线索二叉树是一种物理结构 1、线索二叉树的基本概念
传统的二叉链表只能体现一种父子关系 **不能直接得到结点在遍历中的前驱和后继。**而考虑到在含有n个结点的二叉树中**有n1个空指针。**考虑能否利用这些空指针来存放指向其前驱或后继的指针这样就可以更加方便地遍历二叉树。 故含n个结点的线索二叉树共有n1个线索 引入线索二叉树正是为了加快查找结点前驱和后继的速度。
线索二叉树的结点结构如下 规定
若无左子树则lchild指向其前驱节点ltag为1否则lchild指向左孩子ltag为0若无右子树则rchild指向其后继结点rtag为0否则rchild指向左孩子rtag为0
其存储结构描述如下
typedef struct ThreadNode {int data; // 数据域struct ThreadNode *lchild, *rchild; // 左右孩子指针int ltag, rtag; // 左右线索标志
} ThreadNode, *ThreadBiTree;以这种结点结构构成的二叉链表作为二叉树的存储结构称为二叉链表。其中指向结点前驱和后继的指针称为线索加上线索的二叉树称为线索二叉树。
2、中序线索二叉树的构造 二叉树的线索化是将二叉链表中的空指针改为指向前驱或者后继的线索。而前驱或后继的信息只有在遍历时才能够得到因此二叉树的线索化的本质就是遍历一次二叉树。
p的左指针 空p-lchild pre非空跳过 pre的右指针 空pre-rchildp非空跳过
以下是对上图所示二叉树进行中序线索化的一个示例过程 其代码实现如下
// 中序线索化二叉树
void InThread(ThreadBiTree p, ThreadBiTree pre) {if (p ! NULL) { // 若p非空结点没有全部遍历InThread(p-lchild, pre); // 递归调用if (p-lchild NULL) { // 若p的左孩子为空p-lchild pre; // p的左孩子指向前驱p-ltag 1; // 标记为线索}if (pre ! NULL pre-lchild NULL) { // pre存在且右孩子为空pre-lchild p; // pre的右孩子指向后继pre-rtag 1; // 标记为线索}pre p; // pre指向p的上一个位置InThread(p-rchild, pre); // 对右孩子建立线索}
}线索化后存储结构如下 4、先序和后序遍历
先序和后序遍历的方法类似中序遍历这里不再给出具体流程。
先序线索二叉树的存储
后序线索二叉树的存储 三种线索二叉树的对比 5、二叉树的线索化
1中序线索化代码实现
//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; //左、右线索标志
}ThreadNode,* ThreadTree;//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *preNULL;//中序遍历二叉树一边遍历一边线索化
void InThread(ThreadTree T){if(T!NULL){InThread(T-lchild); //中序遍历左子树visit(T);//访问根节点InThread(T-rchild); //中序遍历右子树}
}
void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre; q-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildq; //建立前驱结点的后继线索pre-rtag1;}preq;
}
//最后还要检查pre的rchild是否为NULL,如果是则令rtag1;2先序线索化代码实现
//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; //左、右线索标志
}ThreadNode,* ThreadTree;//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *preNULL;//中序遍历二叉树一边遍历一边线索化
void PreThread(ThreadTree T){if(T!NULL){visit(T);//访问根节点if(T-ltag0) //lchild不是前驱线索PreThread(T-lchild); PreThread(T-rchild); }
}
void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre; q-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildq; //建立前驱结点的后继线索pre-rtag1;}preq;
}
//最后还要检查pre的rchild是否为NULL,如果是则令rtag1;
void CreatePreThread(ThreadTree T){ThreadTree preNULL;if(T!NULL){ //非空二叉树线索化PreThread(T,pre); //线索化二叉树if(pre-rchildNULL) //处理遍历的最后一个结点pre-rtag1;}
}2后序线索化代码实现
//线索二叉树结点
typedef struct ThreadNode{ElemType data;struct ThreadNode *lchild,*rchild;int ltag,rtag; //左、右线索标志
}ThreadNode,* ThreadTree;//全局变量 pre, 指向当前访问结点的前驱
ThreadNode *preNULL;//中序遍历二叉树一边遍历一边线索化
void PostThread(ThreadTree T){if(T!NULL){PostThread(T-lchild); PostThread(T-rchild); visit(T);//访问根节点}
}
void visit(ThreadNode *q){if(q-lchildNULL){ //左子树为空建立前驱线索q-lchildpre; q-ltag1;}if(pre!NULLpre-rchildNULL){pre-rchildq; //建立前驱结点的后继线索pre-rtag1;}preq;
}void CreatePostThread(ThreadTree T){preNULL; //pre初始化为NULLif(T!NULL){ //非空二叉树线索化PostThread(T,pre); //线索化二叉树if(pre-rchildNULL) //处理遍历的最后一个结点pre-rtag1;}
}6、在线索二叉树中查找前驱、后继
中序线索二叉树找到指定结点 *p 的中序后继 next
若p-rtag1则next p-rchild若p-rtag0则 next 为 p 的右子树中最左下结点。
中序线索二叉树找到指定结点 *p 的中序前驱 pre
若p-ltag1则pre p-lchild若p-ltag0则 next 为 p 的左子树中最右下结点。
先序线索二叉树找到指定结点 * p 的先序后继 next
若p-rtag1则next p-rchild若p-rtag1则next p-rchild 若 p 有左孩子则先序后继为左孩子若 p 没有左孩子则先序后继为右孩子。
先序线索二叉树找到指定结点 *p 的先序前驱 pre
前提改用三叉链表可以找到结点 * p 的父节点。如果能找到 p 的父节点且 p 是左孩子p 的父节点即为其前驱如果能找到 p 的父节点且 p 是右孩子其左兄弟为空p 的父节点即为其前驱如果能找到 p 的父节点且 p 是右孩子其左兄弟非空p 的前驱为左兄弟子树中最后一个被先序遍历的结点如果 p 是根节点则 p 没有先序前驱。 先序遍历中每个子树的根节点是最先遍历到的若根节点有左右孩子则其左右指针都指向了孩子这种情况下没有办法直接找到子树根节点的前驱。 后序线索二叉树找到指定结点 *p 的后序前驱 pre
若p-ltag1则pre p-lchild;若p-ltag0 若 p 有右孩子则后序前驱为右孩子若 p 没有右孩子则后续前驱为右孩子。
后序线索二叉树找到指定结点 *p 的后序后继 next
前提改用三叉链表可以找到结点 * p 的父节点。如果能找到 p 的父节点且 p 是右孩子p 的父节点即为其后继如果能找到 p 的父节点且 p 是左孩子其右兄弟为空p 的父节点即为其后继如果能找到 p 的父节点且 p 是左孩子其右兄弟非空p 的后继为右兄弟子树中第一个被后序遍历的结点如果 p 是根节点则 p 没有后序后继。 后序遍历中每个子树的根节点是最后遍历到的若根节点有左右孩子则其左右指针都指向了孩子这种情况下没有办法直接找到子树根节点的后继。 【考点】二叉树线索化之后仍不能有效求解的问题 查找后序线索二叉树的后续后继查找先序线索二叉树的先序前驱 5.4 树和森林
5.4.1 树的存储结构
1、双亲表示法顺序存储
采用一组连续空间来存储每个节点同时在每个节点中设置一个伪指针指示其双亲结点在数组中的位置。 根结点固定存储在0号位置-1表示其没有双亲。新增数据元素无需按逻辑上的次序存储树的顺序存储结构中数组下标只代表结点的编号不表示各个结点间的关系。 优点查指定结点的双亲很方便 缺点查定结点的孩子只能从头遍历空数据导致遍历更慢 2、孩子表示法顺序链式存储 孩子表示法中每个结点的孩子都使用了单链表链接起来形成一个线性结构这时n个结点就有n个孩子链表叶结点的孩子链表为空表。 这种存储方式寻找子女的操作非常直接而寻找双亲的操作需要遍历n个结点中孩子链表指针域所指向的n个孩子链表。 3、孩子兄弟表示法链式存储【重要】
孩子兄弟表示法又称二叉树表示法即以二叉链表作为树的存储结构。孩子兄弟表示法使每个结点包括三部分内容:结点值、指向结点第一个孩子结点的指针及指向结点下一个兄弟结点的指针沿此域可以找到结点的所有兄弟结点)。
这种存储表示法比较灵活其最大的优点是可以方便地实现树转换为二叉树的操作易于查找结点的孩子等,但缺点是从当前结点查找其双亲结点比较麻烦。若为每个结点增设一个parent域指向其父结点则查找结点的父结点也很方便。 5.4.2 树、森林和二叉树的转换
1、树和二叉树的转化
树转换二叉树的原则每个结点的左指针指向它的第一个孩子右指针指向它在树中的相邻右兄弟。 记忆”左孩子右兄弟“ 由于根节点没有兄弟所以树转化成的二叉树没有右子树。 2、森林和二叉树的转化
森林是m (m≥0棵互不相交的树的集合。
将森林转化成二叉树先将森林中的每棵树转换为二叉树由于任何一棵和树对应的二叉树的右子树必空若把森林中第二棵树根视为第一棵树根的右兄弟即将第二棵树对应的二叉树当作第一棵二叉树根的右子树将第三棵树对应的二叉树当作第二棵二叉树根的右子树以此类推就可以将森林转换为二叉树。 将二叉树转化成森林 5.4.3 树和森林的遍历
1、树的遍历 先根遍历。若树非空先访问根结点再依次遍历根结点的每棵子树遍历子树时仍遵循先根后子树的规则。 树的先根遍历序列与这棵树相应二叉树的先序序列相同。 //树的先根遍历
void PreOrder(TreeNode *R){if(R!NULL){visit(R); //访问根结点while(R还有下一个子树T)PreOrder(T); //先根遍历下一棵子树}
}后根遍历。若树非空先依次遍历根结点的每棵子树再访问根结点遍历子树时仍遵循先子树后根的规则。 树的后根遍历序列与这棵树相应二叉树的中序序列相同。 //树的后根遍历
void PostOrder(TreeNode *R){if(R!NULL){while(R还有下一个子树T)PostOrder(T); //后根遍历下一棵子树visit(R); //访问根结点}
}先根遍历、后根遍历——深度优先遍历 层次遍历用队列实现——广度优先遍历。 ①若树非空则根结点入队 ②若队列非空队头元素出队并访问同时将该元素的孩子依次入队 ③重复②直到队列为空
2、森林的遍历
先序遍历森林。若森林为非空则按如下规则进行遍历: 访问森林中第一棵树的根结点。先序遍历第一棵树中根结点的子树森林。先序遍历除去第一棵树之后剩余的树构成的森林。 效果等同于对各个树依次进行先根遍历也等同于对对应二叉树进行先序遍历 中序遍历森林。森林为非空时按如下规则进行遍历: 中序遍历森林中第一棵树的根结点的子树森林。 访问第一棵树的根结点. 中序遍历除去第一棵树之后剩余的树构成的森林。 效果等同于依次对各个树进行后根遍历也等同于对对应二叉树进行中序遍历 树和森林的遍历与二叉树遍历的关系
树森林二叉树先根遍历先序遍历先序遍历后根遍历中序遍历中序遍历
5.5 树和二叉树的应用
5.5.1 二叉排序树
二叉排序树又称二叉查找树BST, Binary Search Tree一棵二叉树或者是空二叉树或者是具有如下性质的二叉树 左子树上的所有结点的关键字均小于根节点的关键字 右子树上的所有结点的关键字均大于根节点的关键字 左子树和右子树又各自是一颗二叉排序树。 左子树结点值根结点值右子树结点值 进行中序遍历可以得到一个递增的有序序列
**用途**二叉排序树可用于元素的有序组织、搜索
二叉排序树的查找操作 递归实现查找 二叉排序树的插入操作 二叉排序树的构造 二叉排序树的删除操作
①若被删除结点z是叶结点则直接删除不会破坏二叉排序树的性质。
②若结点z只有一棵左子树或右子树则让z的子树成为z父结点的子树替代z的位置
③若结点z有左、右两棵子树则令z的直接后继或直接前驱替代z然后从二叉排序树中删去这个直接后继或直接前驱这样就转换成了第一或第二种情况。z的后继z的右子树中最左下结点该结点一定没有左子树z的前驱z的左子树中最右下结点该结点一定没有右子树
查找效率分析
查找长度——在查找运算中需要对比关键字的次数称为查找长度反映了查找操作时间复杂度。 最好情况n个结点的二叉树最小高度为⌊log2n⌋1\lfloor log_2n\rfloor 1⌊log2n⌋1. 平均查找长度 O(log2nlog_2nlog2n) 最坏情况每个结点只有一个分支树高h结点数n. 平均查找长度O(nnn) 查找成功的平均查找长度ASLAverage Search Length 查找失败的平均查找长度ASLAverage Search Length 5.5.2 平衡二叉树AVL
平衡二叉树Balanced Binary Tree简称平衡树AVL树——树上的任一结点的左子树和右子树的深度之差不超过1.
结点的平衡因子左子树高-右子树高 平衡二叉树结点的平衡因子的值只可能是-1、0或1 只要有任一结点的平衡因子绝对值大于1就不是平衡二叉树 定义平衡二叉树结点代码
typedef struct AVLNode{int key; //数据域int balance; //平衡因子struct AVLBNode *lchild,*rchild;
}AVLNode,*AVLTree;平衡二叉树的插入
在二叉排序树中插入新结点后如何保持平衡——从插入点往回找到第一个不平衡结点调整以该结点为根的子树
每次调整的对象都是”最小不平衡子树“
5.5.3 哈夫曼树和哈夫曼编码
1、哈夫曼树的定义
结点的权有某种现实含义的数值如:表示结点的重要性等)
结点的带权路径长度从树的根到该结点的路径长度(经过的边数)与该结点上权值的乘积
树的带权路径长度树中所有叶结点的带权路径长度之和(WPL, Weighted Path Length) WPL∑i1nwiliWPL\sum_{i1}^nw_il_i WPLi1∑nwili 在含有n个带权叶结点的二叉树中其中带权路径长度(WPL)最小的二叉树称为哈夫曼树也称最优二叉树。 哈夫曼树不是唯一的 2、构造哈夫曼树
给定n个权值分别为wl, w2,…, wn的结点构造哈夫曼树的算法描述如下:
将这n个结点分别作为n棵仅含一个结点的二叉树构成森林F。构造一个新结点从F中选取两棵根结点权值最小的树作为新结点的左、右子树并且将新结点的权值置为左、右子树上根结点的权值之和。从F中删除刚才选出的两棵树同时将新得到的树加入F中。重复步骤2和3直至F中只剩下一棵树为止。 构造哈夫曼树的注意事项
每个初始结点最终都成为叶结点且权值越小的结点到根结点的路径长度越大。哈夫曼树的结点总数为 2n−1。哈夫曼树中不存在度为 1 的结点。哈夫曼树并不唯一但 WPL 必然相同且为最优。 3、哈夫曼编码
将字符频次作为字符结点权值构造哈夫曼树即可得哈夫曼编码可用于数据压缩 前缀编码没有一个编码是另一个编码的前缀 固定长度编码每个字符用相等长度的二进制位表示 可变长度编码允许对不同字符用不等长的二进制位表示
