树的遍历（前序、中序、后序）

前序遍历的思想：先遍历根节点，在遍历左节点，最后遍历右节点。

中序遍历的思想：先遍历左节点，在遍历根节点，最后遍历右节点

后序遍历的思想：先遍历左节点，在遍历右节点，最后遍历根节点

光这么说太过于抽象，就举个例子说一下。

树的遍历（前序、中序、后序）

前序遍历：首先遍历根节点所以输出1，然后左节点，发现左节点也是一个根节点就输出2，在遍历2的左节点，输出4，

然后就到右节点了，此时以2为根节点，所以右节点是5，以5为根节点，输出其左节点7.在以1位根节点输出其右节点3,3的左节点是6.

所以是1245736

中序遍历：先遍历1的左子树也就是2，发现2还有左子树接着遍历2的左子树也就是4，输出4,4没有左子树了所以输出根节点，也就是2，然后遍历2的右子树5，5又有左子树7，7没有左子树了所以输出7，然后输出7的根节点5，就此左子树输出完毕，所以输出根节点1,然后遍历1的右节点3，3有左节点先输出左节点6，在输出3。

所以是4275163

后序遍历也是类似值是最先输出的不一样。

#include<stdlib.h>
#include<stdio.h>
#include<memory.h>

//建立二叉树的节点
typedef struct BiTNode
{
int data;
struct BiTNode* lchild, *rchild;
}BiTNode;

//前序遍历
void preOrder(BiTNode *root)
{
   if (root == NULL)
   {
       return;
   }
   printf("%d ",root->data);
   preOrder(root->lchild);
   preOrder(root->rchild);
}
//中序遍历
void inOrder(BiTNode *root)
{
   if (root == NULL)
   {
       return;
   }
   inOrder(root->lchild);
   printf("%d ", root->data);
   inOrder(root->rchild);
}
//后序遍历
void postOrder(BiTNode *root)
{
   if (root == NULL)
   {
       return;
   }
   postOrder(root->lchild);
   postOrder(root->rchild);
   printf("%d ", root->data);
}
void main()
{
   //初始化节点
   BiTNode t1, t2, t3, t4, t5;
   memset(&t1, 0, sizeof(BiTNode));
   memset(&t2, 0, sizeof(BiTNode));
   memset(&t3, 0, sizeof(BiTNode));
   memset(&t4, 0, sizeof(BiTNode));
   memset(&t5, 0, sizeof(BiTNode));

   t1.data = 1;
   t2.data = 2;
   t3.data = 3;
   t4.data = 4;
   t5.data = 5;

   t1.lchild = &t2;
   t1.rchild = &t3;
   t2.rchild = &t4;
   t3.lchild = &t5;
   //遍历
   printf("preOrder ");
   preOrder(&t1);
   printf("\ninOrder ");
   inOrder(&t1);
   printf("\npostOrder ");
   postOrder(&t1);
   system("pause");
}

树的遍历（前序、中序、后序）

相关推荐