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

6.3遍历二叉树和线索二叉树
6.3.1遍历二叉树
一、递归算法
在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。
遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。左子树1、先序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）访问根结点；
（2）先序遍历左子树；
（3）先序遍历右子树。
用伪码表示：
voidPreOrder（T）//T是树根
{
if（T为空）return；
访问T的元素；
PreOrder（T的左子树）；
PreOrder（T的右子树）；
}2、中序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）中序遍历左子树；
（2）访问根结点；
（3）中序遍历右子树。
用伪码表示：
voidInOrder（T）//T是树根
{
if（T为空）return；
InOrder（T的左子树）；
访问T的元素；
InOrder（T的右子树）；
}3、后序遍历二叉树的操作定义为：
若二叉树为空，则空操作；否则
（1）后序遍历左子树；
（2）后序遍历右子树；
（3）访问根结点。
voidPostOrder（T）//T是树根
{
if（T为空）return；
PostOrder（T的左子树）；
PostOrder（T的右子树）；
访问T的元素；
}先序遍历的例子

PreOrder（T）：先序遍历以T为根的树。（1）对于空树（2）对于只有根结点的树（3）对于只有左子树的树（4）对于只有右子树的树（5）对于具有左子树、右子树的树（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解（6）对于结点更多的树，从上到下逐步分解树的遍历的实现：
下面先建立一棵二叉树，然后给出中序遍历二叉树的递归算法。#include<iostream>
usingnamespacestd;
structnode
{//树的结点结构。二叉链表表示法
intdata;
node*lchild,*rchild;
};voidmerge_tree(node*parent,node*lchild,node*rchild)
{//将parent、lchild、rchild三个结点合并起来，形成树形结构
parent->lchild=lchild;
parent->rchild=rchild;
}
/////////
node*create_node(intdata)
{//为data生成一个结点
node*p=newnode;
p->data=data;
p->lchild=p->rchild=0;
returnp;
}相应写出中序遍历二叉树的算法。
voidInOrderTraverse(node*t)
{
if(t!=0)
{
InOrderTraverse(t->lchild);
cout<<t->data<<"";

InOrderTraverse(t->rchild);

}
}voidtest_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）;
cout<<endl;

}二、非递归算法
递归思想虽然可以很好地适应人的思维，利用它可以快速地设计出算法，但是它的执行效率却是相当的低，为了提高程序的执行效率，某些时候把递归的程序化为非递归的是很有必要的。 我们可以想象，递归程序通常都涉及到一个回溯的问题。比如在二叉树中，进行中序遍历时，刚开始是沿着左子树一直向下运行，直到左子树遍历完成，才去遍历根，然后是右子树。那么怎么样能够从下面的结点回到上面？在递归程序中由每一层递归中的变量