二叉树链式结构的前序、中序、后序、层序遍历

文章目录

• 一、二叉树创建
• 二、前序遍历
• • 概念以及解释
  • 代码
• 三、中序遍历
• • 概念及解释
  • 代码
• 四、后序遍历
• • 概念及解释
  • 代码
• 五、层序遍历
• • 概念及解释
  • 代码

一、二叉树创建

&mesp; 实现二叉树的遍历，我们要先手搓出一个二叉树，在次基础上实现二叉树的前序、中序、后序、层序遍历。


创建二叉树节点的结构体，包括该节点的值，以及该节点的左节点和右节点。

typedef int BTDataType;

typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

//申请节点
BTNode* BuyNode(int x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc: BuyNode");
		return 0;
	}

	node->data = x;
	node->left = node->right = NULL;
}

//二叉树
BTNode* BinaryTreeCreate()
{
    //创建6个节点
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	node1->left = node2;//1的左节点是2
	node1->right = node4;//1的右节点是4
	node2->left = node3;//2的左节点是3
	node4->left = node5;//4的左节点是5
	node4->right = node6;//4的右节点是6

	return node1;
}

下面是二叉树展示图

                      前序、中序、后序遍历均已递归方式来实现

二、前序遍历

概念以及解释

  前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
  前序遍历打印顺序为：根、左、右

代码

// 二叉树前序遍历 (根  左  右）
void  BinaryTreePrevOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");//为空就打印 N
		return 0;
	}
		
	printf("%d ", root->data);//先打印根节点
	BinaryTreePrevOrder(root->left); //递归遍历左子树
	BinaryTreePrevOrder(root->right);//递归遍历右子树
}

三、中序遍历

概念及解释

  中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中（间）。
  中序遍历打印顺序为：左、根、右

代码

void BinaryTreeInOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return 0;
	}
	BinaryTreeInOrder(root->left);//递归遍历左子树
	printf("%d ", root->data);//打印根节点
	BinaryTreeInOrder(root->right);//递归遍历右子树
}

四、后序遍历

概念及解释

&rmsp;&emsp**;后序遍历**(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
  后序遍历的顺序为左、右、根

代码

// 二叉树后序遍历
void BinaryTreePostOrder(BTNode* root)
{
	if (root == NULL)
	{
		printf("N ");
		return 0;
	}
	BinaryTreePostOrder(root->left);
	BinaryTreePostOrder(root->right);
	printf("%d ", root->data);
}

五、层序遍历

概念及解释

  层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对二叉树进行层序遍历。设二叉树的根结点所在层数为1，层序遍历就是从所在二叉树的根结点出发，首先访问第一层的树根结点，然后从左到右访问第2层上的结点，接着是第三层的结点，以此类推，自上而下，自左至右逐层访问树的结点的过程就是层序遍历。


  层序遍历在图形上比前面三种遍历要清晰明了的多，但是在实现上就比较复杂了。他的实现需要用到队列的实现，队列的相关代码在前的博客中已经详细的介绍过了，所以这里我们直接运用。
队列的实现代码：队列的实现

代码

// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
	Queue q;
	QueueInit(&q);//初始化链表
	if (root != NULL)
	{
		QueuePush(&q, root);//插入链表
	}

	while (!QueueEmpty(&q))
	{
		BTNode* top = QueueFront(&q);//取头节点
		QueuePop(&q);//头节点出队列
		printf("%d ", top->data);

		if (top->left)
		{
			QueuePush(&q, top->left);//插入队列
		}
		if (top->right)
		{
			QueuePush(&q, top->right);//插入队列
		}
	}
	printf("\n");
	QueueDestory(&q);
	
}