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

6.3遍历二叉树和线索二叉树 6.3.1 遍历二叉树 一、递归算法 在二叉树的一些应用中，常常要求在树中 查找具有某种特征的结点，或者对树中全部结点 逐一进行某种处理。这就引入了遍历二叉树的问 题，即如何按某条搜索路径巡访树中的每一个结 点，使得每一个结点均被访问一次，而且仅被访 问一次。 遍历对线性结构是容易解决的，而二叉树 是非线性的，因而需要寻找一种规律，以便使二 叉树上的结点能排列在一个线性队列上，从而便 于遍历。 左子树 二叉树的形态 a 右子树 对于如图所示二叉树的形态，假如以L、D、R分别表示遍历 左子树、遍历根结点和遍历右子树，那么遍历整个二叉树就有DLR 、LDR、LRD、DRL、RDL、RLD六种遍历方案。若规定先左后右 ，则只有前三种情况，分别规定为： DLR先（根）序遍历， LDR中（根）序遍历， LRD后（根）序遍历。 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为根的树。 （1）对于空树 做空操作。 （2）对于只有根结点的树 访问结果就是根结点本身。 a （3）对于只有左子树的树 a b 访问顺序 a b 根左子树右子树 （4）对于只有右子树的树 a b 访问顺序 a b 根左子树右子树 （5）对于具有左子树、右子树的树 a c 访问顺序 a c b 根左子树右子树 b （6）对于结点更多的树，从上到下逐步分解 - +/ a * ef b - cd （6）对于结点更多的树，从上到下逐步分解 访问顺序 根左子树右子树 - +/ a * ef b - cd - + a * b - cd / ef （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - + a * b - cd / ef （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - + a * b - cd / ef +a* b - cd （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - / ef +a * b - cd *b- cd （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - / ef +a*b - cd -cd （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - / ef +a*b-cd （6）对于结点更多的树，从上到下逐步分解 访问顺序 根 左子树 右子树 - /ef +a*b-cd 树的遍历的实现： 下面先建立一棵二叉树，然后给出中序遍 历二叉树的递归算法。 #include 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); coutdatarchild); 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）; cout using namespace std; void InOrder(node *t) stack s; s.push(t); while(1) while(1) if(s.top()=0)break; node *temp=s.top(); s.push(temp-lchild); s.pop(); if(s.empty()=true) return; node *temp=s.top(); s.pop(); coutdatarchild); 同理，先序遍历的过程如下 * b - cd 初始状态下，根结点 入栈 * b - cd * * b - cd * 栈顶元素不为空， 访问之， 且栈顶元素的左孩子 入栈 * b - cd * * b * b - cd * * b 栈顶元素不为空， 访问之， 且栈顶元素的左孩子 入栈 * b - cd * * b b * b - cd * * b b 栈顶元素为空， 则栈顶元素出栈 * b - cd * * b b * b - cd * * b b 栈不为空， 则栈顶元素出栈， 且栈顶元素右孩子入 栈 * b - cd * *b * b - cd * *b 栈顶元素为空， 则栈顶元素出栈 * b - cd * *b * b - cd * *b 栈不为空， 则栈顶元素出栈， 且栈顶元素右孩子入 栈 * b - cd - *b * b - cd - *b 栈顶元素不为空， 访问之， 且栈顶元素的左孩子 入栈 * b - cd -*b - c * b - cd -*b 栈顶元素不为空， 访问之， 且栈顶元素的左孩子 入栈 - c * b - cd -*b - c c * b - cd -*b - c c 栈顶元素为空， 则栈顶元素出栈 * b - cd -*b - c c * b - cd -*b - c c 栈不为空， 则栈顶元素出栈， 且栈顶元素右孩子入 栈 * b - cd -*b - c * b - cd -*b - c 栈顶元素为空， 则栈顶元素出栈 * b - cd -*b - c * b - cd -*b - c 栈不为空， 则栈顶元素出栈， 且栈顶元素右孩子入 栈 * b - cd -*b d c * b - cd -*b d c 栈顶元素不为空， 访问之， 且栈顶元素的左孩子 入栈 * b - cd -*bcd d * b - cd -*bcd d 栈顶元素为空， 则栈顶元素出栈 * b - cd -*bcd d * b - cd -*bcd d 栈不为空， 则栈顶元素出栈， 且栈顶元素右孩子入 栈 * b - cd -*bcd * b - cd -*bcd 栈顶元素为空， 则栈顶元素出栈 * b - cd -*bcd * b - cd -*bcd 栈为空，遍历结束 二叉树的先序遍历的非递归算法 定义一个栈S 根结点T入栈s.push（T） while(1) while(1) 如果s的栈顶元素为空，break（跳出循环） 否则，访问栈顶元素，栈顶的左孩子入栈 跳出循环是因为栈顶元素为空，所以栈顶元素出栈 此时如果栈空，算法结束 否则，栈顶元素出栈，且其右孩子入栈 后序遍历比较复杂。 中序遍历是在元素出栈后，右子树入栈前 进行访问；先序遍历是在左子树入栈前进行访问 。 后序遍历应该在右子树出栈后进行访问， 所以我们应该设立一个标志，在右子树入栈前该 标志入栈；右子树访问完毕后出栈，标志也出栈 ，标志下面的那一个结点是根，应该被访问了。 * b - cd 初始状态下，根结点 入栈 * b - cd * * b - cd * 栈顶元素不为空， 栈顶元素的左孩子入 栈 * b - cd * b * b - cd * b 栈顶元素不为空， 栈顶元素的左孩子入 栈 * b - cd * b * b - cd * b 栈顶元素为空， 则栈顶元素出栈 * b - cd * b * b - cd * b 栈不为空， 且栈顶不是标志 标志入栈 栈顶元素右孩子入栈 * b - cd * b flag * b - cd * b flag 栈顶元素为空， 则栈顶元素出栈 * b - cd * b flag * b - cd * b flag 栈不为空， 且栈顶是标志 则标志出栈 且访问标志下的元素 ，访问后出栈 * b - cd * b * b - cd * b 栈不为空， 且栈顶不是标志 标志入栈 栈顶元素右孩子入栈 * b - cd * b flag - * b - cd * b flag - 栈顶元素不为空， 栈顶元素的左孩子入 栈 * b - cd * b flag - c * b - cd * b flag - c 栈顶元素不为空， 栈顶元素的左孩子入 栈 * b - cd * b flag - c * b - cd * b flag - c 栈顶元素为空， 则栈顶元素出栈 * b - cd * b flag - c * b - cd * b flag - c 栈不为空， 且栈顶不是标志 标志入栈 栈顶元素右孩子入栈 * b - cd * b flag - c flag * b - cd * b flag - c flag 栈顶元素为空， 则栈顶元素出栈 * b - cd * b flag - c flag * b - cd * b flag - c flag栈不为空， 且栈顶是标志 则标志出栈 且访问标志下的元素 ，访问后出栈 * b - cd * b flag - c * b - cd * b flag - c 栈不为空， 且栈顶不是标志 标志入栈 栈顶元素右孩子入栈 * b - cd * b flag - c d flag * b - cd * b flag - c d flag栈顶元素不为空， 栈顶元素的左孩子入 栈 * b - cd * b flag - c d flag * b - cd * b flag - c d flag 栈顶元素为空， 则栈顶元素出栈 * b - cd * b flag - c d flag * b - cd * b flag - c d flag 栈不为空， 且栈顶不是标志 标志入栈 栈顶元素右孩子入栈 * b - cd * b flag - c d flag flag * b - cd * b flag - c d flag flag栈顶元素为空， 则栈顶元素出栈 * b - cd * b flag - c d flag flag * b - cd * b flag - c d flag flag 栈不为空， 且栈顶是标志 则标志出栈 且访问标志下的元素 ，访问后出栈 * b - cd * b flag - c d flag * b - cd * b flag - c d flag 栈不为空， 且栈顶是标志 则标志出栈 且访问标志下的元素 ，访问后出栈 * b - cd * b flag - c d * b - cd * b flag - c d 栈不为空， 且栈顶是标志 则标志出栈 且访问标志下的元素 ，访问后出栈 * b - cd *b - c d * b - cd *b - c d 栈为空， 算法结束 后序遍历非递归算法： 定义一个栈S 根结点T入栈s.push（T） while(1) 如果s的栈顶元素为空，break（跳出循环） 否则，栈顶的左孩子入栈 跳出循环是因为栈顶元素为空，所以栈顶元素出栈 while（1） 此时如果栈空，算法结束 如果栈顶元素是标志，则标志出栈，再弹出一个且访问之。 如果栈顶元素temp不是标志，则标志入栈，temp的右孩子入栈 ，且结束循环 转到执行 重写一下就是： 定义一个栈S 根结点T入栈s.push（T） while(1) while(1) 如果s的栈顶元素为空，break（跳出循环） 否则，栈顶的左孩子入栈 跳出循环是因为栈顶元素为空，所以栈顶元素出栈 while（1） 此时如果栈空，算法结束 如果栈顶元素是标志，则标志出栈，再弹出一个且访问之。 如果栈顶元素temp不是标志，则标志入栈，t