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

本文主要介绍了如何使用C++建立和打印二叉树，特别是通过先序遍历的方法。二叉树是一种特殊的数据结构，每个节点最多有两个子节点，分为左子树和右子树，广泛应用于二叉查找树、二叉堆和二叉排序树等领域。在二叉树中，第i层的节点数最多为2的i-1次方，深度为k的二叉树最多有2^k - 1个节点，且叶子节点数与深度为2的节点数之间的关系遵循特定公式。 在C++中，二叉树节点通常用结构体表示，包括数据域、指向左孩子的指针和指向右孩子的指针。为了建立二叉树，可以采用递归方式，这里演示了先序建立二叉树的算法。在输入中，用字符'#'表示空节点，其他字符则用于创建非空节点。`CreateBiTree()`函数首先读取一个字符，如果字符为'#'，则返回空指针；否则，创建一个新的节点，存储字符，并递归地为左右子节点调用`CreateBiTree()`。 二叉树的遍历是关键操作，这里提供了先序、中序和后序遍历的实现。先序遍历顺序为根-左-右，中序遍历顺序为左-根-右，后序遍历顺序为左-右-根。这些遍历方法都使用了递归实现。 在主函数`main()`中，首先调用`CreateBiTree()`建立二叉树，然后调用`PreOrderTraverse(T)`进行先序遍历并打印结果。程序最后使用`getch()`函数暂停，以便用户查看输出。 总结来说，本文详细阐述了如何使用C++创建二叉树以及执行不同顺序的遍历操作。通过理解这些概念和代码实现，读者可以更好地掌握二叉树的基本操作和应用。