设为首页 加入收藏

TOP

leadcode的Hot100系列--二叉树创建和遍历
2019-07-02 14:13:07 】 浏览:25
Tags: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");
}

编程开发网
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇C语言-main方法的两个参数是干什.. 下一篇leadcode的Hot100系列--617. 合并..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

array(4) { ["type"]=> int(8) ["message"]=> string(24) "Undefined variable: jobs" ["file"]=> string(32) "/mnt/wp/cppentry/do/bencandy.php" ["line"]=> int(217) }