先序遍历
先序遍历可以想象为,一个小人从一棵二叉树的根节点为起点,沿着二叉树的外沿,逆时针走一圈回到根节点,路上遇到的元素顺序,就是先序遍历的结果
先序遍历的结果为:A B D H I E J C F K G
中序遍历
中序遍历可以看成,二叉树每个节点,垂直方向投影下来(可以理解为每个节点从最左边开始垂直掉到地上),然后从左往右数,得出的结果便是中序遍历的结果
中序遍历的结果是:H D I B E J A F K C G
后序遍历
后序遍历就像是剪葡萄,我们要把一串葡萄剪成一颗一颗的。就是围着树的外围绕一圈,如果发现一剪刀就能剪下的葡萄(必须是一颗葡萄)(也就是葡萄要一个一个掉下来,不能一口气掉超过1个这样),就把它剪下来,组成的就是后序遍历了
后序遍历的结果是:H I D J E B K F G C A
层次遍历
层次遍历就是从根节点开始,一层一层,从上到下,每层从左到右,依次写值就可以
层次遍历的结果是:A B C D E F G H I J K
解释跑外圈的意思:
绕着外围跑一整圈的真正含义是:遍历所有节点时,都先往左孩子走,再往右孩子走
口诀:
先序遍历:先根,再左,再右
中序遍历:先左,再根,再右
后序遍历:先左,再右,再根
(这里的根,指的是每个分叉子树的根节点,并不只是最开始头顶的根节点,需要灵活思考理解)
代码展示:
#include<stdio.h>#include<stdlib.h>typrdef struct Tree{int data;//存放数据域 struct Tree *lchild;//遍历左子树指针 struct Tree *rchild;//遍历右子树指针 }Tree,*BitTree;BitTree CreateLink(){int data;int temp;BitTree T;scanf("%d",&data);//输入数据 temp=getchar();//吸收空格if(data==-1){return NULL;//输入-1代表此节点下子树不存数据,也就是不继续递归创建 }else{T=(BitTree)malloc(sizeof(Tree));//分配内存空间 T->data=data;//把当前输入的数据存入当前节点指针的数据域中 printf("请输入%d的左子树:",data);T->lchild=CreateLink();//开始递归创建左子树 printf("请输入%d的右子树:",data);T->rchild=CreateLink();//开始到上一级节点的右边递归创建左右子树 return T;//返回根节点 } }//先序遍历 void ShowXianXu(BitTree T)//先序遍历二叉树 {if(T==NULL) return;//递归中遇到NULL,返回上一层节点 printf("%d ",T->data);ShowXianXu(T->lchild);//递归遍历左子树 ShowXianXu(T->rchild);//递归遍历右子树 }//中序遍历void ShowZhongXu(BitTree T){if(T==NULL) return;//递归中遇到NULL,返回上一层节点 ShowZhongXu(T->lchild);//递归遍历左子树printf("%d ",T->data);ShowZhongXu(T->rchild);//递归遍历右子树}//后序遍历void ShowHouXu(BitTree T){if(T==NULL) return;//递归中遇到NULL,返回上一层节点ShowHouXu(T->lchild);//递归遍历左子树 ShowHouXu(T->rchild);//递归遍历右子树 printf("%d ",T->data);}int main(){BitTree S;printf("请输入第一个节点的数据:\n");S = CreateLink();//接受创建二叉树完成的根节点 printf("先序遍历结果: \n");ShowXianXu(S);//先序遍历二叉树 printf("\n中序遍历结果: \n");ShowZhongXu(S);//中序遍历二叉树 printf("\n后序遍历结果: \n");ShowHouXu(S);//后序遍历二叉树 return 0;}
树结点定义:
typedef struct TNode *Position;typedef Position BinTree;//二叉树类型struct TNode{ElementType Data;BinTree Left;BinTree Right;};
先序遍历:
先访问根节点先序遍历其左子树先序遍历其右子树
void PreorderTraversal(BinTree BT){if(BT){printf("%d",BT->Data);PreorderTraversal(BT->Left);PreorderTraversal(BT->Right);}}
中序遍历:
先序遍历其左子树先访问根节点先序遍历其右子树
void InorderTraversal(BinTree BT){if(BT){InorderTraversal(BT->Left);printf("%d",BT->Data);InorderTraversal(BT->Right);}}
后序遍历:
先序遍历其左子树先序遍历其右子树先访问根节点
void PostorderTraversal(BinTree BT){if(BT){PostorderTraversal(BT->Left);PostorderTraversal(BT->Right);printf("%d",BT->Data);}}