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

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

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

``````

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

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;
*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;
*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