很多题目涉及到二叉树，所以先把二叉树的一些基本的创建和遍历写一下，方便之后的本地代码调试。
为了方便，这里使用的数据为char类型数值，初始化数据使用一个数组。
因为这些东西比较简单，这里就不做过多详述。
创建
1、定义一些内容：
// 二叉树节点结构体
typedef struct tree_node
{
struct tree_node *pL;
struct tree_node *pR;
char data;
}TREE_NODE_S
// 输入数据的无效值，若读到无效值，则说明该节点为空
#define INVALID -1
// 全局变量，记录当前输入的数组位置
char count = 0
// 在遍历树的时候，需要对data做的操作
typedef void (*pfprocData)(char *p);
2、使用递归方式创建原始二叉树。
其基本思想与先序遍历基本一样，只不过一个是对数据做输出，一个是对数据做输入。
TREE_NODE_S* createNode(char *str)
{
TREE_NODE_S *pTemp = NULL;
char data = *(str+count);
count ++;
if (data != INVALID)
{
pTemp = (TREE_NODE_S *)calloc(1, sizeof(TREE_NODE_S));
if (NULL == pTemp)
{
return pTemp;
}
pTemp->data = data;
pTemp->pL = createNode(str);
pTemp->pR = createNode(str);
}
return pTemp;
}
3、这里再提供一种无返回值、传树的二级指针的创建方法：
createNode2(TREE_NODE_S **p, char *str)
{
TREE_NODE_S *pTemp = NULL;
char data = *(str+count);
count ++;
if (data != INVALID)
{
pTemp = (TREE_NODE_S *)calloc(1, sizeof(TREE_NODE_S));
if (NULL == pTemp)
{
*p = NULL;
return;
}
// 这里直接对指针进行赋值
*p = pTemp;
pTemp->data = data;
createNode2(&(pTemp->pL), str);
createNode2(&(pTemp->pR), str);
}
else
{
*p = NULL;
}
return;
}
遍历
三种常见的前序、中序、后序遍历：
// 这里pfprocData，是用来处理结构体里面的数据部分的函数
void frontOrder(TREE_NODE_S *p, pfprocData pfunc)
{
if (NULL == p)
{
return;
}
pfunc(&(p->data));
frontOrder(p->pL, pfunc);
frontOrder(p->pR, pfunc);
return;
}
void middleOrder(TREE_NODE_S *p, pfprocData pfunc)
{
if (NULL == p)
{
return;
}
middleOrder(p->pL, pfunc);
pfunc(&(p->data));
middleOrder(p->pR, pfunc);
return;
}
void lastOrder(TREE_NODE_S *p, pfprocData pfunc)
{
if (NULL == p)
{
return;
}
lastOrder(p->pL, pfunc);
lastOrder(p->pR, pfunc);
pfunc(&(p->data));
return;
}
测试
// 先创建出如下两种树，然后做遍历输出
// 1
// / \
// 2 4
// \
// 3
char ps1[] = {1, 2, INVALID, 3, INVALID, INVALID, 4, INVALID, INVALID};
// 1
// / \
// 2 6
// / \ \
// 3 5 7
// \
// 4
char ps2[] = {1, 2, 3, INVALID, 4, INVALID, INVALID, 5, INVALID, INVALID, 6, INVALID, 7, INVALID, INVALID};
// 这里只对节点数据进行打印
void procData(char *p)
{
printf("%u ", *p);
}
int main(void)
{
TREE_NODE_S *pstTreeHead1 = NULL;
TREE_NODE_S *pstTreeHead2 = NULL;
pstTreeHead1 = createTree2(ps1);
pstTreeHead2 = createTree2(ps2)
// 如果使用第二个创建方法，则：
// createTree(&pstTreeHead1, ps1);
// createTree(&pstTreeHead2, ps2);
printf("%-14s", "frontOrder:");
frontOrder(pstTreeHead1, procData);
printf("\n");
printf("%-14s", "frontOrder:");
frontOrder(pstTreeHead2, procData);
printf("\n");
printf("%-14s", "middleOrder:");
middleOrder(pstTreeHead2, procData);
printf("\n");
printf("%-14s", "lastOrder:");
lastOrder(pstTreeHead2, procData);
printf("\n");
}