C语言实现二叉树遍历：先序、中序、后序

#include <stdio.h> #include <malloc.h>

struct BTNode { char data; struct BTNode * pLchild; //p是指针 L是左 child是孩子 struct BTNode * pRchild; };

void PostTraverseBTree(struct BTNode * pT); struct BTNode * CreateBTree(void); void PreTraverseBTree(struct BTNode * pT); void InTraverseBTree(struct BTNode * pT);

int main(void) { struct BTNode * pT = CreateBTree();

// PreTraverseBTree(pT); // InTraverseBTree(pT); PostTraverseBTree(pT);

return 0;

}

void PostTraverseBTree(struct BTNode * pT) { if (NULL != pT) { if (NULL != pT->pLchild) { PostTraverseBTree(pT->pLchild); } if (NULL != pT->pRchild) { PostTraverseBTree(pT->pRchild); //pT->pLchild可以代表整个左子树 } printf('%c\n', pT->data); } }

void InTraverseBTree(struct BTNode * pT) { if (NULL != pT) { if (NULL != pT->pLchild) { InTraverseBTree(pT->pLchild); }

	printf('%c\n', pT->data);

	if (NULL != pT->pRchild)
	{
			InTraverseBTree(pT->pRchild);
		//pT->pLchild可以代表整个左子树
	}	
}

}

void PreTraverseBTree(struct BTNode * pT) { if (NULL != pT) { printf('%c\n', pT->data);

	if (NULL != pT->pLchild)
	{
		PreTraverseBTree(pT->pLchild);
	}
	
	if (NULL != pT->pRchild)
	{
			PreTraverseBTree(pT->pRchild);
		//pT->pLchild可以代表整个左子树
	}	
}	

/* 伪算法 先访问根节点 再先序访问左子树 再先序访问右子树 */ }

struct BTNode * CreateBTree(void) { struct BTNode * pA = (struct BTNode *)malloc(sizeof(struct BTNode)); struct BTNode * pB = (struct BTNode *)malloc(sizeof(struct BTNode)); struct BTNode * pC = (struct BTNode *)malloc(sizeof(struct BTNode)); struct BTNode * pD = (struct BTNode *)malloc(sizeof(struct BTNode)); struct BTNode * pE = (struct BTNode *)malloc(sizeof(struct BTNode));

PA->data = 'A';
pB->data = 'B';
pC->data = 'C';
pD->data = 'D';
pE->data = 'E';

PA->pLchild = pB;
PA->pRchild = pC;
pB->pLchild = pB->pRchild = NULL;
pC->pLchild = pD;
pC->pRchild = NULL;
pD->pLchild = NULL;
pD->pRchild = pE;
pE->pLchild = pE->pRchild = NULL;

return pA;

}

这段代码是一个二叉树的实现。它定义了一个二叉树节点结构体'BTNode'，包含一个字符型数据和左右子节点的指针。代码中实现了三种不同的遍历方式：先序遍历、中序遍历和后序遍历。

在'CreateBTree'函数中，创建了一个简单的二叉树结构，并返回根节点指针。树中共有5个节点，按照先序遍历的顺序依次为A、B、C、D、E。

'PreTraverseBTree'函数实现了先序遍历，按照根节点、左子树、右子树的顺序递归遍历节点，并打印节点的数据。

'InTraverseBTree'函数实现了中序遍历，按照左子树、根节点、右子树的顺序递归遍历节点，并打印节点的数据。

'PostTraverseBTree'函数实现了后序遍历，按照左子树、右子树、根节点的顺序递归遍历节点，并打印节点的数据。

在'main'函数中，调用'CreateBTree'创建了一个二叉树，然后依次调用三种遍历函数进行遍历。

需要注意的是，这段代码的输出结果是按照不同的遍历方式打印出节点的数据，每个节点数据占一行。运行代码后可以观察到不同遍历方式的结果。