遍历二叉树--前序后序中序

### 遍历二叉树：前序、中序、后序 在计算机科学中，二叉树是一种常用的数据结构，由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。遍历二叉树是访问树中所有节点的一种方式，根据访问节点的顺序不同，可以分为前序遍历、中序遍历和后序遍历。 #### 前序遍历（Preorder Traversal） 前序遍历的顺序为：首先访问根节点，然后遍历左子树，最后遍历右子树。在代码中体现为： ```c void Preorder(BinTree T) { if (T) { printf("%c", T->data); // 访问根节点 Preorder(T->lchild); // 遍历左子树 Preorder(T->rchild); // 遍历右子树 } } ``` #### 中序遍历（Inorder Traversal） 中序遍历的顺序为：先遍历左子树，然后访问根节点，最后遍历右子树。这种方式在二叉搜索树中尤为重要，因为这样可以得到一个升序序列。代码实现如下： ```c void Inorder(BinTree T) { if (T) { Inorder(T->lchild); // 遍历左子树 printf("%c", T->data); // 访问根节点 Inorder(T->rchild); // 遍历右子树 } } ``` #### 后序遍历（Postorder Traversal） 后序遍历的顺序为：先遍历左子树，再遍历右子树，最后访问根节点。这种遍历方式在删除二叉树或计算表达式树时非常有用。其代码实现为： ```c void Postorder(BinTree T) { if (T) { Postorder(T->lchild); // 遍历左子树 Postorder(T->rchild); // 遍历右子树 printf("%c", T->data); // 访问根节点 } } ``` #### 创建二叉树 在上述代码中，`CreatBinTree`函数用于创建二叉树。该函数递归地读取输入字符来构建二叉树。当输入字符为' '时，表示该位置没有子节点，返回空指针。否则，创建一个新的节点，以输入的字符作为节点数据，并递归调用自身创建左右子树。 ```c BinTree CreatBinTree(void) { BinTree T; charch; if ((ch = getchar()) == ' ') return (NULL); else { T = (BinTNode *)malloc(sizeof(BinTNode)); T->data = ch; T->lchild = CreatBinTree(); T->rchild = CreatBinTree(); return (T); } } ``` #### 树的深度与节点数量 `TreeDepth`函数用于计算二叉树的深度，同时统计树中的节点总数和叶子节点数量。该函数递归地计算左右子树的深度，返回较大值加一即为树的深度。同时，通过全局变量`NodeNum`和`leaf`记录节点总数和叶子节点数量。 ```c int TreeDepth(BinTree T) { int hl, hr, max; if (T) { hl = TreeDepth(T->lchild); hr = TreeDepth(T->rchild); max = hl > hr ? hl : hr; NodeNum = NodeNum + 1; if (hl == 0 && hr == 0) leaf = leaf + 1; return (max + 1); } else return (0); } ``` #### 层次遍历 除了前中后序遍历，还有层次遍历，也被称为宽度优先遍历，按照从上到下、从左到右的顺序访问所有节点。在给定的部分代码中，层次遍历的实现被截断了，但通常会使用队列来存储当前层的所有节点，然后依次访问这些节点的左右子节点，直到队列为空。 总体而言，二叉树的遍历是理解和操作二叉树结构的基础，不同的遍历方式适用于不同的应用场景。通过掌握这些基本的遍历算法，可以更有效地处理涉及二叉树的问题。