有关二叉树遍历的算法

女爷i 2024-03-17 19:46 3阅读 0赞

**1** **问题**

二叉树遍历是指按照一定的次序访问二叉树中所有的结点，并且每个结点仅被访问一次的过程。通过遍历得到二叉树中某种结点的线性序列，即将非线性结构线性化，这里“访问”的含义可以很多，例如输出结点值或对结点值实施某种运算等。二叉树遍历是最基本的运算，是二叉树中所有其他运算的基础。而本次周博客将针对于二叉树遍历的算法展开讨论，便于更好地理解其算法。

**2** **方法**

1.  先序遍历；  
    1.访问根结点 2.先序遍历左子树 3.先序遍历右子树
2.  中序遍历；  
    1.中序遍历左子树 2.访问根结点 3.中序遍历右子树
3.  后序遍历。

1.后序遍历左子树 2.后序遍历右子树 3.访问根结点

通过实验、实践等证明提出的方法是有效的，是能够解决开头提出的问题。

代码清单 1

<table> 
 <tbody> 
 <tr> 
 <td># 二叉树类 class BTree(object): # 初始化 def __init__(self, data=None, left=None, right=None): self.data = data # 数据域 self.left = left # 左子树 self.right = right # 右子树 # 先序遍历 def preorder(self): # 根左右 if self.data is not None: print(self.data, end=' ') if self.left is not None: self.left.preorder() if self.right is not None: self.right.preorder() # 中序遍历 def inorder(self): # 左根右 if self.left is not None: self.left.inorder() if self.data is not None: print(self.data, end=' ') if self.right is not None: self.right.inorder() # 后序遍历 def postorder(self): # 左右根 if self.left is not None: self.left.postorder() if self.right is not None: self.right.postorder() if self.data is not None: print(self.data, end=' ')</td> 
 </tr> 
 </tbody> 
</table>

**3** **结语**

针对有关二叉树遍历的算法的问题，提出本次博客所涉及的方法（先序遍历、中序遍历、后序遍历），通过本次Python实验，证明该方法是有效的，本此的方法还存在许多不足或考虑不周的地方，例如，通过网络的查询，知道并了解了层序遍历也是二叉树遍历的算法，希望可以在未来的学习过程中可以熟悉并掌握层序遍历，以便更好的解决问题。