常常要求在树中查找具有某种特征结点或者对树中全部结点逐一.ppt

6.3遍历二叉树和线索二叉树 6.3.1 遍历二叉树 一、递归算法 在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条有哪些信誉好的足球投注网站路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。 遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。 1、先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）访问根结点； （2）先序遍历左子树； （3）先序遍历右子树。 用伪码表示： void PreOrder（T）//T是树根 { if（T为空）return； 访问T的元素； PreOrder（T的左子树）； PreOrder（T的右子树）； } 2、中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）中序遍历左子树； （2）访问根结点； （3）中序遍历右子树。 用伪码表示： void InOrder（T）//T是树根 { if（T为空）return； InOrder（T的左子树）； 访问T的元素； InOrder（T的右子树）； } 3、后序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点。 void PostOrder（T）//T是树根 { if（T为空）return； PostOrder（T的左子树）； PostOrder（T的右子树）； 访问T的元素； } 先序遍历的例子 PreOrder（T）：先序遍历以T为根的树。 树的遍历的实现： 下面先建立一棵二叉树，然后给出中序遍历二叉树的递归算法。 #include iostream using namespace std; struct node {//树的结点结构。二叉链表表示法 int data; node *lchild,*rchild; }; void merge_tree(node *parent,node *lchild,node *rchild) {//将parent、lchild、rchild三个结点合并起来，形成树形结构 parent-lchild=lchild; parent-rchild=rchild; } ///////// node *create_node(int data) {//为data生成一个结点 node * p=new node; p-data=data; p-lchild=p-rchild=0; return p; } 相应写出中序遍历二叉树的算法。 void InOrderTraverse(node * t) { if(t!=0) { InOrderTraverse(t-lchild); coutt-data ; InOrderTraverse(t-rchild); } } void test_tree() {////////建立一棵树 node *a,*b,*c,*d,*e,*f,*g; a=create_node(1); b=create_node(2); c=create_node(3); d=create_node(4); e=create_node(5); f=create_node(6); g=create_node(7); merge_tree(e,0,g); merge_tree(d,e,f); merge_tree(b,c,d); merge_tree(a,b,0); //中序遍历，用以测试树是否建立 InOrderTraverse（a）; coutendl; } 二、非递归算法 递归思想虽然可以很好地适应人的思维，利用它可以快速地设计出算法，但是它的执行效率却是相当的低，为了提高程序的执行效率，某些时候把递归的程序化为非递归的是很有必要的。 我们可以想象，递归程序通常都涉及到一个回溯的问题。比如在二叉树中，进行中序遍历时，刚开始是沿着左子树一直向下运行，直到左子树遍历完成，才去遍历根，然后是右子树。那么怎么样能够从下面的结点回到上面？在递归程序中由每一层递归中的变量保存，如果写成非递归程序，也需要有保存上面结点的位置，通常用栈来保存。 我们看一下中序遍历的非递归过程。 根据这样的分析过程可以写出如下的非递归算法： 非递归算法： ①定义一个栈S ②根结点T入栈s.push（T） ③while(1) { 如果s的栈顶元素为空，break（跳出循环） 否则，栈顶的左孩子入栈 } ④跳出循环是因为栈顶元素为空，所以栈顶元素出栈 ⑤此时如果栈空，算法结束 否