《数据结构讲义树和二叉树幻灯片.ppt》由会员分享，可在线阅读，更多相关《数据结构讲义树和二叉树幻灯片.ppt（106页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、数据结构讲义树和二叉树第1页，共106页，编辑于2022年，星期六6.1 树的定义和基本术语1、树的定义 树是由 n(n 0)个结点组成的有限集合。如果n=0，称为空树；否则，在一棵非空树中，满足如下两个条件：（1）有一个特定的称之为根(root)的结点，它只有直 接后继，但没有直接前驱；（2）除根以外的其它结点划分为 m(m 0)个互不相 交的有限集合 T0,T1,Tm-1，每个集合又是一棵树，并且称之为根的子树(subTree)。ABCDGFEHIJKLM第2页，共106页，编辑于2022年，星期六2、树的表示（1）树型表示（直观表示法）6.1 树的定义和基本术语ABCDGFEHIJKLM
2、第3页，共106页，编辑于2022年，星期六2、树的表示（1）树型表示（直观表示法）（2）二元组表示T=(D,R)D=A,B,C,D,E,F,G,H,I,J,K,L,MR=,6.1 树的定义和基本术语ABCDGFEHIJKLM第4页，共106页，编辑于2022年，星期六2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法 6.1 树的定义和基本术语ABCDGFEHIJKLMABEKLFCGDHMJI第5页，共106页，编辑于2022年，星期六2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示6.1 树的定义和基本术语ABCDGFEHIJKLM
3、AEDHJIKLMDGC第6页，共106页，编辑于2022年，星期六2、树的表示（1）树型表示（直观表示法）（2）二元组表示（3）凹入法（4）嵌套集合表示（5）广义表表示（嵌套括号表示）6.1 树的定义和基本术语ABCDGFEHIJKLM（A（B（E（K,L）,F）,C（G）,D（H（M）,I,J）第7页，共106页，编辑于2022年，星期六3、基本术语结点（结点（nodenode）：包含一个数据元素及若干指向其它结点的：包含一个数据元素及若干指向其它结点的分支信息。分支信息。结点的度结点的度(degree)(degree)：结点的子树个数：结点的子树个数叶结点叶结点(leaf)(leaf)：
4、度：度为为0的结点，也称为终端结点。的结点，也称为终端结点。分支结点分支结点(branch)(branch)：度：度不为不为0的结点，也称为非终端结点。的结点，也称为非终端结点。孩子结点孩子结点(child)(child)：一个结点的直接后继或某结点子树的：一个结点的直接后继或某结点子树的根结点根结点。双亲结点双亲结点(parent)(parent)：一个结点的直接前驱或某个结点是其：一个结点的直接前驱或某个结点是其子树之根的子树之根的 双亲双亲。6.1 树的定义和基本术语ABCDGFEHIJKLM第8页，共106页，编辑于2022年，星期六3、基本术语兄弟(sibling)结点:具有同一双亲
5、的所有结点 祖先(ancestor)结点:若树中结点k到ks存在一条路径，则称 k是ks的祖先 子孙(descendant)结点:若树中结点k到ks存在一条路径，则称ks是k的子孙 结点所处层次(level):根结点的层数为1，其余结点的层，其余结点的层 数为双亲结点的层数加 1 树的高度(depth):树中结点的最大层数 树的度(degree):树中结点的最大度数 6.1 树的定义和基本术语ABCDGFEHIJKLM第9页，共106页，编辑于2022年，星期六3、基本术语有序树 子树的次序不能互换无序树 子树的次序可以互换森林（Forest）互不相交的树的集合 6.1 树的定义和基本术语AB
6、CDGFEHIJKLM第10页，共106页，编辑于2022年，星期六4、树的基本操作初始化求指定结点所在树的根结点求指定结点的双亲结点求指定结点的某一孩子结点求指定结点的最右边兄弟结点将一棵树插入到另一树的指定结点下作为它的子树 删除指定结点的某一子树 树的遍历6.1 树的定义和基本术语第11页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.1 二叉树的定义1、二叉树（Binary Tree）或为空树，或由根及两棵不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明说明1）二叉树中每个结点最多有两棵子树；二叉树每个结点度小于等于2;2）左、右子树
7、不能颠倒有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;A A F F G G E E D D C C B B第12页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.1 二叉树的定义2、二叉树的五种不同形态二叉树的五种不同形态第13页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.1 二叉树的定义3、二叉树和树的区别：二叉树不是树的特殊情形，它们是两个概念。树和二叉树之间最主要的差别是：二叉树中结点的子树要区分为左子树和右子树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。第1
8、4页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.2 二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点(i1)性质2：深度为k的二叉树最多有2k-1个结点。(k1)性质3：对任何一棵二叉树,如果其叶结点个数为n0,度为2的非叶结点个数为n2,则有n0n21。第15页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.2 二叉树的性质两种特殊的二叉树：两种特殊的二叉树：满二叉树满二叉树：深度为：深度为k且有且有2k-1个结点的二叉树。个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具在满二叉树中，每层
9、结点都是满的，即每层结点都具有最大结点数。有最大结点数。12345678910111213 1415满二叉树满二叉树第16页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.2 二叉树的性质两种特殊的二叉树：两种特殊的二叉树：完全二叉树完全二叉树：若设二叉树的高度为h，除第 h层外，其它各层的结点数都达到最大个数，第h层的结点集中出现在左端若干连续位置上，这就是完全二叉树。完全二叉树完全二叉树12345678910111213 14关系关系：满二叉树：满二叉树必为必为完全二叉树，而完全二叉树完全二叉树，而完全二叉树不一定不一定是满二叉树。是满二叉树。第17页
10、，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.2 二叉树的性质两种特殊的二叉树：两种特殊的二叉树：完全二叉树举例：完全二叉树举例：12345612345712367(a)完全二叉树(b)非完全二叉树(c)非完全二叉树第18页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.2 二叉树的性质性质4：具有n个结点的完全二叉树的深度为log2n+1 证明：设完全二叉树的高度为深度为h，则有2h-1-1 n2h-1 2h-1=n 2h 取对数h 1=log2(n)1，则序号为i的结点的双亲结点序号为i/2。（2）如2in，则序
11、号为i的结点无左孩子；如2in，则序号为i的结点的左孩子结点的序号为2i。（3）如2i1n，则序号为i的结点无右孩子；如2i1n，则序号为i的结点的右孩子结点的序号为2i1。第20页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.3 二叉树的存储结构1、顺序存储结构#define MAXNODE 100#define MAXNODE 100typedef elemtype SqBiTreeMAXNODEtypedef elemtype SqBiTreeMAXNODESqBiTree bt;SqBiTree bt;ABCDEFGHIJKLA B C D E
12、F G H I J K L二叉树的顺序存储结构二叉树的顺序存储结构11109876543210第21页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.3 二叉树的存储结构1、顺序存储结构 ACBEDFG A B C D E F GABDCEFG(a)一般的二叉树(b)改造后的完全二叉树第22页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.3 二叉树的存储结构1、顺序存储结构 ABCDA B C D单支树单支树顺序存储结构仅适用于完全二叉树2n-1第23页，共106页，编辑于2022年，星期六6.2 二叉树(Binar
13、y Tree)6.2.3 二叉树的存储结构2、链式存储结构（1）二叉链表：二叉链表中每个结点包含三个域：数据域、左指针域、右指针域lchilddatarchildtypedef struct node ElemType data;struct node*lchild;struct node*rchild;BiTNode,*BiTree;第24页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.3 二叉树的存储结构2、链式存储结构（1）二叉链表：EADCGFBBDFACEG 二叉树的二叉链表表示第25页，共106页，编辑于2022年，星期六6.2 二叉树(Bi
14、nary Tree)6.2.3 二叉树的存储结构2、链式存储结构（2）三叉链表：三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域 BDEADFABDFEC第26页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.3 二叉树的存储结构2、链式存储结构示例第27页，共106页，编辑于2022年，星期六6.2 二叉树(Binary Tree)6.2.4 二叉树的基本操作创建二叉树 二叉树的遍历第28页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树（traversing binary tree）一、遍历
15、二叉树的定义：1、先序遍历（D L R）若二叉树为空，则空操作；否则：（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树；A A F F G G E E D D C C B B先序遍历序列：A,B,D,E,G,C,F第29页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树（traversing binary tree）一、遍历二叉树的定义：2、中序遍历（L D R）若二叉树为空，则空操作；否则：（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树；A A F F G G E E D D C C B B中序遍历序列：D,B,G,E,A,
16、C,F第30页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树（traversing binary tree）一、遍历二叉树的定义：3、后序遍历（L R D）若二叉树为空，则空操作；否则：（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点；A A F F G G E E D D C C B B后序遍历序列：D,G,E,B,F,C,A第31页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树例：先序遍历、中序遍历、后序遍历下图所示的表达式语法树 后序遍历序列（后缀表达式）：a b c d-*+e f/-a
17、 b c d-*+e f/-中序遍历序列（中缀表达式）：a+b*c a+b*c d d e/f e/f 先序遍历序列（前缀表达式）：-+a*b-+a*b c d/e f c d/e f第32页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 二、遍历二叉树的递归算法 数据结构定义：typedef int ElemTypetypedef int ElemTypetypedef struct node typedef struct node ElemType data;ElemType data;struct node*lchild;struct node
18、*lchild;struct node*rchild;struct node*rchild;BiTNode,*BiTree BiTNode,*BiTree;第33页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 二、遍历二叉树的递归算法 1、先序遍历PreOrderTranverse(BiTreeT)if(T)printf(“%d”,T-data);/访问的方式有多种PreOrderTranverse(T-LChild);PreOrderTranverse(T-RChild);第34页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉
19、树6.3.1 遍历二叉树 二、遍历二叉树的递归算法 2、中序遍历InOrderTranverse(BiTreeT)if(T)InOrderTranverse(T-LChild);printf(“%d”,T-data);/访问的方式有多种InOrderTranverse(T-RChild);第35页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 二、遍历二叉树的递归算法 3、后序遍历PostOrderTranverse(BiTreeT)if(T)PostOrderTranverse(T-LChild);PostOrderTranverse(T-RChi
20、ld);printf(“%d”,T-data);/访问的方式有多种第36页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 三、遍历二叉树的非递归算法 遍历的递归执行过程：*AGBCDEF第37页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 三、遍历二叉树的非递归算法（一）基于栈的递归消除1、中序遍历的非递归算法第38页，共106页，编辑于2022年，星期六void InOrder（BiTree T）InitStack(S);push(S,T);while(!StackEmpty(S)if(Getop(S,
21、p)&p!=NULL)/向左走到尽头 push(S,p-lchild;pop(S,p);/空指针退栈 if(!StackEmpty(S)/访问结点，向右一步 pop(S,p);visit(p-data);p=p-rchild;6.3 遍历二叉树和线索二叉树第39页，共106页，编辑于2022年，星期六void InOrder（BiTree T）InitStack(S);p=T;while(p!=NULL|!StackEmpty(S)if(p!=NULL)/*根指针进栈，遍历左子树*/push(S,p);p=p-lchild;else/*根指针退栈，访问根结点，遍历右子树*/pop(S,p);v
22、isit(p-data);p=p-rchild;6.3 遍历二叉树和线索二叉树第40页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 三、遍历二叉树的非递归算法（一）基于栈的递归消除1、中序遍历的非递归算法2、先序遍历的非递归算法第41页，共106页，编辑于2022年，星期六void PreOrder（BiTree T）InitStack(S);p=T;while(p!=NULL|!StackEmpty(S)if(p!=NULL)/*根指针进栈，遍历左子树*/visit(p-data);push(S,p);p=p-lchild;else/*根指针退栈
23、，访问根结点，遍历右子树*/pop(S,p);p=p-RChild;6.3 遍历二叉树和线索二叉树第42页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 三、遍历二叉树的非递归算法（一）基于栈的递归消除1、中序遍历的非递归算法2、先序遍历的非递归算法3、后序遍历的非递归算法第43页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树typedef struct BiTree link;int flag;stacktype;void PostOrder（BiTree T）stacktype stackMAXNODE;BiTree p;i
24、nt top,sign;if(T=NULL)return;top=-1;/*栈顶位置初始化*/p=T;while(!(p=NULL&top=-1)if(p!=NULL)/*结点第一次进栈*/top+;stacktop.link=p;stacktop.flag=1;p=p-lchild;else p=stacktop.link;sign=stacktop.flag;top-;if(sign=1)/结点第二次进栈 top+;stacktop.link=p;stacktop.flag=2;/标记第二次出栈*/p=p-rchild;else visit(p-data);p=NULL;第44页，共106
25、页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 三、遍历二叉树的非递归算法（一）基于栈的递归消除1、中序遍历的非递归算法2、先序遍历的非递归算法3、后序遍历的非递归算法（二）不用栈的二叉树遍历的非递归方法 1、对二叉树采用三叉链表存放2、采用逆转链的方法3、在线索二叉树上的遍历 第45页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 四、层次遍历二叉树二叉树的层次遍历，是指从二叉树的第一层（根结点）开始，从上至下逐层遍历，在同一层中，则按从左到右的顺序对结点逐个访问。例：层次遍历序列为 ABCDEFG A A F F
26、 G G E E D D C C B B第46页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.1 遍历二叉树 四、层次遍历二叉树算法voidLevelOrder（BiTreebt）/*层次遍历二叉树bt*/BiTreeQueueMAXNODE;intfront,rear;if(bt=NULL)return;front=-1;rear=0;queuerear=bt;while(front!=rear)front+;p=queuefront;Visit(p-data);if(p-lchild!=NULL)/*队首结点的左孩子入队*/rear+;queuerear=p-
27、lchild;if(p-rchild!=NULL)/*队首结点的右孩子入队*/rear+;queuerear=p-rchild;第47页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用1输出二叉树中的结点输出二叉树中的结点 输出二叉树中结点并无次序要求，因此可用任一种算法来完成。void PreOrder(BiTree root)void PreOrder(BiTree root)/*/*先序遍历输出二叉树结点先序遍历输出二叉树结点*/*/if(root!=NULL)if(root!=NULL)printf(root-data);/*printf(
28、root-data);/*输出根结点输出根结点*/*/PreOrder(root-LChild);/*PreOrder(root-LChild);/*先序遍历左子树先序遍历左子树*/*/PreOrder(root-RChild);/*PreOrder(root-RChild);/*先序遍历右子树先序遍历右子树*/*/问题思考：问题思考：若要求统计二叉树中结点个数应如何去实现？若要求统计二叉树中结点个数应如何去实现？第48页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用 2.统计叶子结点数目统计叶子结点数目方法方法1 1：/*LeafCount/*
29、LeafCount保存叶子保存叶子结点数目的全局点数目的全局变量量,调用之前初始化用之前初始化值为0*/0*/Int LeafCount=0;Int LeafCount=0;void leaf(BiTree root)void leaf(BiTree root)if(root!=NULL)if(root!=NULL)leaf(root-LChild);leaf(root-LChild);leaf(root-RChild);leaf(root-RChild);if(root-LChild=NULL&root-RChild=NULL)if(root-LChild=NULL&root-RChild=
30、NULL)LeafCount+;LeafCount+;第49页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用 2.统计叶子结点数目统计叶子结点数目方法方法2：int leaf(BiTree root)if(root=NULL)return 0;else if(root-LChild=NULL)&(root-RChild=NULL)return 1;else return leaf(root-LChild)+leaf(root-RChild);第50页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用 3
31、.建立二叉链表方式存储的二叉树建立二叉链表方式存储的二叉树void CreateBiTree(BiTree&bt)void CreateBiTree(BiTree&bt)ch=getchar();ch=getchar();if(ch=.)bt=NULL;if(ch=.)bt=NULL;else elsebt=(BiTree)malloc(sizeof(BiTNode);bt=(BiTree)malloc(sizeof(BiTNode);bt-data=ch;bt-data=ch;CreateBiTree(bt-LChild);CreateBiTree(bt-LChild);CreateBiTr
32、ee(bt-RChild);CreateBiTree(bt-RChild);第51页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用 4.在二叉树中查找具有给定值的结点 BiTree FindNode（BiTree T,ElemType x）InitStack(S);push(S,T);while(!StackEmpty(S)if(Getop(S,p)&p!=NULL)/向左走到尽头 push(S,p-lchild);pop(S,p);/空指针退栈 if(!StackEmpty(S)/访问结点，向右一步 pop(S,p);if(p-data=x)r
33、eturn p;p=p-rchild;return NULL;第52页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.2 遍历算法的应用 5.表达式运算可以用二叉树表示表达式前缀表达式、中缀表达式、后缀表达式分别是表达式树的前序、中序、后序遍历结果。思考：利用中缀表达式建立表达式树？根据表达式树如何求得表达式的结果？e e d d c c b b f f a a +*/-第53页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.3 线索二叉树 1.基本概念基本概念二叉树的遍历是将二叉树中结点按一定规律二叉树的遍历是将二叉树中结点按一定规律线
34、性化线性化的过程。的过程。当以二叉链表作为存储结构时，只能找到结点的左、右孩子当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在遍历序列中的前驱和后继信息。信息，而不能直接得到结点在遍历序列中的前驱和后继信息。要得到这些信息，要得到这些信息，第一种方法是将二叉树遍历一遍，在遍历第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪费时过程中便可得到结点的前驱和后继，但这种动态访问浪费时间；第二种方法是充分利用二叉链表中的空链域，将遍历过间；第二种方法是充分利用二叉链表中的空链域，将遍历过程中结点的前驱、后继信息保存下来。程中结点的前驱、
35、后继信息保存下来。第54页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.3 线索二叉树 1.基本概念基本概念在有在有n个结点的二叉链表中共有个结点的二叉链表中共有2n个链域，有个链域，有n+1个空链域。个空链域。我们可以利用剩下的我们可以利用剩下的n+1个空链域来存放遍历过程中结点的个空链域来存放遍历过程中结点的前驱和后继信息。前驱和后继信息。现作如下规定：现作如下规定：若结点有左子树，则其若结点有左子树，则其LChild域指向其左孩子，否则域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其域指向其前驱结点；若结点有右子树，则其RChild域指
36、向其右孩子，否则域指向其右孩子，否则RChild域指向其后继结点。域指向其后继结点。第55页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.3 线索二叉树 1.基本概念基本概念为了区分孩子结点和前驱、后继结点，为结点结构增设两个为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，如下图所示：标志域，如下图所示：LChildLtagDataRtagRChild其中：其中：Ltag=0 LChild域指示结点的左孩子域指示结点的左孩子 1 LChild域指示结点的遍历前驱域指示结点的遍历前驱Rtag=0 RChild域指示结点的右孩子域指示结点的右孩子 1 RC
37、hild域指示结点的遍历后继域指示结点的遍历后继第56页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.3 线索二叉树 1.基本概念基本概念二叉树的二叉线索存储表示：二叉树的二叉线索存储表示：typedef enum PointerTagLink,Thread;typedef struct BitThrNodeElemType data;struct BiThrNode*lchild,*rchild;PointerTag LTag,Rtag;BiThrNode,*BiThrTree;第57页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.
38、3 线索二叉树 1.基本概念基本概念 线索：线索：在这种存储结构中，指向前驱和后继结点的指针叫做在这种存储结构中，指向前驱和后继结点的指针叫做线索线索。线索链表：线索链表：以这种结构组成的二叉链表作为二叉树的存储结构，叫做以这种结构组成的二叉链表作为二叉树的存储结构，叫做线线索链表索链表。线索化：线索化：对二叉树以某种次序进行遍历并且加上线索的过程叫做对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化线索化。线索二叉树：线索二叉树：线索化了的二叉树称为线索化了的二叉树称为线索二叉树线索二叉树。第58页，共106页，编辑于2022年，星期六6.3 遍历二叉树和线索二叉树6.3.3 线索二叉树
39、 2.二叉树的线索化二叉树的线索化 线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前线索化实质上是将二叉链表中的空指针域填上相应结点的遍历前驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过驱或后继结点的地址，而前驱和后继的地址只能在动态的遍历过程中才能得到。因此程中才能得到。因此线索化的过程是在遍历过程中修改空指针域的线索化的过程是在遍历过程中修改空指针域的过程过程。对二叉树按照不同的遍历次序进行线索化，可以得到不同的线对二叉树按照不同的遍历次序进行线索化，可以得到不同的线索二叉树索二叉树（先序线索二叉树、中序线索二叉树和后序线索二叉树）（先序线索二叉树、中序线索二叉树和后序线
40、索二叉树）。第59页，共106页，编辑于2022年，星期六下面是对同一棵二叉树的遍历方法不同得到的不同线索树。下面是对同一棵二叉树的遍历方法不同得到的不同线索树。NULL(a)二叉树二叉树ABCDGEFH(b)先序线索二叉树先序线索二叉树 ABCDGEFHNULLNULL（c）中序线索二叉树）中序线索二叉树 ABCDGEFH（d）后序线索二叉树）后序线索二叉树 NULLABCDGEFH第60页，共106页，编辑于2022年，星期六void InOrderThreading(BiThrTree&Thrt,BiThrTree T)/*对二叉树对二叉树T进行中序线索化，其中进行中序线索化，其中pre
41、始终指向刚访问过的结点始终指向刚访问过的结点*/if(!(Thrt=(BiThrTree)malloc(sizeof(BiThrNode)return;Thrt-LTag=Link;Thrt-RTag=Thread;Thrt-rchild=Thrt;if(!T)Thrt-lchild=Thrt;else Thrt-lchild=T;pre=Thrt;InThreading(T);pre-rchild=Thrt;pre-RTag=Thread;Thrt-rchild=pre;中序线索化算法：中序线索化算法：第61页，共106页，编辑于2022年，星期六void Inthreading(BiThr
42、Tree p)if(p)Inthread(root-LChild);/*线索化左子树线索化左子树*/if(p-LChild=NULL)p-Ltag=Thrad;p-LChild=pre;/*置前驱线索置前驱线索*/if(pre-RChild=NULL)/*置后继线索置后继线索*/pre-RChild=p;pre=p；Inthread(root-RChild);/*线索化右子树线索化右子树*/中序线索化算法：中序线索化算法：第62页，共106页，编辑于2022年，星期六TRAVERSEINTHREAD(BiThrTree T)p=T-lchild;while(p!=T)while(p-ltag=
43、Link)pp-lchild;visit(p-data);while(p-Rtag=Thread&p-rchild!=T)p=p-rchild;visit(p-data);中序线索化二叉树的遍历算法：中序线索化二叉树的遍历算法：第63页，共106页，编辑于2022年，星期六6.4 树和森林6.4.1 树的存储结构1、双亲表示法双亲表示类型定义#define MAX 100typedef struct node char data;int parent;/双亲位置域 NODE;NODE treeMAX;I IA AC CB BH HG GF FE ED D 9 9 A 0 A 0 B 1 B 1
44、 C 1 C 1 D 2 D 2 E 2 E 2 F 3 F 3 G 5 G 5 H 5 H 5 I 5 I 50 01 12 23 34 45 56 67 78 89 9data parent 找一个结点的双亲十分方便，但要找一个结点的孩子则要遍历整个结构第64页，共106页，编辑于2022年，星期六6.4 树和森林6.4.1 树的存储结构2、孩子链表表示法孩子链表表示法I IA AC CB BH HG GF FE ED D A B C D E F G H I0123456789 7 9 8 2 3 5 6 4data link结点的孩子结点链表 找一个结点的孩子十分方便，但要找一个结点的双
45、亲则要遍历整个结构第65页，共106页，编辑于2022年，星期六6.4 树和森林6.4.1 树的存储结构2、孩子链表表示法孩子链表表示法树的孩子链表类型定义 struct node /孩子结点孩子结点 int child;struct node*link;struct t_node char data;struct t_node*link;/孩子链表头指针孩子链表头指针 treeMAX;第66页，共106页，编辑于2022年，星期六6.4 树和森林6.4.1 树的存储结构3、双亲孩子表示法双亲孩子表示法I IA AC CB BH HG GF FE ED D9 A0 B1 C1 D 2 E 2
46、F3 G5 H 5 I5 0123456789 7 9 8 2 3 5 6 4data parent link结点的孩子结点链表第67页，共106页，编辑于2022年，星期六 struct node char data;struct node *son,*brother;I IF F树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点G GH HE EC CD DB BA A6.4 树和森林6.4.1 树的存储结构3、孩子兄弟表示法孩子兄弟表示法I IA AC CB BH HG GF FE ED D第68页，共106页，编辑于2022年，星期六I IA AC CB BD DH HG GF F
47、E E此二叉链表既是树(a)(a)的孩子兄弟表示又是二叉树(b)(b)的二叉链表(a)(a)(b)(b)由此可将树与二叉树对应起来A AI IH HD DG GF FC CE EB BF FI IA AB BD DH HG GC CE E6.4 树和森林第69页，共106页，编辑于2022年，星期六6.4 树和森林6.4.2 森林和二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。1.树转换为二叉树树转换为二叉树 树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。对对树树中中的的每每个个结结点点，只只保保留留其其与与第第一一个个孩孩子子结结点
48、点之之间间的的连连线线，删删去去其与其它孩子结点之间的连线。其与其它孩子结点之间的连线。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。使之结构层次分明。第70页，共106页，编辑于2022年，星期六6.4 树和森林6.4.2 森林和二叉树的转换二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。1.树转换为二叉树树转换为二叉树 树中所有相邻兄弟之间加一条连线。树中所有相邻兄弟之间加一条连线。对对树树中中的的每每个个结结点点，只只保保留留其其与与第第一一个个孩孩子子结结点点之之间间的的连连线，删去其与
49、其它孩子结点之间的连线。线，删去其与其它孩子结点之间的连线。以树的根结点为轴心，将整棵树顺时针旋转一定的角度，以树的根结点为轴心，将整棵树顺时针旋转一定的角度，使之结构层次分明。使之结构层次分明。第71页，共106页，编辑于2022年，星期六I IA AC CB BD DH HG GF FE EF FI IA AB BD DH HG GC CE E6.4 树和森林6.4.2 森林和二叉树的转换1.树转换为二叉树树转换为二叉树第72页，共106页，编辑于2022年，星期六6.4 树和森林6.4.2 森林和二叉树的转换2.森林转换为二叉树森林转换为二叉树森林转换为二叉树的方法为：森林转换为二叉树的
50、方法为：（1）将森林中的每棵树转换成相应的二叉树。）将森林中的每棵树转换成相应的二叉树。（2）第一棵二叉树不动，）第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。在一起后，所得到的二叉树就是由森林转换得到的二叉树。第73页，共106页，编辑于2022年，星期六6.4 树和森林6.4.2 森林和二叉树的转换2.森林转换为二叉树森林转换为二叉树用递归的方法描述森林转换为二叉树的过程为：用递归的方