数据结构(七)二叉树

定义

特点

特殊的二叉树

斜树

顾名思义,其中的结点都只有一个,又分为左斜树和右斜树,这时候又有疑惑了,这种数据结构不是有线性表一样吗,没错,线性表是一种特殊的树

满二叉树

完全二叉树

这个定义有点绕,简单来说就是所有的结点必须是有顺序的,不能跳跃存在

二叉树的性质

1.在二叉树的第i层至多有2的(i-1)次方个结点,参考满二叉树

2.深度游k的二叉树至多有2的k次方-1个结点,参考满二叉树

3.任意二叉树,终端结点为n0,度为2的结点为n2,度为1的结点为n1,则n0=n2+1

下面是推倒过程,设连接线为x,总结点数为n,则:

n=n0+n1+n2

x=n1+2n2

x=n-1

求得n0=n2+1

存储结构

二叉树的顺序结构

这有点像广度优先遍历,但这里关注的是存储结构,不是遍历方式,顺序结构一般只用于满二叉树,普通二叉树会有空间浪费,例如(^表示空)

二叉链表

一个数据域,两个指针域分别表示左孩子和右孩子

二叉树的遍历

前序遍历

中序遍历

后序遍历

层序遍历

这四种遍历名称都是针对每一个根结点而言,

前序:先遍历根节点(深度优先遍历)

中序:中间遍历根节点

后序:最后遍历根节点

层序:从根节点一层一层往下遍历(广度优先遍历)

线索二叉树

定义

指向前驱和后继的指针称为线索,加上线索的二叉链表称为线索二叉链表,相应的二叉树就成为思安所二叉树

还需要证明前驱后后继是否为孩子,所以加入了两个标志位,单个结点的结构如下

场景

赫夫曼树及其应用

定义及原理

从树中一个结点到另一个结点之间的分支构成两个结点之间的路径,路径上的分支数目称做路径的长度

例如这两个二叉树

二叉树a中,从根结点到D结点的路径为4,二叉树b中,从根结点到D结点的路径为2

二叉树a的树路径长度为1+1+2+2+3+3+4+4=20

二叉树b的树路径长度为1+1+2+2+2+2+2+3+3=16

如果考虑带权路径,路径与权的乘积才是最终的路径长度

定义

也称为最优二叉树

如何构建赫夫曼树

如何构建赫夫曼树总结

赫夫曼树的应用-赫夫曼编码

定义

数据压缩的原理基于此

时间: 06-11

数据结构(七)二叉树的相关文章

数据结构:二叉树的链式存储

数据结构:二叉树的链式存储(C语言版) 1.写在前面 二叉树同样有两种存储方式,数组和链式存储,对于数组来说,我们利用二叉树的性质然后利用下标可以方便的找到一个节点的子节点和父节点. 二叉树的性质: 1.二叉树的第i层上至多有2i-1个节点 2.深度为K的二叉树至多有2k-1个节点 3.任何一个二叉树中度数为2的节点的个数必度数为0的节点数目少1. 说明:度数为0,为叶子节点. 4.具有n个节点的完全二叉树的深度为|_Log2N_|+1 5.若完全二叉树中的某节点编号为i,则若有左孩子编号为2i

数据结构之二叉树查找

数据结构之--二叉树查找 定义:它是一棵树,或者具有以下性质的树.  若它的左子树不空,则左子树上所有节点的值均小于它的根节点的值: 若它的右子树不空,则右子树上所有节点的值均大于它的根节点的值:  它的左.右子树也分别为二叉排序树: 图解: ?        ?    ?    ?    ?    ?? #include<stdio.h> #include<stdlib.h> typedef int Status; #define TRUE 1 #define FALSE 0 t

数据结构之二叉树遍历

二叉树的 二叉树节点的描述 public class BiTNode { char data; BiTNode lc,rc; } 下面我们分别用递归和非递归实现前.中.后序遍历,以及使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队. 1.前序遍历 未完待续... 数据结构之二叉树遍历,布布扣,bubuko.com

【算法与数据结构】二叉树 中序线索

中序线索二叉树 /************************************************************************ 线索二叉树 二叉树的节点有五部分构造 ----------------------------------------- | lChild | lTag | value | rTag | rChild | ----------------------------------------- lChild = (lTag == 0 ? 左

浅谈数据结构之二叉树存储结构实现(七)

树:是n个结点的有限集:n=0时称为空树.在任意一棵非空树中,有且只有一个特定的结点称为根结点:其余的结点可分为m(m>0)个互不相交的有限集,其中每一个有限集都是一棵子树.结点拥有的子树数称为结点的度:度为0的结点称为叶结点或者终端结点,度不为0的结点称为分支结点或者非终端结点:树的度就是树内各结点的度的最大值. 二叉树的特点有:(1).每个结点最多有两棵子树,所以二叉树不存在度大于2的结点(注意:不是只有两棵子树,而是最多有两棵子树,没有子树或者有一颗子树都是可以的);(2).左子树和右子树

数据结构-二叉树笔记

看完<数据结构与算法分析>(c描述)后对二叉树的一点总结 树的节点声明: 1 typedef int ElementType; 2 typedef struct TreeNode* Position; 3 typedef Position BiSearchTree; 4 5 struct TreeNode 6 { 7 ElementType Element; 8 Position Left,Right; 9 10 }; 二叉查找树的定义如下: 1.二叉查找树首先是一棵二叉树: 2.二叉查找树除

基本数据结构之二叉树

C语言实现二叉树的遍历 二叉树结点的定义 /* 先序,中序,后序的遍历时间复杂度为O(n),每个结点只访问一次. 层序的时间复杂度最差为O(n^2),当二叉树基本平衡时,时间复杂度为O(n) n为结点个数 */ typedef int tree_node_element; /** * @author 韦轩 * @time 2015/07/11 * @brief 二叉树的结点数据结构 * */ typedef struct binary_tree_node { binary_tree_node*

数据结构之 二叉树---求二叉树后序遍历和层次遍历(先建树,再遍历)

数据结构实验之求二叉树后序遍历和层次遍历 Time Limit: 1000MS Memory limit: 65536K 题目描述 已知一棵二叉树的前序遍历和中序遍历,求二叉树的后序遍历. 输入 输入数据有多组,第一行是一个整数t (t<1000),代表有t组测试数据.每组包括两个长度小于50 的字符串,第一个字符串表示二叉树的先序遍历序列,第二个字符串表示二叉树的中序遍历序列. 输出 每组第一行输出二叉树的后序遍历序列,第二行输出二叉树的层次遍历序列 示例输入 2 abdegcf dbgeaf

重温数据结构:二叉树的常见方法及三种遍历方式 Java 实现

读完本文你将了解到: 什么是二叉树 Binary Tree 两种特殊的二叉树 满二叉树 完全二叉树 满二叉树 和 完全二叉树 的对比图 二叉树的实现 用 递归节点实现法左右链表示法 表示一个二叉树节点 用 数组下标表示法 表示一个节点 二叉树的主要方法 二叉树的创建 二叉树的添加元素 二叉树的删除元素 二叉树的清空 获得二叉树的高度 获得二叉树的节点数 获得某个节点的父亲节点 二叉树的遍历 先序遍历 中序遍历 后序遍历 遍历小结 总结 树的分类有很多种,但基本都是 二叉树 的衍生,今天来学习下二

数据结构例程——二叉树的构造

本文是数据结构基础系列(6):树和二叉树中第13课时二叉树的构造的例程. 1.由先序序列和中序序列构造二叉树 定理:任何n(n≥0)个不同节点的二叉树,都可由它的中序序列和先序序列唯一地确定. 证明(数学归纳法) 基础:当n=0时,二叉树为空,结论正确. 假设:设节点数小于n的任何二叉树,都可以由其先序序列和中序序列唯一地确定. 归纳:已知某棵二叉树具有n(n>0)个不同节点,其先序序列是a0a1-an?1:中序序列是b0b1-bk?1bkbk+1-bn?1. 先序遍历"根-左-右&quo