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

《常常要求在树中查找具有某种特征的结点或者对树中全部结点逐一》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、6.3遍历二叉树和线索二叉树6.3.1遍历二叉树一、递归算法在二叉树的一些应用中，常常要求在树中查找具有某种特征的结点，或者对树中全部结点逐一进行某种处理。这就引入了遍历二叉树的问题，即如何按某条搜索路径巡访树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。遍历对线性结构是容易解决的，而二叉树是非线性的，因而需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。左子树二叉树的形态a右子树对于如图所示二叉树的形态，假如以L、D、R分别表示遍历左子树、遍历根结点和遍历右子树，那么遍历整个二叉树就有DLR、LDR、LRD、DRL、

2、RDL、RLD六种遍历方案。若规定先左后右，则只有前三种情况，分别规定为：DLR——先（根）序遍历，LDR——中（根）序遍历，LRD——后（根）序遍历。1、先序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。用伪码表示：voidPreOrder（T）//T是树根{if（T为空）return；访问T的元素；PreOrder（T的左子树）；PreOrder（T的右子树）；}2、中序遍历二叉树的操作定义为：若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。用伪码

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

4、（3）对于只有左子树的树ab访问顺序ab根左子树右子树（4）对于只有右子树的树ab访问顺序ab根左子树右子树（5）对于具有左子树、右子树的树ac访问顺序acb根左子树右子树b（6）对于结点更多的树，从上到下逐步分解-+/a*efb-cd（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-+/a*efb-cd-+a*b-cd/ef（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-+a*b-cd/ef（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-+a*b-cd/ef+a*b-cd（6）对于结点更多的树，从上到下逐步分解访

5、问顺序根左子树右子树-/ef+a*b-cd*b-cd（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-/ef+a*b-cd-cd（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-/ef+a*b-cd（6）对于结点更多的树，从上到下逐步分解访问顺序根左子树右子树-/ef+a*b-cd树的遍历的实现：下面先建立一棵二叉树，然后给出中序遍历二叉树的递归算法。#includeusingnamespacestd;structnode{//树的结点结构。二叉链表表示法intdata;node*lchild,*rchild;}

6、;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*

7、t){if(t!=0){InOrderTraverse(t->lchild);cout<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_

8、tree(d,e,f);merge_t