二叉树的前序遍历的非递归实现
我们知道二叉树的遍历主要有，前序，中序，后续，我们常用递归的方式进行实现，而我们都知道能用递归函数实现，都可以用数据结构栈进行实现。
下面我们就用栈的数据结构来处理二叉树的前序遍历：
BinaryTree.h
#pragma oncestruct BinaryTreeNode{int m_value;struct BinaryTreeNode* m_left;struct BinaryTreeNode* m_right;};//二叉树结点的创建struct BinaryTreeNode* CreateBinaryNode(int value);//二叉树结点的连接void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild);//二叉树结点的打印void PrintBinaryNode(const struct BinaryTreeNode*node);//前序非递归打印二叉树void PreorderTraverseTreeNonRec(BinaryTreeNode* pRoot);//二叉树结点的销毁void DestroyBinaryNode(struct BinaryTreeNode*node);//整个二叉树的销毁void DestroyBinary(struct BinaryTreeNode*node);BinaryTree.cpp如下所示：
#include"BinaryTree.h"#include<cstdio>#include<queue>#include<stack>//二叉树结点的创建struct BinaryTreeNode* CreateBinaryNode(int value){struct BinaryTreeNode*pNode = new BinaryTreeNode();pNode->m_value = value;pNode->m_left = nullptr;pNode->m_right = nullptr;return pNode;}//二叉树结点的连接void ConnectBinaryNode(struct BinaryTreeNode*Parent, struct BinaryTreeNode* lchild, struct BinaryTreeNode* rchild){if (Parent != NULL){Parent->m_left = lchild;Parent->m_right = rchild;}}//二叉树结点的打印void PrintBinaryNode(const struct BinaryTreeNode*node){if (node != nullptr){printf("node value is[%d]\n",node->m_value);}else{printf("this node is nullptr\n");}}//前序遍历二叉树非递归 采用栈的数据结构void PreorderTraverseTreeNonRec(BinaryTreeNode* pRoot){std::stack<struct BinaryTreeNode*> stacknode;if (pRoot != nullptr){stacknode.push(pRoot);while (!stacknode.empty()){BinaryTreeNode* tmp = stacknode.top();//打印值printf("value is[%d]\n",tmp->m_value);stacknode.pop();if (tmp->m_right) { stacknode.push(tmp->m_right);}if (tmp->m_left) {stacknode.push(tmp->m_left);}}}}//二叉树结点的销毁void DestroyBinary(struct BinaryTreeNode*node){if (node != nullptr){struct BinaryTreeNode*pleft = node->m_left;struct BinaryTreeNode*pright = node->m_right;delete node;node = nullptr;if (pleft != nullptr){DestroyBinary(pleft);}if (pright != nullptr){DestroyBinary(pright);}}}测试代码如下：
int main(int argc, char*argv[]){struct BinaryTreeNode* node1 = CreateBinaryNode(10);struct BinaryTreeNode* node2 = CreateBinaryNode(6);struct BinaryTreeNode* node3 = CreateBinaryNode(14);struct BinaryTreeNode* node4 = CreateBinaryNode(4);struct BinaryTreeNode* node5 = CreateBinaryNode(8);struct BinaryTreeNode* node6 = CreateBinaryNode(12);struct BinaryTreeNode* node7 = CreateBinaryNode(16);ConnectBinaryNode(node1, node2, node3);ConnectBinaryNode(node2, node4, node5);ConnectBinaryNode(node3, node6, node7);//非递归先序遍历printf("preorder no rec start\n");PreorderTraverseTreeNonRec(node1);return 0;} 赞 (0)