树的遍历的操作(包括非递归的前中后和层次遍历)

xiaoxiao2021-02-28  37

递归的就直接贴代码了,前序

void TravelPre(BiTree Tree) { if(Tree) { printf("%c",Tree->data); TravelPre(Tree->lchild); TravelPre(Tree->rchild); } }中后就是将printf换下位置即可。下面重点来说明非递归,首先非递归的前中序是一脉相承的,也就是相似的,因为二叉树在,

遍历的时候有这个特点那就是每个节点会进过3次,而前序遍历就是在第一次遇见节点就输出,中序遍历就是在第二次遇见输出那么这时候栈这个数据结构就可以完美发挥作用了,因为,进栈一次,出栈一次。

//非递归前序遍历 void TravelPreByStack(BiTree Tree) { Stack *stack; InitStack(&stack); if(Tree == NULL) printf("Empty Tree!\n"); else { BiTree p = (BiTree)malloc(sizeof(BiTree)); p = Tree; while(!Empty(stack) || p) //从这里开始这是最关键的地方,这里的实现思想是第一次遇见的节点都放进到栈里 { //面去,这里的判定条件可以相应的有另外的写法!(用且也可以,有兴趣可以试 while(p) //试,不过要修改后面的相应地方) { printf("%c",p->data); //因为是前序,遇见就直接输出,并且放入栈里面的目的是为了在某个节点 Push(&stack,p); //有分支的时候可以在输出完一个分支的时候有效的回到该节点输出另外 p = p->lchild; //一个分支,不然没法获得该回到哪一个节点输出! }//end of while(p) if(Empty(stack)) //栈空就要跳出,并且只能放在这里,放前面和后面都会有相应的用例不能 break; //实现。如:ABCD####E#G#F##创建的树 else { p = Pop(&stack); //左边的子树遍历完毕,逐个右边节点遍历。 p = p->rchild; } }//end of while Empty() }//end of else printf("\n"); }//end of hanshu接下来是中序遍历,和前序基本一样。 //非递归中序遍历 void TravelMidByStack(BiTree Tree) { Stack *stack; InitStack(&stack); if(Tree == NULL) printf("Empty Tree!\n"); else { BiTree p = (BiTree)malloc(sizeof(Tree)); p = Tree; while(!Empty(stack) || p) { while(p) { Push(&stack,p); p = p->lchild; } if(Empty(stack)) break; else { p = Pop(&stack); printf("%c",p->data); p = p->rchild; } }//end of while }//end of else printf("\n"); }下面是比较特别的后序遍历,因为栈只能进,出两道门,而后序需要在,左子树、右子树,根的时候再输出根,所以就要利用其他的手段。

思路1:           改变树的结构变量,在结构中再添加一个整数变量,用来记录是第几次到达该点,若果是第三次则输出。

思路2:

          可以利用栈来完成,只是在第二次本来该出栈的时候,加一个数组来记录次数,如果是第三次才输出。

思路3:

          该思路应该是最简单容易理解实现的,因为在二叉树中后序遍历可以发现一个规律,最先输出的肯定是,叶子节点(先左后右),然后是子节点都输出的根节点输出,此做法的关键是怎么让子节点输出的父节点输出!其实可以利用一个和链表删除类似的小技巧,那就是用个变量记住刚才输出的节点,每次输出的时候比较该节点的子节点是否和该节点重合,重合就代表已经输出过了那么久可以输出。

//非递归后序遍历 void TravelPosByStack(BiTree Tree) { BiTree p = (BiTree)malloc(sizeof(tree)); BiTree IsPri = (BiTree)malloc(sizeof(tree)); IsPri = NULL; //用来记录最近输出的子节点 p = Tree; Stack *stack; InitStack(&stack); while(!Empty(stack) || p) { while(p) //先左下到最底 { Push(&stack,p); p = p->lchild; } p = GetTop(stack); if(p->rchild && p->rchild != IsPri) //关键的条件判断,只有有右边的节点并且是没有被输出过的才向前行 { //进,否则代表该节点应该输出。 p = p->rchild; } else { p = Pop(&stack); printf("%c",p->data); IsPri = p; p = NULL; //让P不进while循环而继续向前行进 } } printf("\n"); }接下来是层次遍历,这个就比较简单,利用队列先进先出就行了,注意是先进左儿子再进右儿子。 //层次遍历 void TravelCCByQueue(BiTree Tree) { Que *que; InitQueue(&que); BiTree p = (BiTree)malloc(sizeof(tree)); p = Tree; AddInQue(&que,p); while(!QueueEmpty(que)) { p = DeleteInQue(&que); if(p->lchild) AddInQue(&que,p->lchild); if(p->rchild) AddInQue(&que,p->rchild); printf("%c",p->data); } printf("\n"); }

转载请注明原文地址: https://www.6miu.com/read-2250394.html

最新回复(0)