【数据结构】【C/C++】创建二叉树-链式存储-C和C++双语教学_二叉树的链式存储c++

一、C语言–链式存储二叉树的创建

1、用二叉链表存储，定义结构体

typedef struct BiTreeNode//定义结构体
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;//左孩子
    struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
1
2
3
4
5
6

2、递归先序创建二叉树

void CreateBiTree(BiTree *T)//要改变指针，所以要把指针的地址传进来
{
    ElemType ch;
    
    scanf("%d", &ch);//注意数据类型
    getchar();//吸收空格或者回车
    if (ch == -1)
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTreeNode));
        
        if (!(*T))//检查是否分配成功
            exit(-1);
            
        (*T)->data = ch;
        CreateBiTree(&(*T)->lChild);//printf("输入%d的左孩子：", ch);
        CreateBiTree(&(*T)->rChlid);//printf("输入%d的右孩子：", ch);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

3、完整代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>

typedef int  ElemType; //数据类型

typedef struct BiTreeNode//定义结构体
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;//左孩子
    struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree *T)//要改变指针，所以要把指针的地址传进来
{
    ElemType ch;
    
    scanf("%d", &ch);//注意数据类型
    getchar();//吸收空格或者回车
    if (ch == -1)
        *T = NULL;
    else
    {
        *T = (BiTree)malloc(sizeof(BiTreeNode));
        
        if (!(*T))//检查是否分配成功
            exit(-1);
            
        (*T)->data = ch;
        CreateBiTree(&(*T)->lChild);//printf("输入%d的左孩子：", ch);
        CreateBiTree(&(*T)->rChlid);//printf("输入%d的右孩子：", ch);
    }
}
int main(void)
{
    BiTree T;

    printf("请输入先序遍历顺序下各个结点的值,-1表示没有结点:\n");
    CreateBiTree(&T);
    
    return 0;
}
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
30
31
32
33
34
35
36
37
38
39
40
41
42

二、C+±-链式存储二叉树的创建

1、用二叉链表存储，定义结构体

typedef int  ElemType; //数据类型

typedef struct BiTreeNode//定义结构体
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;//左孩子
    struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
1
2
3
4
5
6
7
8

2、递归先序创建二叉树
与c语言的区别是，传参时候可以把指针的引用传进来，可以不用malloc分配空间，用new分配，后面的代码更加简洁。

void CreateBiTree(BiTree &T)//要改变指针，C++可以把指针的引用传进来
{
    ElemType ch;

    cin >> ch;

    if (ch == -1)
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data = ch;
        CreateBiTree(T->lChild);//cout<<"输入"<<ch<<"的左孩子：" ;
        CreateBiTree(T->rChlid);//cout<<"输入"<<ch<<"的右孩子：" ;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

3、完整代码

#include<iostream>

using namespace std;

typedef int  ElemType; //数据类型

typedef struct BiTreeNode//定义结构体
{
    ElemType  data; //数据域
    struct BiTreeNode *lChild;//左孩子
    struct BiTreeNode *rChlid;//右孩子
} BiTreeNode, *BiTree;
//先序创建二叉树
void CreateBiTree(BiTree &T)//要改变指针，C++可以把指针的引用传进来
{
    ElemType ch;

    cin >> ch;

    if (ch == -1)
        T = NULL;
    else
    {
        T = new BiTreeNode;
        T->data = ch;
        CreateBiTree(T->lChild);//cout<<"输入"<<ch<<"的左孩子：" ;
        CreateBiTree(T->rChlid);//cout<<"输入"<<ch<<"的右孩子：" ;
    }
}
int main(void)
{
    BiTree T;

    cout<<"请输入先序遍历顺序下各个结点的值,-1表示没有结点:"<<endl;
    CreateBiTree(T);

    return 0;
}

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
30
31
32
33
34
35
36
37
38
39