数据结构二叉树的遍历练习

### 关于二叉树遍历的数据结构练习题或教程

#### 二叉树的定义与基本操作
在计算机科学中，二叉树是一种常见的非线性数据结构。每个节点最多有两个子节点：左子节点和右子节点。对于给定的一个二叉树根节点 `root`，可以通过递归方法计算该树的最大深度：

int BTreeDepth(BTNode* root) {
    if (root == NULL) {
        return 0;
    }
    int leftdepth = BTreeDepth(root->left);
    int rightdepth = BTreeDepth(root->right);
    return leftdepth > rightdepth ? leftdepth + 1 : rightdepth + 1;
}

这段代码展示了如何通过递归来获取一棵二叉树的高度[^1]。

#### 二叉树的四种主要遍历方式
针对二叉树的操作通常涉及不同的遍历模式，主要包括前序遍历、中序遍历、后序遍历以及层序遍历。其中，层序遍历是指按照层次顺序依次访问每一层上的所有结点，在实现上可以借助队列来完成这一过程[^2]。

#### 实现层序遍历的具体算法如下：
为了更好地理解并掌握这些概念，下面给出了一种基于广度优先搜索（BFS）策略实现的Python版本层序遍历函数：

from collections import deque

def levelOrderTraversal(root):
    result = []
    queue = deque([root])
    
    while queue:
        current_level_size = len(queue)
        current_level_nodes = []

        for _ in range(current_level_size):
            node = queue.popleft()
            
            if not node:
                continue
                
            current_level_nodes.append(node.val)

            if node.left:
                queue.append(node.left)
                
            if node.right:
                queue.append(node.right)
        
        if current_level_nodes:
            result.append(current_level_nodes)
    
    return result

此段代码实现了对输入参数为二叉树根节点的对象执行层序遍历的功能，并返回按每层分组的结果列表。

#### 定义二叉树节点类
当涉及到具体的编程实践时，往往还需要先创建表示单个节点的数据模型。这里提供了一个简单的 Python 类用于构建二叉树中的各个节点实例:

class TreeNode(object):
    def __init__(self, value=None, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right

上述代码片段展示了一个典型的二叉树节点对象初始化逻辑[^3]。