访问根结点先序遍历二叉树算法思想.PPT

中序非递归遍历二叉树并输出二叉树结点数目 通过实验要总结与思考树这种数据结构的描述和树的遍历算法的实现，以及建立在树遍历算法基础上的其它算法的实现方法。 * * 实验二、树结构算法设计 实验原理 树是一个或多个结点组成的有限集合T，有且仅有一特殊的称之为根的结点，其余结点可分为m（m=0）个互不相交的集合T1，T2，…Tm，其中每个集合本身又是一个树，称为根的子树。 二叉树是结点数为0或每个结点最多只有左右两棵子树的树。 二叉树是一种特殊的树，它的特点是： ⑴每个结点最多只有两棵子树， 即不存结点度大于2的结点； ⑵子树有左右之分，不能颠倒。 遍历二叉树是指按一定的规律对二叉树的每个结点，访问且仅访问一 次的处理过程。 中序遍历二叉树 算法思想: 若二叉树非空，则： 1）中序遍历左子树； 2）访问根结点； 3）中序遍历右子树。 后序遍历二叉树 算法思想: 若二叉树非空，则： 1）后序遍历左子树； 2）后序遍历右子树； 3）访问根结点。 先序遍历二叉树 算法思想:若二叉树非空,则： 1）访问根结点； 先序遍历左子树； 3）先序遍历右子树。 实验目的 1、理解树结构的逻辑特性； 2、熟练掌握二叉树的逻辑结构 特性以及各种存储方法 3、熟练掌握二叉树的各种基本 操作，尤其是三种遍历算法 以及线索化算法。 实验内容 1、编写中序遍历二叉树的递归 和非递归程序并调试； 2、 给定一颗用链表表示的二叉 树，其根指针为root，编写求 二叉树结点数目的程序并调 试 。 实验数据及结果分析： 6 5 3 2 8 9 7 10 从键盘上读取数据元素，建立的二叉树如左图，则对该图按中序遍历得到的序列为：2-3-5-6-7-8-9-10. 一共8个结点。不管是递归还是非递归，执行结构都一样，只是实现过程不同 实验思考 *