ADT BinaryTree 的实现及验证程序采用的主要数据结构：二叉树、栈、队算法思想：1、 先序建树、输出树、后序遍历用递归方法。性能分析：O( n )2、 先序遍历、中序遍历：性能分析：O( n )(1) 若遇到新节点非空则先入栈，然后访问其左子树。(2) 若为空则将栈顶结点出栈，访问其右子树。(3) 循环1、2直到栈为空且无节点可入栈。先序与中序的区别是：先序在入栈时访问节点，中序在出栈时访问节点。3、 层遍历：性能分析：O( n )(1) 根节点入队(2) 节点出队并访问(3) 若节点有左孩子，则左孩子入队；有右孩子，则右孩子入队。(4) 重复2、3直到队列为空。4、 线索树：算法与先序遍历、中序遍历一样，只是将访问节点的Visit函数改为连接前驱与后继的操作。性能分析：O(
标签：
BinaryTree
ADT
性能分析
树
上传时间：
2014-12-20
上传用户：SimonQQ
