二叉树的前序遍历的非递归实现

冷不防 2022-12-27 01:14 47阅读 0赞

我们知道二叉树的遍历主要有，前序，中序，后续，我们常用递归的方式进行实现，而我们都知道能用递归函数实现，都可以用数据结构栈进行实现。

下面我们就用栈的数据结构来处理二叉树的前序遍历：

BinaryTree.h

#pragma once
    struct 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;
    }