leadcode的Hot100系列--二叉树创建和遍历

很多题目涉及到二叉树，所以先把二叉树的一些基本的创建和遍历写一下，方便之后的本地代码调试。
为了方便，这里使用的数据为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");
}