骇客king 发表于 2015-8-17 14:34:40

关于二叉树迭代建立

CreateBiTree(BiTree *T)
{
        char c;

        scanf("%c", &c);
        if( ' ' == c )
        {
                *T = NULL;
        }
        else
        {
                *T = (BiTNode *)malloc(sizeof(BiTNode));
                (*T)->data = c;
                CreateBiTree(&(*T)->lchild);
                CreateBiTree(&(*T)->rchild);
        }
}

假设我的输入位AB ECF 回车。
这个建立过程是什么样的,我怎么觉得建立过程是建立到E后,然后又以E为双亲建立的C呢?
麻烦给讲解一下~

ryxcaixia 发表于 2015-8-17 14:34:41

                     A
                B         C
          D      E   F    G
树要理解到什么程度?
很多大公司面试题就喜欢考树 因为链表已经考烂了
比如给你个stdlib.h stdio.h让你实现一个STL的map容器和set容器
这俩容器底层就是红黑树实现的 我们那一年360的笔试题校招

而对于压缩算法如图片压缩视频压缩 又是霍夫曼树的延伸
如果是想应付笔试面试 拿来清华严蔚敏的数据结构习题集 紫色封皮那个 含金量超级高
把树的哪一章里面所有的所有习题算法自己上机实现一遍 不但内功大涨 而且90%公司的树这块的笔试面试是没问题了

ryxcaixia 发表于 2015-8-18 08:27:36

说的对 以E为双亲 建立了C F 不过E这个双亲是B的右孩子, B的左孩子为空, 即输入的那个空格

醉酒青牛2011 发表于 2015-8-18 15:09:14

这个题目有些熟悉啊,楼主你先看看二叉树相关知识,应该很好解决的,我好久没看了,帮顶

骇客king 发表于 2015-8-18 15:59:51

我输入写错误了,应该是ABD(两个空格)E(两个空格)CF(两个空格)G(两个个空格),我想这样是不是我就建立了一个满二叉树,也是完全二叉树了,我也明白了递归调用遇到空格返回上一层节点,最后一层是返回到根节点,我都能理解,也看懂,但是自己写不出来,还需要理解到什么程度呢?

yjip267 发表于 2015-8-18 17:22:14

个人感觉是这样的
                                  A
                  B                                     C
       D               E                     F
中左右:ABDECF

骇客king 发表于 2015-8-18 17:45:01

yjip267 发表于 2015-8-18 17:22
个人感觉是这样的
                                  A
                  B                           ...

你这个应该是完全二叉树,不是满二叉树,少了一个G

骇客king 发表于 2015-8-18 17:54:06

纯属个人爱好,喜欢搞这些东西,没想过啥面试,也不可能去哪个公司当程序员,只想自己写些东西给自己用,但是很想深入学习,认识电脑到底是什么,能干什么,哈哈~
这个上机是关键哈,不能光看不练啊~

ryxcaixia 发表于 2015-8-18 17:56:39

骇客king 发表于 2015-8-18 17:54
纯属个人爱好,喜欢搞这些东西,没想过啥面试,也不可能去哪个公司当程序员,只想自己写些东西给自己用,但 ...

妥妥的
清华大学严蔚敏 数据结构+配套习题集
提升内功神器

yjip267 发表于 2015-8-19 08:39:26

G没有看到。呵呵

骇客king 发表于 2015-8-19 11:55:11

本帖最后由 骇客king 于 2015-8-19 12:03 编辑

ryxcaixia 发表于 2015-8-17 14:34
A
                B         C
          D      E   F    G


CreateBiTree(&(*T)->lchild);这个地方没有理解,(*T)->lchild是一个没有初始化地址,不是应该把下一个节点地址给(*T)->lchild吗?这样(*T)->lchild才能指向下一个节点,但是&(*T)->lchild是什么意思呢,那进入下一次递归*T = (BiTNode *)malloc(sizeof(BiTNode));新生成的节点需要被 (*T)->lchild啊是在这重新赋值了吗?


是不是这么理解,&(*T)->lchild取地址之后,进入下一次递归*T = (BiTNode *)malloc(sizeof(BiTNode))给这个传进来地址赋值为新生成节点的地址,这样(*T)->lchild里边放的内容就是新生成节点的地址了,就指向了。

typedef struct BiThrNode
{
        char data;
        struct BiThrNode *lchild, *rchild;
        PointerTag ltag;
        PointerTag rtag;
} BiThrNode, *BiThrTree;

这个结构为什么要过搞一个指针出来呢,就定义一个BiThrNode不行吗?然后程序里边自己控制指针,是不是能方便一些,和清晰一些呢?
求大神给解释一下啊?

ryxcaixia 发表于 2015-8-19 12:48:30

1. CreateBiTree(&(*T)->lchild); 传入的指针是一个未初始化的 他的初始化在函数内部 即你可以丢一个空指针进去 函数内部代为分配内存

2. BiThrNode 这个应该是线索二叉树的节点, ltag rtag分别标志当前的左右节点是否已经被线索化 即是否可以直接找到该节点的前驱和后继

骇客king 发表于 2015-8-19 13:37:16

ryxcaixia 发表于 2015-8-19 12:48
1. CreateBiTree(&(*T)->lchild); 传入的指针是一个未初始化的 他的初始化在函数内部 即你可以丢一个空指针 ...

那可不可以理解为传入的是一个地址,但是这个地址指向的空间是未被初始化的,进入函数内部后,把这个地址指向的空间赋值为一个地址(指向节点的地址)~

就像scanf("%d",&a);这个意思~

骇客king 发表于 2015-8-19 13:37:54

骇客king 发表于 2015-8-19 13:37
那可不可以理解为传入的是一个地址,但是这个地址指向的空间是未被初始化的,进入函数内部后,把这个地址 ...

就像scanf("%d",&a);这个意思~

ryxcaixia 发表于 2015-8-19 13:56:11

骇客king 发表于 2015-8-19 13:37
就像scanf("%d",&a);这个意思~

正解
页: [1]
查看完整版本: 关于二叉树迭代建立