c语言二叉树的先序,中序,后序遍历

2024年2月4日发(作者：)

c语言二叉树的先序,中序,后序遍历

1、先序遍历

先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果

先序遍历结果为：A B D H I E J C F K G

2、中序遍历

中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果

中遍历结果为：H D I B E J A F K C G

3、后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。

还记得我上面提到先序遍历绕圈的路线么？（不记得翻上面理解）

就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。

后序遍历中，根节点默认最后面

后序遍历结果：H I D J E B K F G C A

4、口诀

先序遍历： 先根 再左 再右

中序遍历： 先左 再根 再右

后序遍历： 先左 再右 再根

这里的根，指的是每个分叉子树（左右子树的根节点）根节点，并不只是最开始头顶的根节点，需要灵活思考理解

5、代码展示

#include

#include

typedef 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){ // 输入-1 代表此节点下子树不存数据，也就是不继续递归创建

return NULL;

}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) //

递归中遇到NULL，返回上一层节点

{

return;

}

printf("%d ",T->data);

ShowXianXu(T->lchild); // 递归遍历左子树

ShowXianXu(T->rchild); // 递归遍历右子树

}

// 中序遍历

void ShowZhongXu(BitTree T)

历二叉树

{

if(T==NULL)

递归中遇到NULL，返回上一层节点

{

return;

}

ShowZhongXu(T->lchild);

左子树

printf("%d ",T->data);

ShowZhongXu(T->rchild);

右子树

}

// 后序遍历

void ShowHouXu(BitTree T)

二叉树

{

if(T==NULL)

递归中遇到NULL，返回上一层节点

{

return;

}

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;

}

//

//

中后序