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

1、二叉树的记忆结构和扫描，二叉树的扫描，二叉树的记忆结构，总结和工作，顺序记忆，二叉树表，三叉表，连锁记忆，问题的提出，递归扫描算法，扫描的应用例子，1，PPT学习交流，二叉树的顺序记忆，顺序记忆用一系列的连续存储手段存储数据，顺序记忆要求数据是线性结构2、PPT学习交流，二叉树的顺序记忆：a，c，g，b，d，e，f，k，l，h，m，1，2，3，4，5，6，7，8，9，10，11，12，13，14，15，满二叉树： PPT学习交流二叉树的顺序记忆，012345678910121315，数组的后缀也是节点的编号，01234567891011315，4，PPT学习交流，二叉树的顺序记忆，完全二叉树：

2、从上到下，从左依次编号01、2、3、4、5、6、9、5 一般二叉树：设想完全二叉树，0、0、0、0、0、0、0、0、0、6，PPT学习交流，二叉树的顺序记忆，0、0、0、0、0、0、0、0、1、2、3、4、5、6、7、8、9、10 11、12、12 、8、PPT学习交流、#define MAX_TREE_SIZE 100 /二叉树的最大节点数typedeftelemtypesqbitreemax _ tree _ size； /1号小区存储根节点SqBiTree bt； 二叉树顺序记忆，9，PPT学习交流，#define MAX_TREE_SIZE 100 /二叉树的最大节点数typedefs

3、tructtelemtypedatamax _ tree _ size； char flagMAX_TREE_SIZE； SqBiTree； 二叉树顺序记忆、一般二叉树、10、PPT学习交流、链存储二叉树、二叉树的节点结构：左指针区域、指向当前节点的左子叶、数据区域、指向当前节点的值信息、右指针区域、指向当前节点的右子叶、二叉树的根节点的头指针： 上述二叉树的二叉树的二叉树如下：a，f，e，c，d，b，root，链存储二叉链表，12，PPT学习通信，typedef struct BiTNode /节点结构t elemtype d struct BiTNode *lchild、*rchild；

4、/左右儿童指针BiTNode、*BiTree； 节点结构：二叉链表的c语言类型：左指针域、数据域、右指针域、链存储二叉链表、13、PPT学习通信、三叉链表的节点结构：到父母节点数据域，右指针域，连锁存储三叉链表，14，PPT学习通信，root，二叉树的三叉链表，连锁存储，15，PPT学习交流，typedefstructtritrit 结构节点*rchild、*rchild； 结构节点* parent； 三叉树，*三叉树；三叉链表的c语言类型为：节点结构：/节点结构，/左右孩子的指针，/父母的指针，链中记忆三叉链表，16，PPT学习交流，问题的提案在实用上经常需要寻找具有二叉树特征的节点17、P

5、PT学习交流、问题的提案、定义：通过沿某个搜索路径访问二叉树中的节点，各节点只被访问一次，而且只被访问一次。 作用：扫描的目的是线性化，使二叉树中的节点按某种顺序排列成一个线性矩阵，便于处理。18、PPT学习交流、问题的提出、线性结构的扫描：因为每个节点只有一个接班人，所以搜索路径只有一个。 二叉树的扫描：二叉树不是非线性结构，如果每个节点有两个后续，就存在如何扫描，用什么样的搜索路径扫描的问题。、19、PPT学习交流、问题的提出、二叉树存在以下三个搜索路径： 1先追溯上下层次，从2左(子树)到右(子树)的扫描DLR、LDR、LRD 3接在右(子树)之后扫描左(子树)。 DRL、RDL、RLD

6、、20、PPT学习交流，先通过顺序(根)，再通过、根、左子树、右子树，二叉树为空树则为空的操作； 否则，(1)访问根节点(2)先横穿左子树(3)，再横穿右子树，21，PPT，学习交流， 首先横穿a、b、c、d、e、g、h、k、a、f、g、h、k、h、22、PPT学习交流、班级23 PPT学习交流，void Preorder (BiTree T，void(*visit)(TElemType /右子树)，先巡回，24，PPT学习交流，中序(根)巡回，左子树，根，左子树，右否则，(1)按中顺序遍历左子树(2)访问根节点(3)中顺扫描右子树，25，PPT学习交流：中顺(根)扫描，a，b，c，d，e，f

7、，g，k，a，b，c，d，e，f，f void(*visit)(TElemType /横穿右子树，27，PPT学习交流，后序(根)横穿左子树，右子树，根，根，左子树，右子树，二叉树为空树则空操作； 否则，(1)后遍历左子树(2)后遍历右子树(3)访问根节点。28、PPT学习通信、后手(根)遍历、a、b、c、d、e、f、g、h、k、a、dc、b、h、g、fe、29、PPT学习通信、语音信箱写出PPT学习交流，教室练习三种扫描的结果，31，PPT学习交流，序文序列：中文序列：后文序列：ABBCDDEGHKF，D C B H K G F E A，三种扫描的比较，32，PPT学习交流，1，visit，

8、不考虑三种扫描的算法3种导线的比较，2、3种导线的执行过程不同(visit的位置不同)。 3、前序列和中序列，或者可以从后序列和中序列唯一确定的二叉树，33，PPT学习交流，前序列：中序列：后序列：A B C D E F G H K，bbcehgkf，dbchkgfea，三种扫描的比较，34，PPT学习交流，3，复制二叉树4，制作二叉树检查具有二叉树的节点，应用示例，累计1、二叉树的节点数，35，PPT学习交流，只访问各节点一次，设定全局变量count=0，累计二叉树的节点数，visit为：count，36 t )返回、计数； preorder (t-lchild ) preorder (t-

9、rchild )、void Preorder (BiTree T，* visit ) (t elemtype/遍历右子树，37，PPT学习交流，收集二叉树中的节点数、主()、预览器(t )、打印(“% d”、计数)；38、PPT学习交流、递归思想：如果是空树，则返回0，计算二叉树中的节点数，求出左分树的节点数m，求出右分树的节点数n，返回mn1，39，PPT学习交流，计算二叉树中的节点数，int count node (bi tree 返回指针t指向的二叉树中所有叶的节点的数量，22222222222222 T ) return 0 /空树，m=CountNode(T-lchild )，n=C

10、ountNode(T-rchild )，return (m n 1)、40， 求二叉树的深度，课程练习：空树的深度为0，41，PPT学习交流，求二叉树的深度，返回int Depth (BiTree T )/二叉树的深度，if (！ t )返回(0)、深度左侧=深度，深度右侧=深度，深度val=1？ 深度左：深度右； 返回深度val； 42、PPT学习通信，检查具有二叉树的节点，给二叉树的根节点指针t和x，在t中查找数据元素值等于x的节点，如果找到，则返回指针，否则返回空指针。t，X=C，43，PPT学习通信，查询二叉树中的某个节点，1 .在二叉树不空闲的前提下，与根节点的要素进行比较，相等的话

11、找到指向根节点的指针，2 .否则用左子树搜索，找到的话返回指针如果找到，则返回指针，否则返回空指针，44，PPT学习通信，在二叉树中的某个节点，BiTree Search (BiTree T，TElemType x )，if (！ t )如果返回(空) if (t -数据=x )返回(t )，if(p) /返回值不是空指针，则在左侧子树中x表示返回(p )； else return (搜索(t-rchild，x ) )；p=Search(T-lchild，x )、45、PPT学习交流，复制二叉树(练习)，给定的一个二叉树，t指向其根节点，复制一个二叉树，返回指向新的根节点的指针，根元素、右子树

12、，NEWT，左子树、右子树、左子树、46、PPT学习交流，复制二叉树，1，t为空的话复制空指针、2、根节点，p指向新的节点，复制左子树，pl指向左子树的根，4，复制右子树，pr复制右子树的根回到6，p，47，PPT学习交流，复制二叉树，比特树复制，AD (！ t )返回(空)，p=新bi节点； p -数据=t -数据，pl=复制(t-lchild )，pr=复制(t-rchild )，p-lchild=pl； p-rchild=pr； PS (p )、48、PS学习交流，用以下字符串表示， 创建、二叉树，并以字符串形式在“根左子树右子树”中定义一棵二叉树，用空白字符表示，1 )空树，2 )只包

13、含根节点的二叉树，a、用字符串“a”表示，3 )、49、PPT学习交流，二叉树，AB C D，a，a ，50，PPT学习交流，制作二叉树，生成Status CreateBiTree(BiTree /根节点，return OK； PK (！ (t=新比特)退出(溢出)、if (ch=) T=NULL； 建立CreateBiTree(T-lchild) /左子树，bitree(t-rcild) /结构右子树，51，PPT学习交流，总结，1 )二叉树的顺序记忆表示，2 )二叉树的二叉链表记忆表示，二叉链表，父母链表，三叉链表、后序(后根)、52，PPT学习交流，作业，作业： 6.12，6.42，6.43，53，PPPT学习交流建立二叉树，由二叉树的先序和中序序列建立树，二叉树的中序序列：左子树，左子树，右子树，右子树，根，根建立二叉树，ab，be，gf，ab，be，f，g，a，b，c，c，c，d，d，e，f，g，a，b，c，d，d，e，f，f，g，g，先着3:55， PPT学习通信、二叉树、bi node * bi tree :30创建(TPR，T in，int prepos，int low，int