数据布局 （20）二叉树的遍历与线索化

一、二叉树的遍历

       遍历是对树的一种最根本的运算，所谓遍历二叉树，就是按肯定的规则温序次走遍二叉树的全部节点，使每一个节点都被访问一次，而且只被访问一次。二叉树的遍历方式重要有四种：前序遍历、中序遍历、后序遍历和层序遍历。

•         前序遍历：
  
  
  
  • 遍历序次：根节点→左子树→右子树。
    
  • 特点：先访问根节点，然后遍历左子树，末了遍历右子树。
    
  • 应用场景：在须要起首处置处罚根节点，然后递归处置处罚左右子树的场景下使用。
    
  
  
•         中序遍历：
  
  
  
  • 遍历序次：左子树→根节点→右子树。
    
  • 特点：先遍历左子树，然后访问根节点，末了遍历右子树。这种遍历方式得到的节点序次是按照从小到大的序次分列的（对于二叉搜刮树）。
    
  • 应用场景：在须要按照某种序次（如升序或降序）访问节点的场景下使用。
    
  
  
•         后序遍历：
  
  
  
  • 遍历序次：左子树→右子树→根节点。
    
  • 特点：先遍历左子树，然后遍历右子树，末了访问根节点。
    
  • 应用场景：在须要起首处置处罚左右子树，然后处置处罚根节点的场景下使用。
    
  
  
•         层序遍历：
  
  
  
  • 遍历序次：按照从根节点开始的条理序次，从上到下、从左到右依次访问每个节点。
    
  • 特点：按照节点的条理序次举行遍历。
    
  • 应用场景：在须要按照条理序次访问节点的场景下使用，如条理遍历打印二叉树。
    
  
  

二、二叉树的线索化

       二叉树线索化是一种将平常二叉树转换为具有特殊线索（指向前驱和后继节点）的二叉树的过程。这种线索化的目的是为了进步对二叉树的遍历服从以及节流存储空间。

•         线索化的概念：
  
  
  
  • 在平常二叉树中，每个节点都有两个指针（左指针和右指针），分别指向其左孩子和右孩子。但在某些环境下，这些指针大概为空（即指向NULL）。线索化就是使用这些空闲的指针来存储节点的前驱和后继信息。
    
  • 对于每个节点，如果其左指针为空，则可以用这个指针指向该节点的前驱节点；如果其右指针为空，则可以用这个指针指向该节点的后继节点。
    
  
  
•         线索化的步调：
  
  
  
  • 根据某种遍历序列（如前序、中序或后序遍历），先确定下来每个节点的前驱和后继。
    
  • 对于每个节点，如果其左指针或右指针为空，则分别用这些指针指向其前驱或后继节点。
    
  • 为每个节点增长一个标记字段（如ltag和rtag），用于指示其左指针和右指针是指向孩子还是线索。
    
  
  
•         线索化的长处：
  
  
  
  • 进步遍历服从：线索化后，可以在常量时间内找到节点的前驱和后继节点，从而实现更高效的遍历。
    
  • 节流存储空间：线索化可以用较少的额外存储空间来实现，由于只须要为每个节点增长一个或两个标记字段来存储线索信息。
    
  • 支持双向遍历：线索化的二叉树可以支持双向遍历，即可以在给定节点的前向和后向方向上遍历树。
    
  
  
•         线索化的实现：
  
  
  
  • 可以通过递归或迭代的方式实现二叉树的线索化。
    
  • 在实现过程中，须要维护一个前驱节点指针（如pre指针），用于纪录遍历过程中当前节点的前一个节点。
    
  • 每次遍历到一个节点时，根据该节点的左指针和右指针是否为空，以及前驱节点指针的值，来创建前驱和后继关系。
    
  
  

总结

       综上所述，二叉树的遍历与线索化是数据布局中的紧张内容。遍历方式的选择取决于具体的应用场景和需求；而线索化则是一种进步遍历服从和节流存储空间的有用方法。

 结语    

光阴因芳华慨然以赴而更加静好

凡间因少年挺身向前而更加瑰丽

！！！