数据结构二叉树的存储结构和遍历-ppt课件.ppt

1、二叉树的存储结构和遍历二叉树的存储结构和遍历二叉树的遍历二叉树的遍历二叉树的存储结构二叉树的存储结构小结和作业小结和作业顺序存储顺序存储二叉链表二叉链表三叉链表三叉链表链式存储链式存储问题的提出问题的提出递归遍历算法递归遍历算法遍历的应用实例遍历的应用实例二叉树的顺序存储二叉树的顺序存储顺序存储是用一组连续的存储单元存放数据顺序存储要求数据是线性结构二叉树是非线性结构如何把二叉树转换为线性结构，而且保持结点之间的父/子关系?二叉树的顺序存储二叉树的顺序存储ACGBDEFK LHJIM NO123456789101112131415满二叉树：从上到下，从左往右依次编号二叉树的顺序存储二叉树的顺序

2、存储 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二叉树的顺序存储二叉树的顺序存储ACGBDEFHJI12345678910完全二叉树：从上到下，从左往右依次编号 0 1 2 3 4 5 6 7 8 9 10 A B CEFDGH IJ二叉树的顺序存储二叉树的顺序存储ABDCEF一般的二叉树：想象成一个完全二叉树一般的二叉树：想象成一个完全二叉树ABDCEF00000000二叉树的顺序存储二叉树的顺序存储ABDCEF000

3、000001234567891011121314二叉树的顺序存储二叉树的顺序存储ABDCEF1253714 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 A B CDEF 0 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;二叉树的顺序存储二叉树的顺序存储#define MA

4、X_TREE_SIZE 100 / 二叉树的最大结点数二叉树的最大结点数typedef struct TElemType dataMAX_TREE_SIZE; char flagMAX_TREE_SIZE; SqBiTree;二叉树的顺序存储二叉树的顺序存储适用于一般的二叉树链式存储链式存储二叉链表二叉链表lchild data rchild二叉链表的结点结构二叉链表的结点结构: :左指针域，指向当左指针域，指向当前结点的左子树前结点的左子树数据域，存储当前数据域，存储当前结点的取值信息结点的取值信息右指针域，指向当右指针域，指向当前结点的右子树前结点的右子树指向二叉树根结点指向二叉树根结点头

5、指针：头指针：前述二叉树的二叉链表如下所示：前述二叉树的二叉链表如下所示：AFECDBroot链式存储链式存储二叉链表二叉链表a1a2a3LABDCEF1253714typedef struct BiTNode / 结点结构结点结构 TElemType data; struct BiTNode *lchild, *rchild; / 左右孩子指针左右孩子指针 BiTNode, *BiTree;lchild data rchild结点结构结点结构: :二叉链表的二叉链表的C C 语言类型描述如下语言类型描述如下: :左指针域左指针域数据域数据域右指针域右指针域链式存储链式存储二叉链表二叉链表pa

6、rent lchild data rchild三叉链表的结点结构三叉链表的结点结构: :指向双亲结指向双亲结点的指针域点的指针域左指针域左指针域数据域数据域右指针域右指针域链式存储链式存储三叉链表三叉链表rootAEFDCB二叉树的三叉链表表示：二叉树的三叉链表表示：链式存储链式存储三叉链表三叉链表 typedef struct TriTNode TElemType data; struct TriTNode *lchild, *rchild; struct TriTNode *parent; TriTNode, *TriTree;三叉链表的三叉链表的C C 语言类型描述如下语言类型描述如下:

7、 :parent lchild data rchild结点结构结点结构: :/ 结点结构结点结构/ 左右孩子指针左右孩子指针/双亲指针双亲指针链式存储链式存储三叉链表三叉链表问题的提出问题的提出 在实际应用中，经常需要在二叉树中查找具有某些特征的结点，或者对树中的全部结点逐一进行某种处理，这就提出了二叉树的遍历的问题。问题的提出问题的提出 定义：定义：顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。作用：作用： 遍历的目的是线性化，使二叉树中的结点能够按照某种次序排列在一个线性队列上，便于处理。问题的提出问题的提出 线性结构的遍历：因为每个结点均只有一个后继，

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

9、右子树）先序遍历右子树先序（根）遍历先序（根）遍历ABCDEFGHKABCDEFGHKA B C D E F G H K课堂练习课堂练习ABDCEFABC写出先序遍历的结果写出先序遍历的结果void 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); / 遍历右子树 先序遍历先序遍历中序（根）遍历中序（根）遍历左子树右

10、子树根根根根左左子树子树右右子树子树 若二叉树为空树，则空操作；否则，（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(

11、T-rchild, visit); / 遍历右子树后序（根）遍历后序（根）遍历左子树右子树根根根根左左子树子树右右子树子树 若二叉树为空树，则空操作；否则，（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); /

12、 遍历左子树3 Postorder(T-rchild, visit); / 遍历右子树4 visit(T-data); / 访问结点后序遍历后序遍历课堂练习课堂练习写出三种遍历的结果ABECDABCDEFGHK先序序列：先序序列：中序序列：中序序列：后序序列：后序序列：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、由前序序列和中序序列

13、，或者后序和中序序列可以唯一确定一颗二叉树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三种遍历的比较三种遍历的比较3、复制二叉树、复制二叉树4、建立二叉树、建立二叉树2、查询二叉树中某个结点、查询二叉树中某个结点应用举例应用举例1、统计二叉树中结点的个数、统计二叉树中结点的个数遍历访问了每个结点一次且仅一次遍历访问了每个结点一次且仅一次设置一个全局变量设置一个全局变量count=0count=0统计二叉树中结点的个数统计二叉树中结点的个数将将visitvisi

14、t改为改为:count+:count+统计二叉树中结点的个数统计二叉树中结点的个数void PreOrder (BiTree T)if (! T ) return;count+;Preorder( T-lchild); Preorder( T-rchild);void 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);/

15、 遍历右子树 统计二叉树中结点的个数统计二叉树中结点的个数int count=0;main()PreOrder(T);printf(”%d”,count);递归思想递归思想: :如果是空树，返回如果是空树，返回0 0统计二叉树中结点的个数统计二叉树中结点的个数求出左子树的结点的个数求出左子树的结点的个数m求出右子树的结点的个数求出右子树的结点的个数n返回返回m+n+1统计二叉树中结点的个数统计二叉树中结点的个数int CountNode (BiTree T)/返回指针T所指二叉树中所有叶子结点个数 if (!T ) return 0;/空树空树m = CountNode( T-lchild);

16、 n = CountNode( T-rchild); return (m+n+1);求二叉树的深度求二叉树的深度课堂练习：课堂练习：空树的深度为空树的深度为0，求二叉树的深度求二叉树的深度int Depth (BiTree T )/ 返回二叉树的深度if ( !T ) return (0);depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild );depthval = 1 + (depthLeft depthRight ? depthLeft :depthRight);return depthval;查询二叉树中的某个结点查询二叉

17、树中的某个结点给定指向二叉树的根结点的指针给定指向二叉树的根结点的指针T T和和x x，在，在T T中查找中查找数据元素的值等于数据元素的值等于x x的结点，如果找到，则返回一的结点，如果找到，则返回一个指针，指向这个结点，否则，返回空指针。个指针，指向这个结点，否则，返回空指针。ABECDTX= C查询二叉树中的某个结点查询二叉树中的某个结点1. 1. 在二叉树不空的前提下在二叉树不空的前提下, ,和根结点的元素进和根结点的元素进行比较行比较, ,若相等若相等, ,则找到返回指向根结点的指针则找到返回指向根结点的指针2. 2. 否则在左子树中进行查找否则在左子树中进行查找, ,若找到若找到,

18、 ,则返回指针则返回指针3. 3. 否则继续在右子树中进行查找否则继续在右子树中进行查找, ,若找到若找到, ,则返则返回指针回指针, ,否则返回空指针否则返回空指针查询二叉树中的某个结点查询二叉树中的某个结点BiTree Search (BiTree T, TElemType x) if (!T) return(NULL);if (T-data=x) return (T)； if(p) /返回值不是空指针，则表示返回值不是空指针，则表示x在左子树中在左子树中return(p); else return(Search(T-rchild, x) ;p=Search(T-lchild, x);复制

19、二叉树复制二叉树( (练习练习) )给定一棵二叉树，给定一棵二叉树，T指向其根结点，复制一棵二叉树，指向其根结点，复制一棵二叉树，返回一个指向新树根结点的指针返回一个指向新树根结点的指针根元素根元素T右子树右子树根元素根元素NEWT左子树左子树右子树右子树左子树左子树复制二叉树复制二叉树1、如果、如果T为空，则返回空指针为空，则返回空指针2、复制根结点，、复制根结点，p指向新结点指向新结点3、复制左子树，、复制左子树，pl指向左子树的根指向左子树的根4、复制右子树，、复制右子树，pr指向右子树的根指向右子树的根5、p-lchid = pl，p-rchild = pr6、返回、返回p复制二叉树复

20、制二叉树Bitree Copy(BitTree T)if(!T) return(NULL);p = new BiNode; p-data = T-datapl = Copy(T-lchild);pr = Copy(T-rchild);p-lchild = pl; p-rchild =pr;return(p);以下列字符串表示以下列字符串表示AB C D 建立二叉树建立二叉树以字符串的形式以字符串的形式“根左子树右子树根左子树右子树”定义定义一棵二叉树一棵二叉树以空白字符以空白字符“ ”“ ”表示表示1）空树）空树2）只含一个根）只含一个根结点的二叉树结点的二叉树A以字符串以字符串“A ” ”表

21、示表示ABCD3）建立二叉树建立二叉树A B C D A BCDATBCD建立二叉树建立二叉树Status CreateBiTree(BiTree &T) / CopyTreescanf(&ch);else T-data = ch; / 生成根结点return OK;if (!(T = new BiTNode) exit(OVERFLOW);if (ch = = ) T = NULL; CreateBiTree(T-lchild); / 构造左子树 CreateBiTree(T-rchild); / 构造右子树小结小结1）二叉树的顺序存储表示）二叉树的顺序存储表示 2）二叉树的二叉链表存储表示）二叉树的二叉链表存储表示 二叉链表二叉链表 双亲链表双亲链表 三叉链表三叉链表 3）二叉树的遍历）二叉树的遍历 前序（先根）前序（先根） 中序（中根）中序（中根） 后序（后根）后序（后根） 作业作业作业：作业：6.12，6.42 ，6.43建立二叉树建立二叉树由二叉树的先序和中序序列建树由二叉树的先序和中序序列建树二叉树的先序序列：二叉树的先序序列：二叉树的中序序列：二叉树的中序序列：左子树左子树左子树左子树右子树右子树右子树右子树根根根根建立二叉树建立二叉树a b c d e f gc b d a e g faab bccddeeffggabcdefg先序先序:中序中序: