《【北邮本科课程 数据结构】ds6》由会员分享，可在线阅读，更多相关《【北邮本科课程 数据结构】ds6（92页珍藏版）》请在金锄头文库上搜索。
1、第六章第六章 树和二叉树树和二叉树 6.1 树的定义和基本术语 6.2 二叉树及其存储结构 6.3 遍历二叉树 6.4 线索二叉树 6.5 赫夫曼树及其应用 6.6 树和森林 6.7 二叉树和树的应用示例 本章学习要点、习题与上机作业 数据结构-第六章 树和二叉树1 6.1 6.1 树的定义和基本术语树的定义和基本术语 树是一类重要的非线性数据结构，是以分支关系 定义的层次结构。 6.1.1 树的定义树的定义 树树是由n(n0)个结点组成的有限集合T，非空树满足： 1)有一个称之为根根(root)的结点。 2)当n1时，除根以外的其余结点被分成m(m0)个互不 相交的集合T1， T2， Tm，
2、其中每一个集合本身又 是一棵树，且称为根的子树子树。 数据结构-第六章 树和二叉树2 6.1.2 6.1.2 树的逻辑表示方法树的逻辑表示方法 数据结构-第六章 树和二叉树3 A B C D E F G H I J 1层 2层 3层 4层 特点特点 除根结点外， 每个结点都仅有一 个前趋(父)结点。 数据结构-第六章 树和二叉树4 树的其它表示方法树的其它表示方法 嵌套集合表示法（文氏图表示法）嵌套集合表示法（文氏图表示法） 凹入表表示法凹入表表示法 A B E F G J C D HI 广义表表示法广义表表示法A( B( E，F(J)，G )，C，D( H，I ) A B E F J G C
3、 D H I 6.1.3 6.1.3 基本术语基本术语 结点的度结点的度结点拥有的子树数目。 树的度树的度树的各结点度的最大值。 叶子叶子(终端终端)结点结点度为0的结点。 分支分支(非终端非终端)结点结点度不为0的结点。 内部结点内部结点除根结点之外的分支结点。 双亲与孩子双亲与孩子(父与子父与子)结点结点结点的子树的根称为该结点的 孩子；该结点称为孩子的双亲。 兄弟兄弟属于同一双亲的孩子。 堂兄弟堂兄弟 双亲在同一层的结点互为堂兄弟。 结点的祖先结点的祖先从根到该结点所经分支上的所有结点。 结点的子孙结点的子孙该结点为根的子树中的任一结点。 数据结构-第六章 树和二叉树5 结点的层次结点的
4、层次 表示该结点在树中的相对位置。根为第一层， 其它的结点依次下推；若某结点在第L层上，则其孩子在 第L+1层上。 树的深树的深(高高)度度 树中结点的最大层次。 有序树有序树 树中各结点的子树从左至右是有次序的，不能互 换。否则，称为无序树无序树。 路径长度路径长度 从树中某结点Ni出发，能够“自上而下地”通 过树中结点到达结点Nj，则称Ni到Nj存在一条路径，路径 长度等于这两个结点之间的分支数。 树的路径长度树的路径长度 从根到每个结点的路径长度之和。 森林森林 是m(m0)棵互不相交的树的集合。 数据结构-第六章 树和二叉树6 6.1.4 6.1.4 树的基本操作树的基本操作 1)构造
5、空树InitTree(空间浪费可能大，特例：单枝树。 数据结构-第六章 树和二叉树15 存储结点数据和左、右孩子在向量中的序号存储结点数据和左、右孩子在向量中的序号 0 1 2 3 4 data A B C D E lc 1 -1 3 -1 -1 rc 2 -1 -1 4 -1 #define MAX_SIZE 80/预定义最大结点数目 typedef struct TElemType data ; int lc,rc ; int parent ; TNode; typedef TNode SBiTreeMAX_SIZE ; A B C D E 0 12 3 4 bt SBiTree bt;
6、data lc rc 6.2.4.2 6.2.4.2 链式存储结构链式存储结构 二叉链表二叉链表 三叉链表三叉链表 /带双亲的二叉链表带双亲的二叉链表 数据结构-第六章 树和二叉树16 lchild data rchildlchild data parent rchild A B C D E A B C D E btbt 二叉链表的类型定义三叉链表的类型定义 数据结构-第六章 树和二叉树17 typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, * BiTree; typedef str
7、uct TriTNode TElemType data; struct TriTNode *lchild, *rchild, *parent; TriTNode, * TriTree; 6.3 6.3 遍历二叉树遍历二叉树 目的：非线性结构线性结构 6.3.1 概念概念 指按某条搜索路线走遍二叉树的每个结点，使得树中 每个结点都被访问一次，且仅被访问一次。 数据结构-第六章 树和二叉树18 二叉树每个结点有两个后继，则存在如何遍历即按什么样的 搜索路径进行遍历的问题。必须找到一种规律，将二叉树转换 为一种线性结构，然后进行遍历。 在实际应用中通常要在二叉树中查找具有某些特性的结点， 或是对二叉
8、树中的所有结点作某种处理，这就需要涉及二叉树 的遍历问题。 数据结构-第六章 树和二叉树19 6.3.2 典型的遍历方法典型的遍历方法TraverseBiTree(T, Visit() 先先(根)序遍历(DLR)：PreOrderTraverse (T, Visit() 中中(根)序遍历(LDR)：InOrderTraverse (T, Visit() 后后(根)序遍历(LRD)：PostOrderTraverse (T, Visit() 层层序遍历：LevelOrderTraverse (T, Visit() 上述逆序方式很少使用 D L R T 对“二叉树”而言，可以有三条搜索路径： 先上
9、后下的按层次遍历； 先左（子树）后右（子树）的遍历； 先右（子树）后左（子树）的遍历。 数据结构-第六章 树和二叉树20 A D B C D L R A D L R D L R B D C D L R 先序遍历序列：A B D C 先序遍历: 访问根结点、遍历左子树、遍历右子树 数据结构-第六章 树和二叉树21 A D B C L D R B L D R L D R A D C L D R 中序遍历序列：B D A C 中序遍历: 遍历左子树、访问根结点、遍历右子树 数据结构-第六章 树和二叉树22 A D B C L R D L R D L R D A D C L R D 后序遍历序列： D
10、 B C A 后序遍历: B 遍历左子树、遍历右子树、访问根结点 确定遍历结果的一种简单方法确定遍历结果的一种简单方法 先序遍历(DLR)：ABDEC 中序遍历(LDR)：DBEAC 后序遍历(LRD)：DEBCA 利用遍历结果确定二叉树利用遍历结果确定二叉树 先序序列+中序序列 中序序列+后序序列 先序序列+后序序列 先序序列: ABCDEFGH 中序序列: BDCEAFHG 数据结构-第六章 树和二叉树23 A B C D E A B F C G DEH 思考：层序思考：层序+ +先序先序/ /中序中序/ /后序后序 能否确定？如何做？能否确定？如何做？ D L R 数据结构-第六章 树和
11、二叉树24 6.3.3 二叉树遍历算法二叉树遍历算法 (存储结构为二叉链表) 约定：遍历要求对每个数据元素调用函数 VisitVisit。 6.3.3.1 先序遍历算法先序遍历算法 Status PreOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if ( Visit(T-data) ) if ( PreOrderTraverse(T-lchild, Visit) ) if ( PreOrderTraverse(T-rchild, Visit) ) return OK; return ERROR; else return
12、 OK; /PreOrderTraverse 递归算法递归算法 T D L R 数据结构-第六章 树和二叉树25 Status pre(BiTree T) if (T) printf(T-data); pre(T-lchild); pre(T-rchild); 主程序主程序 Pre( T ) 返回 返回 pre(T R); 返回 返回 pre(T R); A CB D T B printf(B); pre(T L); B T A printf(A); pre(T L); A T D printf(D); pre(T L); D T C printf(C); pre(T L); C 返回 T 左
13、是空返回 pre(T R); T 左是空返回 T 右是空返回 T 左是空返回 T 右是空返回 pre(T R); 先序序列：A B D C 数据结构-第六章 树和二叉树26 算法分析：算法分析： 时间复杂度 沿遍历路线访问每一个结点，对含n个结点 的二叉树，时间复杂度为O(n)。 空间复杂度 递归算法所需辅助空间为树的深度，最坏情 况下树的深度为h。空间复杂度O(h)。 数据结构-第六章 树和二叉树27 改进的递归算法改进的递归算法 Status PreOrderTraverse1(BiTree T) if (T) if ( visit(T-data) ) if (T-lchild) if (
14、 ! PreOrderTraverse1(T-lchild) ) return ERROR; if (T-rchild) if (! PreOrderTraverse1(T-rchild) ) return ERROR; return OK; else return ERROR; else return OK; /PreOrderTraverse1 目的：减少对空二叉树的递归调用。 数据结构-第六章 树和二叉树28 非递归算法非递归算法 Status PreOrderTraverse2(BiTree T) IniStack(S); p=T ; Push(S, NULL); while ( p
15、) if ( !visit(p-data) ) return ERROR; if ( p-rchild ) Push(S, p-rchild); if ( p-lchild ) p=p-lchild; else Pop(S, p); return OK; /PreOrderTraverse2 p1 p2 p3 T 数据结构-第六章 树和二叉树29 6.3.3.2 中序遍历算法中序遍历算法 Status InOrderTraverse(BiTree T, Status(* Visit)(TElemType e) if (T) if ( InOrderTraverse(T-lchild, Visit) ) if ( Visit(T-data) ) if ( InOrderTraverse(T-rchild,Visit) ) return OK; return ERROR; else return OK; /InOrderTraverse 递归算法递归算法 T D L R 数据结构-第六章 树和二叉树30 非递归算法一非递归算法一
