二叉树的知识点

发表于 | 分类于

typedef struct node
{
ElemType data;
struct node leftchild;
struct node rightchild;
}tree;

/创建/

1
2
3
4
5
6
7
8
9
10
11
12
13
void creat(tree *&t)
{
    ElemType data;
    data=getchar();
    if(data=='#')
        t=NULL;
    else{
        t=(tree *)malloc(sizeof(tree));
        t->data=data;
        creat(t->leftchild);
        creat(t->righthcild);
    }
}

/遍历/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
void preordertraverse(tree *t)
{
    if(t)
    {
        printf("%c",t->data);
        preordertraverse(t->leftchild);
        preordertraverse(t->rightchild);
    }
}
void inordertraverse(tree *t)
{
    if(t)
    {
        inordertraverse(t->leftchild);
        printf("%c",t->data);
        inordertraverse(t->rightchild);
    }
}
void posordertraverse(tree *t)
{
    if(t)
    {
        posordertraverse(t->leftchild);
        posordertraverse(t->rightchild);
        printf("%c",t->data);
    }
}

/二叉树的深度/

1
2
3
4
5
6
7
8
9
10
11
12
13
in depthoftree(tree *t)
{
    int leftdepth;
    int rightdepth;
    if(!t)
    {
        return 0;
    }
    leftdepth=depthoftree(tree->leftchild);
    rightdepth=depthoftree(tree->rightchild);
    return (leftdepth>=rightdepth)?(leftdepth+1):(rightdepth+1);
}

/二叉树的节点的个数/

1
2
3
4
5
6
7
8
9
10
11
12
13
int leafcount(tree *t,int num)
{
    if(t)
    {
        if(!t->leftchild&&!t->rightchild)
            num++;
        leafcount(t->leftchild);
        leafcount(t->rightchild);
    }
    return num;
}

/求另一种遍/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct node *ans(int len,char *st1,char *st2)
{
    tree *root;
    int i;
    if(len==0)
    {
        return NULL;
    }
    root=(struct node *)malloc(sizeof(struct node));
    root->data=st1[0];
    for(i=0;i<len;i++)
    {
        if(st2[i]==root->data)
        {
            break;
        }
    }
    root->leftchild=ans(i,st1+1,st2);
    root->rightchild=ans(len-i-1,st1+i+1,st2+i+1);
    return root;
};
Fork me on GitHub