DevSONG | 欢迎来到DevSONG个人博客

上一篇文章说到了二叉树，简单实现了一下二叉树的基本操作，用常规的递归思想测试了二叉树的遍历。本篇文章我们来探讨一下二叉树的非递归遍历。【提示：请忽略文章中 “结点”“节点”的混用，懒得改了，输入法承担一半责任】二叉树的非递归遍历除了前、中、后序遍历外，还有一个层序遍历。前三者常用堆栈辅助完成遍历过程，层序遍历则借助队列完成。本篇文章只探讨前中后三种遍历算法的非递归实现。在此之前，我们需要准备一个可用的“堆栈”。堆栈不用多解释了，实现方式很多，每个人的写法和实现思路或许都会有一些不一样，但是只要能达到设计目 ”后进先出“ 就行了。此处我也简单实现了一下，简单测试完毕，不排除有潜在问题，仅供参考： stack.h #ifndef STACK_H #define STACK_H #include "misc.h" #include <stdio.h> #include <stdlib.h> stack_t * initStack(); void traverseStackReverse(stack_t * stack, void (*callBack)()); void traverseStack(stack_t * stack, void (*callBack)()); int isStackEmpty(stack_t *stack); stackDataType popData(stack_t *stack); int pushData(stack_t *stack, stackDataType data); stackDataType getTopData(stack_t *stack); void destroyStack(stack_t **stack); #endif // STACK_H 由于此次测试需要用到上一篇中二叉树相关的东西，所以增加了一个额外的文件：misc.h #ifndef MISC_H #define MISC_H typedef int dataType; //数据类型，简单测试，将 DataType 设置为 int //节点类型 typedef struct nodeData{ struct nodeData *leftChild; struct nodeData *rightChild; dataType data; }node_t; //堆栈数据类型 typedef node_t stackDataType; //堆栈数据结点结构 typedef struct stackNode{ struct stackNode *pre; struct stackNode *next; stackDataType data; }stackNode_t; //堆栈结点类型 //堆栈结构 typedef struct myStack{ int size; stackNode_t *node; stackNode_t * stackPointer; }stack_t; #endif // MISC_H stack.c #include "stack.h" /** *初始化堆栈 */ stack_t * initStack(){ stack_t *temp = (stack_t *)malloc(sizeof(stack_t)); if(temp == NULL){ printf("\nERROR : memory initial error!\n"); return NULL; } temp->size = 0; temp->stackPointer = NULL; temp->node = NULL; return temp; } /** *入栈操作 */ int pushData(stack_t *stack, stackDataType data){ if(stack == NULL){ printf("\nERROR: stack is NULL\n"); return -1; } if(stack->size == 0){ stack->node = (stackNode_t *)malloc(sizeof(stackNode_t)); if(stack->node == NULL){ printf("\nERROR : push data failed, memory initial error!\n"); return -1; } stack->node->next = NULL; stack->node->pre = NULL; stack->node->data = data; stack->size++; stack->stackPointer = stack->node; return 0; } stack->stackPointer->next = (stackNode_t *)malloc(sizeof(stackNode_t)); if(stack->stackPointer->next == NULL){ printf("\nERROR : push data failed, memory initial error!\n"); return -1; } stack->size++; stack->stackPointer->next->data = data; stack->stackPointer->next->pre = stack->stackPointer; stack->stackPointer->next->next = NULL; stack->stackPointer = stack->stackPointer->next; return 0; } /** *弹出栈顶元素 */ stackDataType popData(stack_t *stack){ if(stack == NULL){ printf("\nERROR: stack is NULL!\n"); return; } if(stack->size <= 0){ printf("\nERROR: stack is empty!\n"); return; } stackNode_t *temp = stack->stackPointer; stack->stackPointer = stack->stackPointer->pre; if(stack->stackPointer != NULL){ stack->stackPointer->next = NULL; } stack->size--; sizeof(temp->data); return temp->data; free(temp); } /** *获取栈顶元素 */ stackDataType getTopData(stack_t *stack){ if(stack == NULL){ printf("\nERROR: stack is NULL!\n"); return; } if(stack->size <= 0){ printf("\nERROR: stack is empty!\n"); return; } return stack->stackPointer->data; } /** *堆栈是否为空 *@return int ：空 ----- 1 ：非空 ----- 0 */ int isStackEmpty(stack_t *stack){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return -1; } return stack->size == 0 1 : 0; } /** *堆栈元素遍历 */ void traverseStack(stack_t * stack, void (*callBack)()){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return; } if(stack->size == 0){ printf("\nWARNING : stack is empty\n"); return; } stackNode_t *temp = stack->stackPointer; while(temp != NULL){ callBack(temp->data); temp = temp->pre; } } /** *堆栈元素遍历（反序） */ void traverseStackReverse(stack_t * stack, void (*callBack)()){ if(stack == NULL){ printf("\nERROR:stack is NULL\n"); return; } if(stack->size == 0){ printf("\nWARNING : stack is empty\n"); return; } stackNode_t *temp = stack->node; while(temp != NULL){ callBack(temp->data); temp = temp->next; } } /** *销毁堆栈 */ void destroyStack(stack_t **stack){ if(*stack == NULL){ return; } if((*stack)->size != 0){ stackNode_t *temp = (*stack)->node; stackNode_t *temp1 = temp; while(temp != NULL){ temp1 = temp; temp = temp->next; free(temp1); } } free(*stack); *stack = NULL; } 测试：main函数 int main(){ node_t *p; //初始化 node_t *tree = initBiTree(); tree->data = 10; p = insertRightChildByData(tree, 20); p = insertLeftChildByData(p, 50); insertRightChildByData(p, 60); insertLeftChildByData(p, 70); p = insertLeftChildByData(tree, 30); insertLeftChildByData(p, 40); /*构建了如下结构的二叉树 10 / \ 30 20 / / 40 50 / \ 70 60 */ //遍历输出 printf("============= 二叉树遍历（递归方式） ===========\n"); puts("former: "); formerTraversal(tree, visitNodeAction); puts("\nin: "); inTraversal(tree, visitNodeAction); puts("\nafter: "); afterTraversal(tree, visitNodeAction); /*********** 堆栈测试 ***********/ printf("\n\n============= 堆栈测试 ===========\n"); stackDataType data1 = {NULL, NULL, 1}; stackDataType data2 = {NULL, NULL, 2}; stackDataType data3 = {NULL, NULL, 3}; //构建堆栈 stack_t *stack = initStack(); pushData(stack, data1); pushData(stack, data2); pushData(stack, data3); //输出堆栈 printf("size: %d\n", stack->size); traverseStack(stack, visitStack); puts(""); traverseStackReverse(stack, visitStack); //获取栈顶元素 printf("\ntop data: %d\n", getTopData(stack).data); //弹出栈顶元素 printf("data: %d\n", popData(stack).data); printf("size: %d\n", stack->size); traverseStack(stack, visitStack); puts(""); traverseStackReverse(stack, visitStack); printf("\n\n============= 结合堆栈进行二叉树非递归遍历 ===========\n"); /******** 结合堆栈进行二叉树非递归遍历 *********/ puts("前序遍历（非递归）:"); preOrder(tree, visitNodeAction); puts("\n中序遍历（非递归）:"); inOrder(tree, visitNodeAction); puts("\n后序遍历（非递归）:"); postOrder(tree, visitNodeAction); //销毁二叉树 destroyBiTree(&tree); //销毁堆栈 destroyStack(&stack); return 0; } 以上只是部分代码，如果您觉得网页不便查看代码，可以下载完整源文件：点击此处下载前序（先序）遍历先序遍历比较简单，也容易理解，只要保证根节点在子节点之前访问即可。实现步骤：（1）初始化堆栈（2）将根节点入栈（3）当堆栈非空时，循环执行 a、b、c 三步： a、出站一个结点，访问该节点 b、若该节点的右孩子节点非空，则入栈该节点的右孩子节点 c、若该节点的左孩子节点非空，则入栈该节点的左孩子结点（4）结束 C语言实现： /** *前序（先序）遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void preOrder(node_t *tree, void (*callback)()){ stack_t *stack = initStack(); node_t temp; pushData(stack, *tree); while(!isStackEmpty(stack)){ temp = popData(stack); callback(&temp); if(temp.rightChild != NULL){ pushData(stack, *temp.rightChild); } if(temp.leftChild != NULL){ pushData(stack, *temp.leftChild); } } destroyStack(&stack); } 中序遍历实现步骤：（1）初始化堆栈（2）当临时结点不为空或者堆栈不为空的情况下循环执行以下操作： a、若临时节点不为空将临时结点指向的当前节点入栈，并让当前节点指向其左孩子节点 b、若临时结点为空，则出栈一个元素，访问该元素，之后让当前节点指向出栈元素的右孩子节点（3）结束遍历 C语言实现： /** *中序遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void inOrder(node_t *tree, void (*callback)()){ stack_t *stack = initStack(); node_t *node = tree; node_t temp; while(node != NULL || !isStackEmpty(stack)){ if(node != NULL){ pushData(stack, *node); node = node->leftChild; }else{ temp = popData(stack); callback(&temp); node = temp.rightChild; } } destroyStack(&stack); } 后序遍历后序遍历相交于以上两者而言稍微复杂了一些，如果依旧用一个堆栈来操作的话过程很繁琐，期间还需要对一些节点作标记。注意到后序遍历对比前序遍历的反向过程非常类似，所以可以借助两个堆栈，堆栈一主要是做一个临时枢纽，每个节点都先入堆栈一，不作访问，堆栈2保留最终待访问的顺序，最后依次输出堆栈2进行访问即可。【或许我描述的不够准确，直接看代码即可】 C语言实现 /** *后序遍历（非递归方式） *@param tree : 待遍历二叉树根节点 *@param callack : 回调函数 */ void postOrder(node_t *tree, void (*callback)()){ //利用两个堆栈进行操作 stack_t *stack = initStack(); stack_t *stackParent = initStack(); node_t node; pushData(stack, *tree); //细心的你可能会发现此步骤和前序遍历有些相似 //实际上原理一致，仔细对比前序遍历和后序遍历的过程，它们很相似，##但又不仅仅是直接反序那么简单## while(!isStackEmpty(stack)){ node = popData(stack); pushData(stackParent, node); //此处必须左孩子结点在右孩子结点之前入栈， //因为后面出站再入栈（stackParent）又会有一个顺序的转变 //只有这样才能保证最终遍历结果是正确的（此处体现“但又不仅仅是直接反序那么简单”这句话） if(node.leftChild != NULL){ pushData(stack, *node.leftChild); } if(node.rightChild != NULL){ pushData(stack, *node.rightChild); } } while(!isStackEmpty(stackParent)){ node = popData(stackParent); callback(&node); } //销毁堆栈 destroyStack(&stack); destroyStack(&stackParent); } 测试结果： ============= 二叉树遍历（递归方式） =========== former: 10 30 40 20 50 70 60 in: 40 30 10 70 50 60 20 after: 40 30 70 60 50 20 10 ============= 堆栈测试 =========== size: 3 3 2 1 1 2 3 top data: 3 data: 3 size: 2 2 1 1 2 ============= 结合堆栈进行二叉树非递归遍历 =========== 前序遍历（非递归）: 10 30 40 20 50 70 60 中序遍历（非递归）: 40 30 10 70 50 60 20 后序遍历（非递归）: 40 30 70 60 50 20 10 总结以上简单实现了一下二叉树的非递归遍历，对比递归方式的实现，非递归还是显得有些麻烦。当然并不是说非递归实现不好，此处没有孰好孰坏的说法，只有合不合适的说法。递归固然方便理解和实现且速度快，但是其有一个不可忽视的缺点，那就是内存占用很大，如果一棵非常大的二叉树用常规的递归算法去遍历，每一个结点都是一次递归的调用，这样下来会占用非常大的内存资源，非递归实现对于内存的占用则好很多。所以不同情况下对于遍历算法的选择也是有很多考虑因素的。完整源文件在文章中已给出链接。此外查看系列文章只需点击文章下面的标签即可以上只是我个人的见解，能力有限，难免会出错，若您发现问题或者您有不同看法，欢迎留言。【原创内容，转载请注明出处】

数据结构可分为线性结构和非线性结构两大类。本篇文章讨论的二叉树属于树形结构之一，树形结构属于非线性结构。注意：树和二叉树不是包含关系。二叉树不是树的特例，二者是树形结构的两种不同类型，不存在包含关系。之所以在此总结二叉树，是因为堆排序等等常用算法涉及到二叉树，并且二叉树也是一个必备的数据结构基础知识。在树形结构中，每个节点允许有一个直接前驱节点，但允许有一个以上的直接后继节点。树的存储结构和操作实现都比较复杂，但可以将其转化为二叉树处理。常用术语（1）满二叉树：在二叉树中，若所有的双亲结点都存在叶子结点，且所有子结点都在同一层上，这样的二叉树叫做满二叉树。（2）完全二叉树：若一棵具有n个结点的二叉树的结构与满二叉树的前n个结点的结构相同，则称这样的二叉树为完全二叉树。二叉树的存储结构二叉树的存储结构主要有三种：顺序存储结构、链式存储结构和仿真指针存储结构。（1）顺序存储结构顺序存储是指将二叉树的结点用数组按照一定的规律存储起来。容易想象：当二叉树为完全二叉树的时候，存储为线性结构方便操作且节省空间。但是若要存储的二叉树不是完全二叉树的时候，要想正确存储二叉树，存储结构中就要添加 “空节点” 占位（因为计算子节点的位置需要用到下标），大量的空节点出现显然是不太适合的。所以，对于完全二叉树，采用线性存储结构是不错的选择。若不是完全二叉树，但与完全二叉树相差很小的时候，由于需要添加的空节点数量很少，所以也可以用线性存储结构，相差很大的话就得另寻它法了。（2）二叉树的链式存储结构二叉树的链式存储结构就是用指针来描述结点之间的关系。最常用的就是 “二叉链”，二叉链结构的每个节点通常包含三个域：左孩子指针域leftChild，数据域data，右孩子指针域rightChild。 [leftChild | data | rightChild] 二叉链操作简单，可以方便地构建各种形状的二叉树。缺点是查找当前节点的双亲结点比较麻烦（为此出现了三叉链，在二叉链的基础上增加了一个指向双亲结点的指针域）。（3）二叉树的仿真指针存储结构仿真指针用到的是数组下标，leftChild和rightChild中均存储孩子结点所在的数组下标，这样就通过数组下标建立了一个指向关系。这个思想理解起来也比较简单，这里就不细说了。本篇主要讨论最常用的的结构：二叉树的链式存储结构 C语言实现及测试：首先是头文件：tree.h #ifndef TREE_H #define TREE_H #include <stdio.h> #include <stdlib.h> typedef int dataType; //数据类型，简单测试，将 DataType 设置为 int //节点类型 typedef struct nodeData{ struct nodeData *leftChild; struct nodeData *rightChild; dataType data; }node_t; node_t * initBiTree(); int insertLeftChildNode(node_t * currNode, node_t *childNode); int insertRightChildNode(node_t * currNode, node_t *childNode); node_t * insertLeftChildByData(node_t *currNode, dataType data); node_t * insertRightChildByData(node_t *currNode, dataType data); //警告及错误输出 void printError(char *error); void printWarning(char *warning); //销毁 void destroyBiTree(node_t **rootNode); //前序遍历（递归方式） void formerTraversal(node_t * node, void (*nodeAction)()); //中序遍历（递归方式） void inTraversal(node_t * node, void (*nodeAction)()); //后序遍历（递归方式） void afterTraversal(node_t * node, void (*nodeAction)()); node_t * deleteRightChild(node_t * currNode); node_t * deleteLeftChild(node_t * currNode); #endif 其次是tree.c: #include "tree.h" /** \brief 初始化二叉树 * \return */ node_t * initBiTree(){ node_t *root = (node_t*)malloc(sizeof(node_t)); root->leftChild = NULL; root->rightChild = NULL; root->data = 0; return root; } /** \brief 通过已存在节点为当前节点插入左子节点 * * \param currNode : 目标节点 * \param childNode : 待插入子节点 * \return */ int insertLeftChildNode(node_t * currNode, node_t *childNode){ if(currNode == NULL){ printError("current Node is NULL"); return -1; } if(childNode == NULL){ printError("child node is NULL"); return -1; } if(currNode->leftChild != NULL){ printError("current node's leftChild is already exists"); return -1; } currNode->leftChild = childNode; return 0; } /** \brief 通过已存在节点为当前节点插入右子节点 * * \param currNode : 目标节点 * \param childNode : 待插入子节点 * \return */ int insertRightChildNode(node_t * currNode, node_t *childNode){ if(currNode == NULL){ printError("current Node is NULL"); return -1; } if(childNode == NULL){ printError("child node is NULL"); return -1; } if(currNode->rightChild != NULL){ printError("current node's rightChild is already exists"); return -1; } currNode->rightChild = childNode; return 0; } /** \brief 通过数据为当前节点插入左节点 * * \param currNode : 目标节点 * \param data : 待插入数据 * \return */ node_t * insertLeftChildByData(node_t *currNode, dataType data){ if(currNode == NULL){ printError("current node is NULL"); return NULL; } if(currNode->leftChild != NULL){ printError("current node's leftChild is already exists"); return NULL; } //空间初始化 node_t * temp = (node_t *)malloc(sizeof(node_t)); if(temp == NULL){ printError("memory initial error!"); return NULL; } temp->leftChild = NULL; temp->rightChild = NULL; temp->data = data; currNode->leftChild = temp; return temp; } /** \brief 通过数据为当前节点插入右节点 * * \param currNode : 目标节点 * \param data : 待插入数据 * \return */ node_t * insertRightChildByData(node_t *currNode, dataType data){ if(currNode == NULL){ printError("current node is NULL"); return NULL; } if(currNode->rightChild != NULL){ printError("current node's rightChild is already exists"); return NULL; } //空间初始化 node_t * temp = (node_t *)malloc(sizeof(node_t)); if(temp == NULL){ printError("memory initial error!"); return NULL; } //注意每次插入新节点都要初始化 temp->leftChild = NULL; temp->rightChild = NULL; temp->data = data; currNode->rightChild = temp; return temp; } /** \brief 删除当前节点的左节点 * * \param currNode : 目标节点 * \return */ node_t * deleteLeftChild(node_t * currNode){ if(currNode == NULL){ printWarning("current node is NULL."); return NULL; } if(currNode->leftChild == NULL){ printError("the left child node which you want to delete is NULL"); return NULL; } //直接调用销毁函数，若节点后面还有子节点，则销毁的是一整棵子树 destroyBiTree(&currNode->leftChild); return currNode; } /** \brief 删除当前节点的右节点 * * \param currNode : 目标节点 * \return */ node_t * deleteRightChild(node_t * currNode){ if(currNode == NULL){ printWarning("current node is NULL."); return NULL; } if(currNode->rightChild == NULL){ printError("the right child node which you want to delete is NULL"); return NULL; } //直接调用销毁函数，若节点后面还有子节点，则销毁的是一整棵子树 destroyBiTree(&currNode->rightChild); return currNode; } /** \brief 先序（前序）遍历 * * \param node : 二叉树根节点 * \param nodeAction : 回调函数 * \return * */ void formerTraversal(node_t * node, void (*nodeAction)()){ if(node == NULL){ printWarning("the node you want to traverse is NULL"); return; } nodeAction(node); if(node->leftChild != NULL){ formerTraversal(node->leftChild, nodeAction); } if(node->rightChild != NULL){ formerTraversal(node->rightChild, nodeAction); } } /** \brief 中序遍历 * * \param node : 二叉树根节点 * \param nodeAction : 回调函数 * \return * */ void inTraversal(node_t * node, void (*nodeAction)()){ if(node == NULL){ printWarning("the node you want to traverse is NULL"); return; } if(node->leftChild != NULL){ inTraversal(node->leftChild, nodeAction); } nodeAction(node); if(node->rightChild != NULL){ inTraversal(node->rightChild, nodeAction); } } /** \brief 后序遍历 * * \param node : 二叉树根节点 * \param nodeAction : 回调函数 * \return * */ void afterTraversal(node_t * node, void (*nodeAction)()){ if(node == NULL){ printWarning("the node you want to traverse is NULL"); return; } if(node->leftChild != NULL){ afterTraversal(node->leftChild, nodeAction); } if(node->rightChild != NULL){ afterTraversal(node->rightChild, nodeAction); } nodeAction(node); } /** \brief 销毁二叉树 * * \param node : 二叉树根节点 * \return * */ void destroyBiTree(node_t **rootNode){ if(rootNode == NULL || *rootNode == NULL){ printWarning("the node which you want to destroy is NULL"); return; } if((*rootNode)->leftChild != NULL){ destroyBiTree(&(*rootNode)->leftChild); } if((*rootNode)->rightChild != NULL){ destroyBiTree(&(*rootNode)->rightChild); } free(*rootNode); *rootNode = NULL; } /** * 组织错误输出 * *@param error : 错误信息 */ void printError(char *error){ printf("### ERROR: "); printf("%s", error); printf("\n"); } /** * 组织警告输出 * *@param warning : 警告信息 */ void printWarning(char *warning){ printf("## WARNING: "); printf("%s", warning); printf("\n"); } 最后是main.c执行测试： #include "tree.h" /** *自定义回调函数，遍历时使用 */ void visitNodeAction(node_t * node){ if(node == NULL){ printf("node is null!\n"); } printf(" %d ",node->data); } int main(){ node_t *p; //初始化 node_t *tree = initBiTree(); tree->data = 10; p = insertRightChildByData(tree, 20); p = insertLeftChildByData(p, 50); insertRightChildByData(p, 60); p = insertLeftChildByData(tree, 30); insertLeftChildByData(p, 40); /*构建了如下结构的二叉树 10 / \ 30 20 / / 40 50 \ 60 */ //遍历输出 puts("former: "); formerTraversal(tree, visitNodeAction); puts("\nin: "); inTraversal(tree, visitNodeAction); puts("\nafter: "); afterTraversal(tree, visitNodeAction); //销毁 destroyBiTree(&tree); return 0; } 上述测试运行结果：总结上述展示了基本的二叉树操作，包括结点的插入、删除、遍历（递归方式）、销毁等。二叉树的遍历也存在很多学问，实现方式也有很多，用递归实现是很简洁的，也是很基础的。借助其他常用的数据结构也可以用非递归的思路来做。在以后的文章中会有总结。另外，此处用的测试数据非常简单，只是简单的整形数据，实际中根据需求更改DataType即可。以上只是我个人见解，欢迎留言，欢迎吐槽，欢迎分享。【原创内容，转载请注明出处】