二叉树的四种遍历方式

我不是女神ヾ 2022-12-26 11:21 119阅读 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 PreorderTraverseTree(const BinaryTreeNode* pRoot);
    
    //中序打印二叉树
    void InorderTraverseTree(const BinaryTreeNode* pRoot);
    
    //后序打印二叉树
    void PostorderTraverseTree(const BinaryTreeNode* pRoot);
    
    //层序打印二叉树
    void LayerTraverseTree(BinaryTreeNode* pRoot);
    
    //二叉树结点的销毁
    void DestroyBinaryNode(struct BinaryTreeNode*node);
    
    //整个二叉树的销毁
    void DestroyBinary(struct BinaryTreeNode*node);

BinaryTree.cpp代码如下：

#include"BinaryTree.h"
    #include<cstdio>
    #include<queue>
    //二叉树结点的创建
    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 PreorderTraverseTree(const BinaryTreeNode* pRoot)
    {
    	PrintBinaryNode(pRoot);
    
    	if (pRoot != nullptr)
    	{
    		if (pRoot->m_left != nullptr)
    			PreorderTraverseTree(pRoot->m_left);
    
    		if (pRoot->m_right != nullptr)
    			PreorderTraverseTree(pRoot->m_right);
    	}
    
    }
    //中序遍历打印二叉树
    void InorderTraverseTree(const BinaryTreeNode* pRoot)
    {
    	if (pRoot != nullptr)
    	{
    		if (pRoot->m_left != nullptr)
    			InorderTraverseTree(pRoot->m_left);
    
    		PrintBinaryNode(pRoot);
    
    		if (pRoot->m_right != nullptr)
    			InorderTraverseTree(pRoot->m_right);
    	}
    }
    
    //后续遍历二叉树
    void PostorderTraverseTree(const BinaryTreeNode* pRoot)
    {
    	if (pRoot != nullptr)
    	{
    		if (pRoot->m_left != nullptr)
    			PostorderTraverseTree(pRoot->m_left);
    
    		
    
    		if (pRoot->m_right != nullptr)
    			PostorderTraverseTree(pRoot->m_right);
    
    		PrintBinaryNode(pRoot);
    	}
    }
    
    //层序遍历二叉树
    void LayerTraverseTree(BinaryTreeNode* pRoot)
    {
    	if (pRoot == nullptr)
    	{
    		return;
    	}
    	std::queue<struct BinaryTreeNode*> Nodequeue;
    	Nodequeue.push(pRoot);
    
    	while (Nodequeue.size() > 0)
    	{
    		struct BinaryTreeNode*tmpnode = Nodequeue.front();
    		Nodequeue.pop();
    		//打印值
    		printf("node value[%d]\n", tmpnode->m_value);
    		if (tmpnode->m_left != nullptr)
    		{
    			Nodequeue.push(tmpnode->m_left);
    		}
    		if (tmpnode->m_right != nullptr)
    		{
    			Nodequeue.push(tmpnode->m_right);
    		}
    	}
    
    }
    
    
    //二叉树结点的销毁
    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);
    		}
    
    
    	}
    }

测试代码如下：

#include"BinaryTree.h"
    #include<cstdio>
    
    //手动的创建如下树
    /*
    		 8
    	  /    \
    	 6	    10
       /  \    /  \
      5	   7   9   11
    */
    
    int main(int argc, char*argv[])
    {
    	struct BinaryTreeNode* node1 = CreateBinaryNode(8);
    	struct BinaryTreeNode* node2 = CreateBinaryNode(6);
    	struct BinaryTreeNode* node3 = CreateBinaryNode(10);
    	struct BinaryTreeNode* node4 = CreateBinaryNode(5);
    	struct BinaryTreeNode* node5 = CreateBinaryNode(7);
    	struct BinaryTreeNode* node6 = CreateBinaryNode(9);
    	struct BinaryTreeNode* node7 = CreateBinaryNode(11);
    
    
    	ConnectBinaryNode(node1, node2, node3);
    	ConnectBinaryNode(node2, node4, node5);
    	ConnectBinaryNode(node3, node6, node7);
    
    	//先序遍历
    	printf("preorder start\n");
    	PreorderTraverseTree(node1);
    	printf("inorder start\n");
    	InorderTraverseTree(node1);
    	printf("postorder start\n");
    	PostorderTraverseTree(node1);
    	printf("layerorder start\n");
    	LayerTraverseTree(node1);
    
    	return 0;
    }

程序的输出结果如下所示：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70][]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poYW5naHVhaWNoYW8_size_16_color_FFFFFF_t_70]: /images/20221120/710c565db82a4f488d9840a06d1e30a9.png