根据提供的文档信息,我们可以深入探讨数据结构中的二叉树及其操作方法。此文档涉及的关键知识点主要包括:二叉树的创建、二叉树的遍历(包括递归与非递归方式),以及二叉树的存储表示等内容。
### 一、二叉树的创建
在文档中,`CreateBTNode` 函数用于创建一个二叉树。这个函数接收一个指向树根节点的指针 `b` 和一个字符串 `str`,通过解析字符串来构建二叉树。具体实现步骤如下:
1. **初始化变量**:定义了一个动态数组 `St` 用于存储节点指针,同时定义了变量 `top` 作为栈顶指示器,并初始化为空。
2. **遍历字符串**:从字符串的第一个字符开始遍历,直到遇到终止符 `\0`。
3. **处理字符**:
- 如果遇到 `(`,则将当前节点入栈,并设置标志 `k` 表示接下来的节点将是当前节点的左孩子。
- 如果遇到 `)`,则弹出栈顶元素。
- 如果遇到 `,`,则将标志 `k` 设置为 2,表示接下来的节点将是栈顶节点的右孩子。
- 对于其他字符(即数据部分),创建一个新的节点,用当前字符初始化其数据域,并将其设置为叶子节点。然后根据栈顶状态将新节点设置为左孩子或右孩子。
通过这种方式,可以根据输入字符串构建出相应的二叉树。
### 二、二叉树的遍历
文档中提供了三种遍历二叉树的方法:递归的先序遍历、非递归的先序遍历以及另一种非递归先序遍历方法。
#### 1. 递归的先序遍历
递归先序遍历遵循“根-左-右”的顺序。具体来说,对于每个节点:
- 首先访问根节点。
- 然后递归地遍历左子树。
- 最后递归地遍历右子树。
这种方法简洁易懂,但可能因递归深度过大而导致栈溢出。
#### 2. 非递归的先序遍历(带标志位)
非递归先序遍历利用栈来辅助遍历过程,以避免递归带来的问题。这里采用了一个结构体 `St` 来存储节点指针及一个标记值 `tag`,用来区分是否已经访问过当前节点。遍历过程如下:
- 初始化栈顶为空。
- 将根节点入栈,并设置其 `tag` 为 1。
- 当栈不为空时,循环执行以下操作:
- 如果栈顶节点的 `tag` 为 1,则表示当前节点还未被访问,将其左右孩子(如果存在)依次入栈,并将当前节点重新入栈,同时设置其 `tag` 为 0。
- 如果栈顶节点的 `tag` 为 0,则表示可以直接访问该节点,输出节点值后弹出该节点。
这种方法可以有效避免栈溢出的问题,但需要额外的空间来存储节点标记。
#### 3. 非递归的先序遍历(不带标志位)
第三种非递归先序遍历方法同样使用栈,但没有使用额外的标记字段。遍历逻辑如下:
- 初始化栈顶为空。
- 将根节点入栈。
- 当栈不为空时,循环执行以下操作:
- 弹出栈顶节点并输出。
- 如果该节点有右孩子,则将右孩子入栈。
- 如果该节点有左孩子,则将左孩子入栈。
这种方法相比第二种非递归遍历方法更加简单,但可能需要更复杂的逻辑来确定访问顺序。
### 总结
本篇文档详细介绍了如何基于输入字符串创建二叉树,以及如何通过递归和非递归的方式进行先序遍历。这些方法不仅适用于理论学习,也对实际编程实践有着重要的指导意义。通过理解这些基本概念和技术,开发者可以更好地理解和设计高效的数据结构算法。