在做数据结构慕课 03 - 树 3 Tree Traversals Again 这道题时, 我的思路是先构造好树, 而后直接用 PostOrderTraversal(BinTree BT)进行后序遍历 (这道题目前暂未 ac, 整体方法有待完善) 课上所讲的后序遍历递归实现方法是这样的
- void PostOrderTraversal(BinTree BT)
- {
- if(BT){
- PostOrderTraversal(BT->Left);
- PostOrderTraversal(BT->Right);
- printf("%d\n", BT->Data);
- }
- }
不过这样一来就有问题, 题目中有明确的输出格式要求 (All the numbers must be separated by exactly one space, and there must be no extra space at the end of the line.) 如果是循环方式很容易想到在循环中进行判断并执行相应操作, 可是递归函数中每次递归都是再进入相同的函数, 若是直接在函数中进行标记判断每次进入该函数时标记变量又会被重置, 循环中用到的方法很明显是不可行的于是我想到了用全局变量
如下所示, 在函数外定义好标志变量 count, 将 PostOrderTraversal(BinTree BT)函数传入值增加一个标志位参数, 且该函数最后也要返回改变后的 count 值需要注意的是这样一改变之后每次调用该后序遍历函数时必须变成 count = PostOrderTraversal(BT->Left, count); 以实现 count 数据的传送更新
- int count = 1;
- int PostOrderTraversal(BinTree BT, int count)
- {
- if(BT){
- count = PostOrderTraversal(BT->Left, count);
- count = PostOrderTraversal(BT->Right, count);
- if(count == 1){
- printf("%d", BT->Data);
- count++;
- }
- else
- printf("%d", BT->Data);
- }
- return count;
- }
这样就实现了第一个数和之后的数输出格式的不同
来源: http://www.bubuko.com/infodetail-2533660.html