C++实现二叉树的创建与遍历

"这篇文章主要介绍了如何使用C++来创建二叉树并进行前序、中序和后序遍历。二叉树是一种重要的数据结构，它由节点（包含数据和两个指向子节点的指针）组成。二叉链表是二叉树的一种常见存储结构，其中每个节点包含一个字符数据、一个指向左子节点的指针和一个指向右子节点的指针。" 在C++中，我们首先定义一个`struct node`来表示二叉树的节点，包含一个字符类型的数据成员`data`，以及两个指向子节点的指针`lchild`和`rchild`。然后，我们使用指针`bitree`来指向这个结构体，以便在程序中操作二叉树。 创建二叉树的过程是通过递归实现的。`Create`函数接收一个指针`T`，读取用户输入的字符，如果输入的是'!'，则表示创建空节点（`T=NULL`）。否则，分配内存给新节点，并继续递归地创建左子树和右子树。 前序遍历（根-左-右）是在访问根节点后，再分别遍历左子树和右子树。`inpre`函数使用了栈来辅助遍历，当当前节点不为空或者栈不空时，循环进行。首先，将当前节点压入栈中并打印其数据，然后遍历左子节点。当左子树遍历完后，从栈中弹出节点，访问其右子树。 中序遍历（左-根-右）通常用于二叉搜索树，顺序是左子树-根节点-右子树。`inorder`函数采用递归方式，先遍历左子树，然后打印根节点数据，最后遍历右子树。 后序遍历（左-右-根）在访问根节点之前，需要先遍历左子树和右子树。`postorder`函数同样使用递归方法，首先遍历左子树，接着遍历右子树，最后打印根节点数据。 此外，代码中还定义了一个`depth`函数，用于计算二叉树的深度。这通过递归地计算左右子树的最大深度来实现。如果树为空，则深度为0；否则，返回左子树和右子树深度中的较大值加1。 总结来说，这段代码展示了如何在C++中创建二叉树以及使用前序、中序和后序遍历的方法。这些基本操作对于理解和处理二叉树问题至关重要，它们广泛应用于各种数据结构和算法的实现，如搜索、排序和树的遍历问题。