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

6.3遍历二叉树和线索二叉树6.3.1遍历二叉树一、递归算法在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。,对于如图所示二叉树的形态，假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，那么遍历整个二叉树就有DLR、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR先（根）序遍历，LDR中（根）序遍历，LRD后（根）序遍历。,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）对于只有根结点的树,访问结果就是根结点本身。,a,（3）对于只有左子树的树,a,b,访问顺序,a,b,根,左子树,右子树,（4）对于只有右子树的树,a,b,访问顺序,a,b,根,左子树,右子树,（5）对于具有左子树、右子树的树,a,c,访问顺序,a,c,b,根,左子树,右子树,b,（6）对于结点更多的树，从上到下逐步分解,-,+,/,a,*,e,f,b,-,c,d,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,+,/,a,*,e,f,b,-,c,d,-,+,a,*,b,-,c,d,/,e,f,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,+,a,*,b,-,c,d,/,e,f,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,+,a,*,b,-,c,d,/,e,f,+,a,*,b,-,c,d,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,/,e,f,+,a,*,b,-,c,d,*,b,-,c,d,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,/,e,f,+,a,*,b,-,c,d,-,c,d,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,/,e,f,+,a,*,b,-,c,d,（6）对于结点更多的树，从上到下逐步分解,访问顺序,根,左子树,右子树,-,/,e,f,+,a,*,b,-,c,d,树的遍历的实现：下面先建立一棵二叉树，然后给出中序遍历二叉树的递归算法。,#includeusingnamespacestd;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);coutdatarchild);,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）;coutlc