清华大学：《数据结构》课程教学资源（习题讲义实验）二叉树试验三

试验三 实验题目:在采用链式存储结构存储的二叉树上,以root指向根接 点,p指向任一给定的接点,编程实现求出从根接点到给定接点之间 的路径 试验要求: 1、采用二叉链表作存储结构。 创建二叉树,并实例化有若干结点的二叉树 3、实现二叉树非递归后序遍历算法,并输出所需路径,算法要有较好 的性能。 4、设计驱动程序、测试用例,并得出正确结果。 试验目的 、掌握二叉树的存储结构及其基本操作,学会定义二叉树的链式存储 结构,在实际问题中灵活运用。 2、掌握二叉树的基本运算,如插入结点、输出结点、遍历算法等,熟 悉操作的实现方法。 3、通过本试验的具体应用实例,进一步熟悉和掌握二叉树的操作。 提示: 在二叉树上无论采用哪种遍历方法,都能够访问遍树中的所有结点。由于访 问结点的顺序不同,前序遍历和中序遍历都很难达到设计的要求;但采用后序遍 历二叉树是可行的,因为后序遍历是最后访问根结点,按这个顺序将访问过的结 点存储到一个顺序栈中,然后再输出即可。因此可以非递归地后序遍历二叉树 root,当后序遍历访问到结点*p时,此时栈 stack中存放的所有结点均为给定结 点*p的祖先,而由这些祖先便构成了一条从根结点到结点*p之间的路径

试验三 实验题目：在采用链式存储结构存储的二叉树上，以 root 指向根接 点，p 指向任一给定的接点，编程实现求出从根接点到给定接点之间 的路径 试验要求： 1、 采用二叉链表作存储结构。 2、 创建二叉树，并实例化有若干结点的二叉树。 3、 实现二叉树非递归后序遍历算法，并输出所需路径，算法要有较好 的性能。 4、 设计驱动程序、测试用例，并得出正确结果。 试验目的： 1、 掌握二叉树的存储结构及其基本操作，学会定义二叉树的链式存储 结构，在实际问题中灵活运用。 2、 掌握二叉树的基本运算，如插入结点、输出结点、遍历算法等，熟 悉操作的实现方法。 3、 通过本试验的具体应用实例，进一步熟悉和掌握二叉树的操作。 提示： 在二叉树上无论采用哪种遍历方法，都能够访问遍树中的所有结点。由于访 问结点的顺序不同，前序遍历和中序遍历都很难达到设计的要求；但采用后序遍 历二叉树是可行的，因为后序遍历是最后访问根结点，按这个顺序将访问过的结 点存储到一个顺序栈中，然后 再输出即可。因此可以非递归地后序遍历二叉树 root，当后序遍历访问到结点*p 时，此时栈 stack 中存放的所有结点均为给定结 点*p 的祖先，而由这些祖先便构成了一条从根结点到结点*p 之间的路径