Alternative method to set up a binary tree?

Question

I tried to find the method to establish the binary tree. Almost all existing methods like the following code：

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

such method likes PreOrderTraverse, Is there any other method to establish the binary tree？

The title is very strange, but I don't know how to fix it (i.e. I don't know what to write). — unwind, Jul 03 '15 at 14:14
@unwind: I've edited it - i *think* that's the intended meaning, but I'm not sure! — psmears, Jul 03 '15 at 14:16
I'm guessing this code looks fishy because `BiTree` is a typedef:ed pointer, which is very bad practice, as it makes the code unreadable. — Lundin, Jul 03 '15 at 14:20

score 0 · Answer 1 · edited May 23 '17 at 12:14

0

This:

T = (BiTree)malloc(sizeof(BiTNode));

should probably be

T = malloc(sizeof *T);

Don't cast the return value of malloc() in C, and use sizeof.

Upper-case variable names in C is very rare and quite confusing, and you shouldn't typedef away the pointer asterisk in my opinion.

edited May 23 '17 at 12:14

Community

1
1

answered Jul 03 '15 at 14:12

unwind

391,730
64
469
606

score 0 · Answer 2 · answered Jul 03 '15 at 14:31

I'm guessing BiTree is a pointer hidden behind a typedef? That's very bad practice, because it makes the code unreadable. Change the BiTree typedef to be a plain typedef struct.
Avoid using scanf() or any other complex functions from inside a recursive function, recursion is slow enough without it. (Recursive functions in general are bad because they are so ineffective and hard to read, binary trees is about the only valid use for them.)
Don't cast the return value of malloc.

As for the algorithm itself, you can create a binary tree without recursion, by using a "previous" pointer in every node, pointing upwards in the tree (similar to a double-linked list). Such implementations consume more data memory, because every node must store an additional pointer, but far less stack memory. The concern for stack overflow that comes with recursion is removed. And they execute much faster because the recursion function calling overhead is removed.

Alternative method to set up a binary tree?

2 Answers2