(转)二叉树的建立 C语言描述(Establishment of (turn) binary tree c language description)

这篇blog转自笔者的CSDN账号,为笔者学习《数据结构》课程时所撰写,现转至博客园,仅作归档用。
原文的撰写时间是2021-05-14。

学校的《数据结构》教材给出的二叉树的建立算法有点问题,因此自己稍加修改以使之可以使用。

结点定义

typedef int element_type;
typedef struct binary_tree {
    element_type data;
    struct binary_tree *lchild;    //左孩子
    struct binary_tree *rchild;    //右孩子
} BinaryTree;

树的结点数据可以从键盘读入,也可以从文件读入。这里采用从文件读入结点数据的方式,读入的算法不再详述。数据格式为:

[结点数据内容] [是否有左孩子] [是否有右孩子]

比如,一个结点的数据为100,有左孩子,没有右孩子,则可表示为:

100 1 0

文件一行记录一个结点,按照先序遍历的顺序存储行。读取的结果存放在中,存储数据,和存储左孩子和右孩子的情况。

data_line[100][3]
data_line[x][0]
data_line[x][1]
[x][2]

具体实现如下,用了两个函数。要创建树,调用即可。

createBinaryTree()
BinaryTree *createTree(BinaryTree *tree, int data_line[100][3], int *arr_len, int *nRow)
{
    tree->data = data_line[*nRow][0];   //赋值
    tree->lchild = NULL;
    tree->rchild = NULL;

    int nRowCurr = *nRow;               //存储当前行数
    if (data_line[nRowCurr][1] == 1) {
        (*nRow)++;
        tree->lchild = (BinaryTree *)malloc(sizeof(BinaryTree));    //为左孩子分配空间
        createTree(tree->lchild, data_line, arr_len, nRow);
    }
    if (data_line[nRowCurr][2] == 1) {
        (*nRow)++;
        tree->rchild = (BinaryTree *)malloc(sizeof(BinaryTree));    //为右孩子分配空间
        createTree(tree->rchild, data_line, arr_len, nRow);
    }

    if (*nRow + 1 == *arr_len)      //递归的结束条件,结束后返回当前调用栈的tree,即根节点。
        return tree;
    return NULL;            //递归未结束时,返回值没有用,这里随便返回一个NULL
}

int createBinaryTree(BinaryTree **tree)
{
    int arr_len;
    int data_line[100][3];
    int nRow = 0;
    readFile("/mnt/d/WorkSpace/DataStructure/Homework/homework06/data.txt", &arr_len, data_line);
    *tree = (BinaryTree *)malloc(sizeof(BinaryTree));       //先为根节点分配空间
    *tree = createTree(*tree, data_line, &arr_len, &nRow);  //创建根节点的子树

    return arr_len;     //返回这棵树的结点数量
}

那一行是从文件读入数据,这里不再给出。

readFile()

在父结点的调用栈为孩子结点分配空间的原因是为了防止孩子结点的地址丢失。如果每个调用栈只为自身结点分配空间的话,本来孩子结点是,进入孩子结点的调用栈再分配存储空间,则孩子结点的地址要发生变化(从变成一个确定的分配值),而父节点是无法得知这个变化的,这样就会导致地址丢失。

NULL
NULL

Happy Hacking!

参考文献

[1].胡学刚,张先宜.数据结构[M].安徽大学出版社:合肥,2015:134.

————————

This blog was transferred from the author’s CSDN account and was written by the author when learning the course of data structure. Now it is transferred to the blog Garden for archiving only.
The original text was written on May 14, 2021.

The binary tree building algorithm given in the school’s data structure textbook has some problems, so I have slightly modified it to make it usable.

Node definition

typedef int element_type;
typedef struct binary_tree {
    element_type data;
    struct binary_tree *lchild;    //左孩子
    struct binary_tree *rchild;    //右孩子
} BinaryTree;

The node data of the tree can be read from the keyboard or from the file. Here, the node data is read from the file, and the read algorithm will not be described in detail. The data format is:

[node data content] [whether there are left children] [whether there are right children]

For example, if the data of a node is 100, with left children and no right children, it can be expressed as:

100 1 0

Each line of the file records a node, and the lines are stored in the order of first traversal. The read results are stored in the, storing data, and storing the situation of left and right children.

data_line[100][3]
data_line[x][0]
data_line[x][1]
[x][2]

The specific implementation is as follows, using two functions. To create a tree, call.

createBinaryTree()
BinaryTree *createTree(BinaryTree *tree, int data_line[100][3], int *arr_len, int *nRow)
{
    tree->data = data_line[*nRow][0];   //赋值
    tree->lchild = NULL;
    tree->rchild = NULL;

    int nRowCurr = *nRow;               //存储当前行数
    if (data_line[nRowCurr][1] == 1) {
        (*nRow)++;
        tree->lchild = (BinaryTree *)malloc(sizeof(BinaryTree));    //为左孩子分配空间
        createTree(tree->lchild, data_line, arr_len, nRow);
    }
    if (data_line[nRowCurr][2] == 1) {
        (*nRow)++;
        tree->rchild = (BinaryTree *)malloc(sizeof(BinaryTree));    //为右孩子分配空间
        createTree(tree->rchild, data_line, arr_len, nRow);
    }

    if (*nRow + 1 == *arr_len)      //递归的结束条件,结束后返回当前调用栈的tree,即根节点。
        return tree;
    return NULL;            //递归未结束时,返回值没有用,这里随便返回一个NULL
}

int createBinaryTree(BinaryTree **tree)
{
    int arr_len;
    int data_line[100][3];
    int nRow = 0;
    readFile("/mnt/d/WorkSpace/DataStructure/Homework/homework06/data.txt", &arr_len, data_line);
    *tree = (BinaryTree *)malloc(sizeof(BinaryTree));       //先为根节点分配空间
    *tree = createTree(*tree, data_line, &arr_len, &nRow);  //创建根节点的子树

    return arr_len;     //返回这棵树的结点数量
}

That line reads data from the file and is not given here.

readFile()

The reason for allocating space for child nodes in the call stack of parent nodes is to prevent the address loss of child nodes. If each call stack only allocates space for its own node, the original child node is to re allocate storage space into the call stack of the child node, the address of the child node will change (from a certain allocation value), and the parent node cannot know this change, which will lead to address loss.

NULL
NULL

Happy Hacking!

reference

[1]. Hu Xuegang, Zhang Xianyi Data structure [M] Anhui University Press: Hefei, 2015:134