二叉树的基本算法
(1) 根据屏幕提示输入二叉树的各个结点,并建立该二叉树; (2)选择某种遍历方式输出该二叉树; (3)求该二叉树的叶子结点数; (4)求该二叉树的高度; (5)将该二叉树中所有结点的左、右子树相互换,并输出。 二叉树是一种特殊的树结构,每个节点最多有两个子节点,分别称为左子节点和右子节点。在本文中,我们将探讨二叉树的一些基本算法,包括如何创建二叉树、遍历二叉树以及计算其叶子节点数和高度,以及如何实现二叉树的左右子树交换。 我们来看如何创建二叉树。创建二叉树的过程是通过输入节点数据,然后递归地创建左子树和右子树。在给定的代码中,`createBiTree()` 函数使用递归方式构建二叉树。它首先读取一个字符,如果字符为'#'表示没有更多的节点,返回空指针NULL;否则,分配内存创建一个新的节点,存储字符数据,并递归地创建左子树和右子树。 接下来是二叉树的遍历。遍历二叉树有三种常见方法:前序遍历、中序遍历和后序遍历。在代码中,这三种遍历方式都使用了递归实现: - **前序遍历**(PreOrder):先访问根节点,然后递归遍历左子树,最后遍历右子树。 - **中序遍历**(InOrder):先遍历左子树,然后访问根节点,最后遍历右子树。 - **后序遍历**(PostOrder):先遍历左子树,然后遍历右子树,最后访问根节点。 对于二叉树的一些属性,我们可以计算: - **高度**:高度是指从根节点到最远叶子节点的最长路径上边的数目。`height()` 函数通过递归计算左右子树的高度并取较大值加1得到二叉树的高度。 - **叶子节点数**:叶子节点是没有子节点的节点。`leafs()` 函数递归地检查每个节点,当左右子节点都为空时,表示找到了一个叶子节点,返回1;否则,继续递归计数。 为了实现**交换二叉树的所有左右子树**,`Exchange()` 函数递归地交换每个节点的左右子树。保存当前节点的左子树,然后将右子树赋值给左子树位置,将保存的左子树赋值给右子树,最后对左右子树进行递归交换。 这些基本操作是二叉树算法的基础,它们广泛应用于各种问题,如搜索、排序、数据压缩等。理解并掌握这些概念和算法对于学习数据结构和算法至关重要。在实际应用中,二叉树可以被用来实现二分查找、堆排序、AVL树、红黑树等更高级的数据结构和算法。