12二叉树的存储结构和遍历.ppt

《12二叉树的存储结构和遍历.ppt》由会员分享，可在线阅读，更多相关《12二叉树的存储结构和遍历.ppt（64页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、二叉树的存储结构和遍历二叉树的存储结构和遍历二叉树的遍历二叉树的存储结构小结和作业顺序存储顺序存储二叉链表二叉链表三叉链表三叉链表链式链式存储存储问题的提出问题的提出递归遍历算法递归遍历算法非递归遍历算法非递归遍历算法复习双亲链表双亲链表1、一个有、一个有n个结点的满二叉树的叶子结点有多少？个结点的满二叉树的叶子结点有多少？2、完全二叉树的分支为、完全二叉树的分支为1的节点有多少？的节点有多少？3、一个有、一个有n个结点的二叉树最大深度是多少？最少个结点的二叉树最大深度是多少？最少深度是多少？深度是多少？4、二叉树中、二叉树中n0=50，n2为多少？为多少？n1至少为多少？至少为多少？复习复习

2、二叉树的顺序存储二叉树的顺序存储顺序存储是用一组连续的存储单元存放数据顺序存储要求数据是线性结构二叉树是非线性结构如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?二叉树的顺序存储二叉树的顺序存储ACGBDEFK LHJIM NO123456789101112131415满二叉树：从上到下，从左往右依次编号二叉树的顺序存储二叉树的顺序存储 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15数组的下标，也是结点的编号 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15A B CEFDGH IJK LM N O二叉树的顺序存储二叉树的顺序存储

3、ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号 0 1 2 3 4 5 6 7 8 9 10 A B CEFDGH IJ二叉树的顺序存储二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储二叉树的顺序存储ABDCEF000000001234567891011121314二叉树的顺序存储二叉树的顺序存储ABDCEF1253714二叉树的顺序存储二叉树的顺序存储ABDCEF1253714 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B CDEF 0

4、 1 2 3 4 5 6 7 8 9 10 11 12 13 14 11110010000001如何知道有无数据？#define MAX_TREE_SIZE 100 /二叉树的最大结点数二叉树的最大结点数typedef TElemType SqBiTreeMAX_TREE_SIZE;/1号单元存储根结点号单元存储根结点SqBiTree bt;二叉树的顺序存储二叉树的顺序存储适合完全二叉树（书上的定义0号单元？）#define MAX_TREE_SIZE 100 /二叉树的最大结点数二叉树的最大结点数typedef struct TElemType dataMAX_TREE_SIZE;char

5、flagMAX_TREE_SIZE;SqBiTree;二叉树的顺序存储二叉树的顺序存储适用于一般的二叉树链式存储链式存储二叉链表二叉链表lchild data rchild二叉链表的结点结构二叉链表的结点结构:左指针域，指向当左指针域，指向当前结点的左子树前结点的左子树数据域，存储当前数据域，存储当前结点的取值信息结点的取值信息右指针域，指向当右指针域，指向当前结点的右子树前结点的右子树指向二叉树根结点指向二叉树根结点头指针：头指针：前述二叉树的二叉链表如下所示：前述二叉树的二叉链表如下所示：AFECDBroot链式存储链式存储二叉链表二叉链表a1a2a3LABDCEFtypedef stru

6、ct BiTNode /结点结构结点结构 TElemType data;struct BiTNode *lchild,*rchild;/左右孩子指针左右孩子指针 BiTNode,*BiTree;lchild data rchild结点结构结点结构:二叉链表的二叉链表的C C 语言类型描述如下语言类型描述如下:左指针域左指针域数据域数据域右指针域右指针域链式存储链式存储二叉链表二叉链表parent lchild data rchild三叉链表的结点结构三叉链表的结点结构:指向双亲结指向双亲结点的指针域点的指针域左指针域左指针域数据域数据域右指针域右指针域链式存储链式存储三叉链表三叉链表rootA

7、EFDCB二叉树的三叉链表表示：二叉树的三叉链表表示：链式存储链式存储三叉链表三叉链表 typedef struct TriTNode TElemType data;struct TriTNode *lchild,*rchild;struct TriTNode *parent;TriTNode,*TriTree;三叉链表的三叉链表的C C 语言类型描述如下语言类型描述如下:parent lchild data rchild结点结构结点结构:/结点结构结点结构/左右孩子指针左右孩子指针/双亲指针双亲指针链式存储链式存储三叉链表三叉链表链式存储链式存储双亲链表双亲链表结点结构结点结构:data p

8、arent LRTag数据域数据域双亲域，存储当双亲域，存储当前结点双亲结点前结点双亲结点的存储位置的存储位置左右孩子标志，左右孩子标志，如果是其双亲如果是其双亲的左孩子，则的左孩子，则填写填写“L”;如如果是右孩子，果是右孩子，则填写则填写“R”根根链式存储链式存储双亲链表双亲链表BDCEAF01234564401-13LRRRLABDCEF链式存储链式存储双亲链表双亲链表 typedef struct BPTNode /结点结构结点结构 TElemType data;int parent;/指向双亲的指针 char LRTag;/左、右孩子标志域 BPTNodetypedef struct

9、 BPTree/树结构树结构 BPTNode nodesMAX_TREE_SIZE;int num_node;/结点数目结点数目 int root;/根结点的位置根结点的位置 BPTree链式存储链式存储双亲链表双亲链表问题的提出问题的提出 在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出问题的提出 定义：定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。作用：作用：遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出问题的提出

10、线性结构的遍历：因为每个结点均只有一个后继，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个结点有两个后继，则存在如何遍历即按什么样的搜索路径进行遍历的问题。问题的提出问题的提出二叉树存在下述三条搜索路径：二叉树存在下述三条搜索路径：n1先上后下先上后下的按层次遍历；n2先左先左（子树）后右后右（子树）的遍历；nDLR，LDR，LRDn3先右先右（子树）后左后左（子树）的遍历。nDRL，RDL，RLD先序（根）遍历先序（根）遍历左子树右子树根根根根左左子树子树右右子树子树 若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则，否则，（1 1）访问根结点）访问根结点（2 2）先序

11、遍历左子树）先序遍历左子树（3 3）先序遍历右子树）先序遍历右子树先序（根）遍历先序（根）遍历ABCDEFGHKABCDEFGHKA B C D E F G H K先序遍历先序遍历ABDCEFABCvoid Preorder(BiTree T,void(*visit)(TElemType&e)/先序遍历二叉树 1 if(!T)return;2 visit(T-data);/访问结点 3 Preorder(T-lchild,visit);/遍历左子树 4 Preorder(T-rchild,visit);/遍历右子树 先序遍历先序遍历中序（根）遍历中序（根）遍历左子树右子树根根根根左左子树子树右

12、右子树子树 若二叉树为空树，则空操作；否则，（1 1）中序遍历左子树；）中序遍历左子树；（2 2）访问根结点；）访问根结点；（3 3）中序遍历右子树）中序遍历右子树中序（根）遍历中序（根）遍历ABCDEFGHKABCDEFGHKAB D CE H G K F中序遍历中序遍历void Inorder(BiTree T,void(*visit)(TElemType&e)/中序遍历二叉树二叉树 1 if(!T)return;2 Inorder(T-lchild,visit);/遍历左子树3 visit(T-data);/访问结点4 Inorder(T-rchild,visit);/遍历右子树后序（根

13、）遍历后序（根）遍历左子树右子树根根根根左左子树子树右右子树子树 若二叉树为空树，则空操作；否则，（1 1）后序遍历左子树；）后序遍历左子树；（2 2）后序遍历右子树；）后序遍历右子树；（3 3）访问根结点。）访问根结点。后序（根）遍历后序（根）遍历ABCDEFGHKABCDEFGHKAD C B H K G F Evoid Postorder(BiTree T,void(*visit)(TElemType&e)/后序遍历二叉树 1 if(!T)return;2 Postorder(T-lchild,visit);/遍历左子树3 Postorder(T-rchild,visit);/遍历右子树

14、4 visit(T-data);/访问结点后序遍历后序遍历ABCDEFGHK先序先序序列：序列：中序序列：中序序列：后序序列：后序序列：A B C D E F G H KB D C A E H G K FD C B H K G F E A三种遍历的比较三种遍历的比较1、如果不考虑visit，三种遍历的算法在结构上是一样的，因此，压栈和出栈的过程相同。三种遍历的比较三种遍历的比较2、三种遍历的执行过程是不一样的（visit的位置不一样）。3、由前序序列和中序序列，或者后序和中序序列可以唯一确定一颗二叉树非递归遍历一非递归遍历一1、分析递归算法的入、出栈过程，找出规律2、分析递归算法的执行过程，找

15、出visit结点的时机ABECD先序遍历先序遍历-执行过程执行过程先序遍历先序遍历-执行过程执行过程(A)1.if2.vi3.(B)4.(E)1.if2.vi3.(C)4.(D)1.if2.vi3.()4.()1.if2.vi3.()4.()1.if2.vi3.()4.()先序遍历先序遍历-压栈、出栈过程压栈、出栈过程1、调用函数时要压栈2、压栈的内容包括：2.1、调用函数的工作现场1、局部变量2.2、调用函数传递给被调用函数的参数2、返回地址先序遍历先序遍历-压栈、出栈过程压栈、出栈过程3.2、恢复调用函数的工作现场1、局部变量3.1、调用函数传递给被调用函数的参数，丢弃3、函数返回时要出栈

16、2、返回地址ABECD先序遍历先序遍历-压栈、出栈过程压栈、出栈过程A,？B,4C,4N,4A,？B,4C,4A,？B,4C,4N,A,？B,4C,4A,？B,4A,？B,4D,B,41、栈中的每个元素表示一次函数调用2、元素值的含义:参数返回到调用函数的语句编号ABECD先序遍历先序遍历-压栈、出栈过程压栈、出栈过程A,？B,4D,N,4A,？B,4D,A,？B,4D,N,A,？B,4D,A,？B,4A,？ABECD先序遍历先序遍历-压栈、出栈过程压栈、出栈过程A,？E,A,？E,N,4A,？E,A,？E,N,A,？E,A,？空栈先序遍历先序遍历Status PreOrder(BiTree

17、T,Status(*visit)(TElemType e)/测试用例InitStack(S);Push(S,T);/空树、左和右单枝树、完全二叉树while(!StackEmpty(S)while(GetTop(S,p)&p)/栈顶不是空指针 visit(p);push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);/技巧，访问完p的右子树，不再 /访问pPush(S,p-rchild;/while测试用例测试用例1、空树2、只有根3、单枝树4、满二叉树，或者 完全二叉树ABCABC中序遍历中序遍历Status InOrder(BiTree T,

18、Status(*visit)(TElemType e)InitStack(S);Push(S,T);while(!StackEmpty(S)while(GetTop(S,p)&p)/栈顶不是空指针 push(S,p-lchild);Pop(S,p);if(!StackEmpty(S)Pop(S,p);visit(p);Push(S,p-rchild;/while后序遍历后序遍历Status PostOrder(BiTree T,Status(*visit)(TElemType e)InitStack(S);Push(S,);/L,R，表示T下次要进栈的是T /的左、右子树while(!Stac

19、kEmpty(S)while(GetTop(S,)&p)/栈顶不是空指针 push(S,lchild,L);Pop(S,);while(!StackEmpty(S)Pop(S,);if(k=R)visit(p)else Push(S,Push(S,rchild,L;break;/while非递归遍历二非递归遍历二1、设置一个堆栈2、用递归的思想写非递归的程序先序遍历先序遍历NRL 若二叉树为空树，则空操作；若二叉树为空树，则空操作；否则，否则，（1 1）访问根结点）访问根结点（2 2）先序遍历左子树）先序遍历左子树（3 3）先序遍历右子树）先序遍历右子树先序遍历先序遍历NRL1、p指向二叉树的

20、根结点2、如果p不为空 2.1 访问p 2.2 p的右子树压栈 2.3 p=p-lchild 2.4 转去执行23、出栈(p=栈顶元素)pRpp先序遍历先序遍历Status PreOrder(BiTree T,Status(*visit)(TElemType e)if(!T)return;/空树，直接返回InitStack(S);p=T;do if(p)visit(p);/处理p指向的结点Push(S,p-rchild);/保存其右子树，/待以后处理p=p-lchild;/处理左子树elsePop(S,p);while(!StackEmpty(S)中序遍历中序遍历Status InOrder(

21、BiTree T,Status(*visit)(TElemType e)if(!T)return;/空树，直接返回InitStack(S);p=T;do if(p)Push(S,p);/保存自己，/待以后处理p=p-lchild;/处理左子树elsePop(S,p)；/左子树已经处理完visit(p);p=p-rchild;while(!StackEmpty(S)后序遍历后序遍历Status PostOrder(BiTree T,Status(*visit)(TElemType e)if(!T)return;/空树，直接返回InitStack(S);p=T;do if(p)Push(S,);/

22、第1次入栈p=p-lchild;/处理左子树elsePop(S,)if(k=1)Push(S,);/第2次入栈 p=p-rchild;else visit(p);while(!StackEmpty(S)比较比较1、先序遍历压栈的是右子树，先序遍历出栈的是右子树的根，按先序遍历右子树。3、中序压栈的是根结点。中序遍历出栈的是二叉树的根，访问它以后，再按中序遍历右子树。3、后序遍历压栈、出栈的是二叉树的根。它要压栈出栈两次，第一次出栈，要遍历右子树，第二次出栈，要访问它自己。小结小结1）二叉树的顺序存储表示）二叉树的顺序存储表示 2）二叉树的二叉链表存储表示）二叉树的二叉链表存储表示 二叉链表二叉

23、链表 双亲链表双亲链表 三叉链表三叉链表 3）二叉树的遍历）二叉树的遍历 前序（先根）前序（先根）中序（中根）中序（中根）后序（后根）后序（后根）遍历算法、算法遍历算法、算法的递归描述的递归描述、非、非递归描述递归描述作业作业作业：作业：6.12，6.33，6.42 中序遍历非递归，算法中序遍历非递归，算法6.3Status InOrderTraverse(BiTree T,Status(*visit)(TElemType&e)InitStack(S);p=T;While(p|!StackEmpty(S)if(p)Push(S,p);p=p-lchild;else Pop(S,p);if(!v

24、isit(p-data)return ERROR;p=p-rchild;/else/whilereturn OK;n非递归算法非递归算法ABCDEFGpiP-A(1)ABCDEFGpiP-AP-B(2)ABCDEFGpiP-AP-BP-C(3)p=NULLABCDEFGiP-AP-B访问：访问：C(4)算法算法6.3pABCDEFGiP-A访问：访问：C B(5)ABCDEFGiP-AP-D访问：访问：C Bp(6)ABCDEFGiP-AP-DP-E访问：访问：C Bp(7)ABCDEFGiP-AP-D访问：访问：C B Ep(8)ABCDEFGiP-AP-DP-G访问：访问：C B EP=NULL(9)ABCDEFGiP-A访问：访问：C B E G Dp(11)ABCDEFGiP-AP-F访问：访问：C B E G Dp(12)ABCDEFGiP-AP-D访问：访问：C B E Gp(10)ABCDEFGiP-A访问：访问：C B E G D Fp=NULL(13)ABCDEFGi访问：访问：C B E G D F Ap(14)ABCDEFGi访问：访问：C B E G D F Ap=NULL(15)