关于二叉树迭代建立

骇客king

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

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

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

ryxcaixia

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

醉酒青牛2011

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

骇客king

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

yjip267

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

骇客king

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

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

骇客king

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

ryxcaixia

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

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

yjip267

G没有看到。呵呵

骇客king

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

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

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

骇客king

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

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

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

骇客king

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

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

ryxcaixia

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

正解