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

二叉树的存储结构和遍历，二叉树的遍历，二叉树的存储结构，总结和运算，顺序存储，二叉链表，三叉链表，链式存储，问题提出，递归遍历算法，遍历的应用实例，二叉树的顺序存储，顺序存储是用一组连续的存储单元来存储数据，顺序存储要求数据是线性结构，二叉树是非线性结构，如何将二叉树转换成线性结构并保持节点之间的父子关系？二叉树的顺序存储A、C、G、B、D、E、F、K、L、H、J、I、M、N、O、1、2、3、4、5、6、7、8、9、10、11、12、13、14、15，全二叉树：从上到下、从左到右编号，二叉树的顺序存储，012345678910112131415，数组的下标，也是从左到右，012345678910，二叉树的顺序存储，一般二叉树：想象一个完整的二叉树、0，0，0，0，0，0，0，0，0，0，1，2，3，4，5，6，7，8，9，10，11，12，13，14，二叉树的顺序存储，012345678910，012345678910，二叉树的顺序存储，二叉树的顺序存储，0，0，0，0，0，0，0，0，0，0，0，1，2，3，4，5，6，7，8，9，10，11，1 ，#defineMAX_TREE_SIZE100/二叉树类型的最大节点数deflemtypseqbitreemax _ TREE _ SIZE；/单元1存储根节点SqBiTreebt，二叉树的顺序存储，#defineMAX_TREE_SIZE100/二叉树类型结构的最大节点数 teletype datamax _ TREE _ SIZE；charflag最大树的大小； SqBiTree，二叉树的顺序存储，适用于一般二叉树，链式存储-二叉链表，二叉链表的节点结构：左指针字段，指向当前节点的左子树，数据字段，当前节点的值信息，右指针字段，指向当前节点的右子树，头指针：指向二叉树根节点的二叉链表，头指针：上述二叉树的二叉链表如下所示structBiTNode*lchild，*rchild。/左右子指针位节点，*位树；节点结构：二进制链表的C语言类型描述如下：左指针字段，数据字段，右指针字段，链存储-二进制链表，三叉链表的节点结构：指向父节点的指针字段，左指针字段，数据字段，右指针字段，链存储-三叉链表，根，e，星期日下午，星期日下午，二叉树的三叉链表表示：链存储-三叉链表，typedeftructrinode teletypedata；struct曲节点*lchild，*rchild。结构节点*父节点；TriTNode，* TriTree三叉链表的C语言类型描述如下：节点结构：/节点结构，/左右子指针，/父指针，链式存储-三叉链表，提出了问题。在实际应用中，经常需要在二叉树中寻找具有一定特征的节点，或者逐个处理树中的所有节点，这就产生了二叉树的遍历问题。定义：沿着特定的搜索路径巡视二叉树中的节点，这样每个节点只能被访问一次。遍历的目的是线性化，这样二叉树中的节点可以按照一定的顺序排列成一个线性队列，以便于处理。线性结构的遍历问题：因为每个节点只有一个后继节点，所以只有一条搜索路径。二叉树的遍历：二叉树是非线性结构，每个节点有两个后继节点，然后是如何遍历的问题，即遍历什么样的搜索路径。问题是二叉树有以下三条搜索路径：1。从上到下逐层遍历；2.从左(子树)到右(子树)的遍历；德国航天中心，LDR，LRD3.从右(子树)到左(子树)的遍历。DRL、RDL、RLD、前序(根)遍历、根、左子树、右子树，如果二叉树为空，则为空操作；否则，(1)访问根节点(2)遍历左子树(3)先按顺序遍历右子树、遍历第一个顺序(根)，a、b、c、d、e、f、g、h、k、a、b、c、d、e、f、g、h、k、a、BCD、efghk，在类中练习，写下第一个顺序遍历的结果，VirtuaPreorder(BitReet、Void(* visit)(ts elem type/遍历右子树)，先遍历，遍历中间顺序(根)，然后再遍历根、左子树、右子树，如果二叉树是空树，则执行空操作； 否则，(1)中间顺序遍历左子树；(2)访问根节点；(3)中间顺序遍历右子树、中间顺序(根)遍历，a，b，c，d，e，f，g，h，k，a，b，c，d，e，f，g，h，k，a，BDC，ehgkf，中间顺序遍历，void in order (bitreet，void(* visit)(ts elemtype/遍历右子树)，反向顺序(根)遍历，左子树，右子树，根，根，左子树，右子树否则，(1(2)按以下顺序遍历右子树；(3)访问根节点。后顺序(根)遍历，a，b，c，d，e，f，g，h，k，a，dcb，hkgfe，void后顺序(bitreed，void(* visit)(ts elem type/访问节点)，后顺序遍历，课堂练习，写出三次遍历的结果，前顺序：中顺序：后顺序：ABCDEFGHK，BDCAEHGKF，DCBHKGFEA，三次遍历的比较：1。如果不考虑访问，三种遍历算法在结构上是相同的，因此推栈和推栈的过程是相同的。与三次遍历相比，两次和三次遍历的执行过程是不同的(访问位于不同的地方)。3，二叉树可以由前序序列和中序序列，或后序和中序序列，前序序列，中序序列，后序序列，ABCDEFGHK，BDCAEHGKF，DCBHKGFEA，三次遍历的比较，3，复制二叉树，4，建立二叉树，2，查询二叉树中的节点，应用示例，1，计算二叉树中的节点数，遍历访问每个节点一次且仅一次， 设置一个全局变量count=0，计算二叉树中的节点数，将访问次数改为：count，计算二叉树中的节点数。 t)返回；计数；预订(T-l child)；订单前(T-r child)；void preorder (bitreed，void(* visit)(ts elemtype/遍历右子树)，计算二叉树中的节点数，int count=0；主()，前序(T)；printf(“% d”，计数)；如果是空树，则返回0，计算二叉树中的节点数，计算左子树中的节点数m，计算右子树中的节点数n，返回m1，计算二叉树中的节点数，intCountNode(BiTreeT)/返回由指针t表示的二叉树中所有叶节点数，如果(！t)返回0；/空树，m=计数节点(T-l child)；n=计数节点(T-r child)；return(m1)；要查找二叉树的深度，课堂练习：空树的深度是0，要查找二叉树的深度，intDepth(BiTreeT)/返回二叉树的深度，如果(！t)返回(0)；深度=深度(T-l child)；深度=深度(T-r child)；depthval=1 (depthLeftdepthRight？depthLeft:depthRight右后)；returndepthval，查询二叉树中的一个节点，给定指向二叉树根节点的指针T和X，在T中找到数据元素值等于X的节点，如果找到，返回指向该节点的指针，否则，返回空指针。，T，X=C ，查询二叉树中的一个节点，1。在二叉树不为空的前提下，比较根节点的元素，如果相等，找到一个指向根节点的指针，2。否则，在左边的子树中搜索，如果找到，返回一个指针，3。否则，继续在右子树中搜索，如果找到，返回一个指针，否则返回一个空指针，查询二叉树中的一个节点。返回(空)；如果(T-数据=x)返回(T)；如果(p)/返回值不是空指针，则x在左子树中返回(p );搜索(T-rchild，x)；p=搜索(T-lchild，x)；复制二叉树(练习)，给定一个二叉树，t指向它的根节点，复制一个二叉树，返回一个指向新根节点的指针，根元素，t，右子树，NEWT，左子树，右子树，左子树，复制二叉树，1，如果t为空，返回空指针，2，复制根节点，P指向新节点，3，复制左子树，pl指向左子树的根，4，复制右子树，Pr指向右子树的根，5，p-lchid=pl，P-ARCHID=1返回(空)；p=新索引节点；p-数据=T-数据，pl=复制(T-l child)；pr=复制(T-r child)；p-l child=pl；p-r child=pr；返回(p)；以下字符串用于表示，ABCD，建立二叉树，以字符串“根左子树右子树”的形式定义二叉树，并使用空白字符“”来表示，1)空树，2)仅包含一个根节点的二叉树，A，字符串“A”用于表示，3)，建立二叉树，ABCD，A，B，C，D，A，T，B，C，D，建立二叉树，StatusCreateBiTree(BiTree/生成根节点，返回确定；如果(！(T=新节点)退出(溢出)；如果(ch=)T=空；CreateBitree(T-l child)；/构造左子树，创建二叉树(T-archild)；/右子树的构造，摘要，1)二叉树的顺序存储表示，2)二叉树的二叉链表存储表示，二叉链表，父链表，三叉链表，3)二叉树的遍历，前序(第一个根)，中间序(中间根)，后序(后根)，作业，作业：6.12，6.42，6.43，二叉树的建立，由二叉树的前序和中间序构造二叉树，二叉树的前序：二叉树的中间序： 左子树、左子树、右子树、右子树、根、根、和建立二叉树、abcdefg、cbdaegf、a、a、b、b、c、c、d、d、e、e