《数据结构实例教程（C语言版）：第6章 树和二叉树的结构分析与应用》由会员分享，可在线阅读，更多相关《数据结构实例教程（C语言版）：第6章 树和二叉树的结构分析与应用（40页珍藏版）》请在金锄头文库上搜索。
1、 数据结构实例教程（数据结构实例教程（C语言版）语言版）第第6 6章树和二叉树的结构分析与应用章树和二叉树的结构分析与应用 学习目标学习目标 了解树的定义及基本术语。 熟练掌握二叉树的性质、存储结构及二叉树的各种遍 历算法。 熟练掌握二叉树线索化的过程。 熟练掌握哈夫曼树的构造方法及哈夫曼树的编码。 掌握树的各种存储结构及特点，以及树和森林与二叉 树之间的转换方法。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.16.1树的概念树的概念 一、树形结构实例描述 树形结构是一类重要的非线性结构。树形结构是结点之间有分支，并具有层次关系的结构。 数据结构实例教程（数据结构实例教程（C语言
2、版）语言版）6.16.1树的概念树的概念 二、树的定义 树是n(n0)个结点的有限集T。结点之间存在特定的关系。ABCDEFIJGH根子树子树子树 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.16.1树的概念树的概念 三、树的基本术语 1、结点的度：树中的一个结点拥有的孩子数目。ABCDEFIJGH 结点A的度为3 。 2、叶子（终端结点）：度为零的结点。 叶子结点为C、E、I、J、G、H 。ABCDEFIJGH 3、孩子和双亲 ：某个结点的子树之根称为该结点的孩子， 该结点称为孩子的双亲或父亲。 结点F称为结点B的孩子 结点 B称为结点F的双亲 4、兄弟：同一双亲的孩子。 结点
3、I和结点J互称为兄弟 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.16.1树的概念树的概念 三、树的基本术语 5、结点的层数和树的高度:结点的层数从根起算，根的层数 为1。树中结点的最大层数称为树的高度或深度。 ABCEFIJGH树高度为4 6、森林：是m(m0)棵互不相交的树的集合 。 DE第一层第二层第三层第四层 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 一、二叉树形态实例描述 假设一个父亲最多只能有两个孩子，而且分左孩子和右孩子。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 二、二叉树的定义 1、 二
4、叉树是n(n0)个结点的有限集，它可以为空集(n=0)或由一个根结点及两棵互不相交的左子树和右子树组成 。 2、二叉树的五种基本形态如下： 空空 只有根只有根 只有左子树只有左子树 只有右子树只有右子树 左右子树都有左右子树都有 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 三、二叉树的性质 1、满二叉树定义：一棵深度为k有且仅有2K-1个结点的二叉树。 2、完全二叉树定义：允许最下一层上的结点都集中在该层最 左边的若干位置上，右侧可以缺少结点的二叉树。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 三、二叉树的性质 3、二叉
5、树的4个重要性质 二叉树第i层上的结点数目最多为2i-1。 ABDEFGC第三层最多有4个结点 深度为k的二叉树最多有2K-1个结点 。 深度为3，最多有7个结点 在任意一棵二叉树中，若叶子结点的个数为n0， 度为2的结点的个数为n2，则有n0=n2+1。具有n个结点的完全二叉树的深度为 log2n+1。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 1、顺序存储结构 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 1、顺序存储结构 完全二叉树的顺序存储结构 结点数量 数据结构实例教程
6、（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 1、顺序存储结构 一般二叉树的顺序存储结构 将一般二叉树添上一些“虚结点”，其中“虚结点”用“ ”表示，成为完全二叉树。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 2、链式存储结构一个父亲照顾两个孩子 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 2、链式存储结构 链式存储结构示意图 链式存储结构类型定义 typedef struct nodetypedef struct node char d
7、ata char data； struct node *lchild struct node *lchild，* *rchildrchild；/左右孩子左右孩子指针指针BTreeNodeBTreeNode； 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 3、构造二叉树的算法 该算法采用完全二叉树编号的方法，存储每个结点的地址，每个结点信息又是采用链式结构存储。算法设置一个一维数组q，用来存储每个结点的地址值 。二叉树建立算法源程序链接二叉树建立算法源程序链接程序运行后，输入1，A时，存储结构的形态如下： 数据结构实例教程（数据结构实例教程
8、（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 3、构造二叉树的算法 输入2，B时，存储结构的形态如下：输入3，C时，存储结构的形态如下： 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.26.2二叉树二叉树 四、二叉树的存储结构 3、构造二叉树的算法 输入6，D时，存储结构的形态如下： 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.36.3二叉树的遍历二叉树的遍历 一、先序遍历 1、先序遍历过程为访问根、遍历左子树、遍历右子树。 ABDEFGC 例：先序遍历结果：ABDECFG void preorder(BTreeNode *bt)void pre
9、order(BTreeNode *bt) if(bt!=NULL) if(bt!=NULL) printf(%c ,bt-data); printf(%c ,bt-data); preorder(bt-lchild); preorder(bt-lchild); preorder(bt-rchild); preorder(bt-rchild); 2、先序遍历递归算法如下： 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.36.3二叉树的遍历二叉树的遍历 二、中序遍历 1、中序遍历过程为遍历左子树、访问根、遍历右子树。 ABDEFGC 例：中序遍历结果：DBEAFCG void inor
10、der(BTreeNode void inorder(BTreeNode *bt)*bt) if(bt!=NULL) if(bt!=NULL) inorder(bt- inorder(bt-lchild);lchild); printf(%c ,bt- printf(%c ,bt-data);data); inorder(bt- inorder(bt-rchild); rchild); 2、中序遍历递归算法如下： 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.36.3二叉树的遍历二叉树的遍历 三、后序遍历 1、后序遍历过程为遍历左子树、遍历右子树、访问根 。 ABDEFGC 例：后
11、序遍历结果：DEBFGCA void postorder(BTreeNode void postorder(BTreeNode *bt)*bt) if(bt!=NULL) if(bt!=NULL) postorder(bt- postorder(bt-lchild);lchild); postorder(bt- postorder(bt-rchild);rchild); printf(%c ,bt- printf(%c ,bt-data);data); 2、后序遍历递归算法如下： 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.46.4线索二叉树线索二叉树 一、线索二叉树定义1、线索
12、二叉树定义：利用空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针。 2、线索链表中的结点结构（增加两个域） lchildltagdatartagrchild 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.46.4线索二叉树线索二叉树 一、线索二叉树定义3、线索二叉树结点类型定义如下： typedef struct nodetypedef struct node char data char data；/数据域数据域 int ltag,rtag; / int ltag,rtag; /标志域标志域 struct node *lchild struct node *lchil
13、d，* *rchildrchild；/左右孩子左右孩子指针指针BThrNodeBThrNode； 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.46.4线索二叉树线索二叉树 二、线索二叉树实现 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.46.4线索二叉树线索二叉树 二、线索二叉树实现例：查找某结点*p在中序线索二叉树中的后继结点。BThrNode *InorderSuccessor(BThrNode *p)BThrNode *InorderSuccessor(BThrNode *p) BThrNode *qBThrNode *q； if (p-rtag=1) /*p
14、 if (p-rtag=1) /*p的右子树为空的右子树为空 return p-rchild return p-rchild； /返回右线索所指的中序返回右线索所指的中序后继后继 else else q=p-rchild q=p-rchild； /从从* *p p的右孩子开始查找的右孩子开始查找 while(q-ltag=0) q=q-lchild while(q-ltag=0) q=q-lchild； /沿左链沿左链往下查找往下查找 return q return q； /当当q q的左子树为空时，它就是最左的左子树为空时，它就是最左下结点下结点 数据结构实例教程（数据结构实例教程（C语言版
15、）语言版）6.56.5树和森林树和森林 一、树、森林与二叉树的相互转换 1、树转换为二叉树过程 ABCDEFIJGHABECGDFJHI 将所有兄弟结点用线连接起来； 每个结点只保留与其长子的连线外，去掉该结点与其它孩子的连线； 将水平线顺时针旋转45度。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 一、树、森林与二叉树的相互转换 2、森林转换为二叉树过程 将每棵二叉树的根结点视为兄弟从左至右连在一起；其他按照树转换为二叉树的方法进行。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 一、树、森林与二叉树的相互转换 3
16、、二叉树转换为森林过程 ABECDGFHI 若结点x是双亲y的左孩子，则把x的右孩子，右孩子的右孩子，都与y用线连接起来； 去掉所有双亲到右孩子的连线。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 二、树的存储结构 1、双亲表示法/结点的类型定义如下：typedef struct DataType data；/结点数据 int parent； /双亲指针PTreeNode；/树的类型定义如下：typedef struct PTreeNode nodesMaxTreeSize; /MaxTreeSize为数组大小 int n； /结点总数 PTree； 数
17、据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 二、树的存储结构 1、双亲表示法ABCDEFIJGH树的建立算法源程序链接树的建立算法源程序链接 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 二、树的存储结构 2、孩子链表表示法类型定义如下：typedef struct Cnode /typedef struct Cnode /子链表结子链表结点点 int child int child； /孩子结点对应的孩子结点对应的序号序号 struct Cnode *next struct Cnode *next；CNodeCNod
18、e；typedef structtypedef struct DataType data DataType data；/存放树中结点存放树中结点数据数据 CNode *firstchild CNode *firstchild；/链表头指链表头指针针PTNodePTNode；typedef structtypedef struct PTNode PTNode nodesMaxTreeSizenodesMaxTreeSize； int n int n，rootroot； /n/n为结点为结点总数总数CTreeCTree； 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树
19、和森林 二、树的存储结构 2、孩子链表表示法ABCDEFIJGHCNode类型PTNode类型CTree类型 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 三、树和森林的遍历 1、树先序遍历过程 访问根结点；从左到右依次先序遍历根的各子树。 ABCDEFIJGH例：遍历结果为：ABEFCGHIDJ 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.56.5树和森林树和森林 三、树和森林的遍历 2、树后序遍历过程 从左到右依次后序遍历根的各子树;访问根结点。 ABCDEFIJGH例：遍历结果为：EFBGHICJDA 注：森林的遍历方法相当于依次遍历第
20、一棵树、第二棵树、注：森林的遍历方法相当于依次遍历第一棵树、第二棵树、第、第n棵树。棵树。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 一、哈夫曼树的定义 1、路径和路径长度：在一棵树中，从一个结点往下可以达到 的孩子或子孙结点之间的通路，称为路径。通路中分支的 数目称为路径长度。2、结点的权及带权路径长度：若将结点赋给一个某种含义的 数值，则这个数值称为该结点的权。结点带权路径长度为 从根结点到该结点之间的路径长度与该结点的权的乘积。ABDEFGCA到B到D构成路径，路径长度为2。D带权路径长度为2*3=6。3 数据结构实例教程（数据结
21、构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 一、哈夫曼树的定义 3、树的带权路径长度：树的带权路径长度规定为所有叶子结 点的带权路径长度之和，记为WPL。 第一棵树 WPL=8*2+2*2+4*3+15*3+21*2=119 第二棵树 WPL=8*2+2*3+4*2+15*3+21*2=117 第三棵树 WPL=8*3+2*4+4*4+15*2+21*1=99 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 一、哈夫曼树的定义 3、哈夫曼树(Huffman tree)：给定n个权值作为n个叶子结 点，构造一棵二
22、叉树，若带权路径长度达到最小，称这样 的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。例如：给定4个叶子结点a、b、c、d和e分别带权8、2、4、15和21。右图二叉树带权路径长度最小，为哈夫曼树。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 二、哈夫曼树的构造 1、哈夫曼树的构造过程 将权值W1,W2,Wn的结点构造成森林F=T1,T2,Tn。第二步：选择森林中两个权值最小的结点合并为新结点， 原有两个结点作为新结点的左右孩子，然后从森林中删除 这两个结点，新结点加入森林中。 第三步：重复第二步，直到森林中只剩下一个结
23、点为止。 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 二、哈夫曼树的构造 例如：给定4个叶子结点a、b、c、d和e分别带权8、2、4、15和21。 bcabcde8241521构造成森林：6246a14814d291529e502150构造结束 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 二、哈夫曼树编码 1、哈夫曼树的编码过程 将树中左分支和右分支分别标记为0和1。将从根到叶子的路径上的标记依次相连,作为该叶子所表示字符的编码。bcade00001111编码结果： a字符的编码:1
24、01 b字符的编码:1000 c字符的编码:1001 d字符的编码:11 e字符的编码:0 数据结构实例教程（数据结构实例教程（C语言版）语言版）6.66.6哈夫曼树及其应用哈夫曼树及其应用 三、哈夫曼树应用 例：已知存在哈夫曼树，利用编码知识得出100010111所代表 的字符串是什么？编码结果： a字符的编码:101 b字符的编码:1000 c字符的编码:1001 d字符的编码:11 e字符的编码:0解决办法： 由于编码的唯一性，得出100010111中的1000代表字符b， 100010111中的101代表字符a， 100010111中的11代表字符 d，最终得到的字符串为“ bad”。
