c二叉树的建立与遍历

二叉树是数据结构中的一种，它是由节点和边组成的有向树形结构，其中每个节点最多有两个子节点，分别称为左子节点和右子节点。在实际应用中，二叉树经常被用来存储有层次结构的数据，如文件系统、目录结构等。C语言作为一种强大的编程语言，可以很好地用于实现二叉树的建立和遍历。本文将从多个角度分析C二叉树的建立与遍历。

1. 二叉树的数据结构

C语言是一种基于指针的语言，因此我们可以用指针来实现二叉树的结构。一个二叉树节点通常包含三个部分：数据部分、左子节点指针和右子节点指针。因此我们可以定义一个二叉树节点的结构体如下：

```

typedef struct TreeNode

{

int data;

struct TreeNode* left;

struct TreeNode* right;

} TreeNode;

```

在这个结构体中，data表示该节点存储的数据，left和right分别为左子节点和右子节点的指针。通过这种方式，我们就可以非常方便地定义和操作一个二叉树了。

2. 二叉树的建立

在C语言中，我们可以通过递归的方式来建立一个二叉树。具体来说，我们每次先读取一个输入数据，然后分别递归创建它的左子树和右子树。如果某个节点没有左子树或右子树，那么就将相应的指针设置为NULL。下面是一个建立二叉树的示例代码：

```

TreeNode* createTree()

{

int data;

scanf("%d", &data);

if(data == -1) // 表示该节点为空

{

return NULL;

}

else

{

TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));

node->data = data;

node->left = createTree();

node->right = createTree();

return node;

}

}

```

在这个函数中，我们首先读取一个输入数据，并检查它是否为-1。如果为-1，则表示该节点为空，直接返回NULL。否则，我们创建一个新的节点，并递归创建它的左右子树。最后返回该节点即可。

3. 二叉树的遍历

二叉树的遍历是指按照一定规则依次访问二叉树中的所有节点。常见的遍历方式有三种：前序遍历、中序遍历和后序遍历。下面将分别介绍每种遍历方式的实现方法：

* 前序遍历：先访问根节点，然后依次遍历左右子树。

```

void preOrder(TreeNode* root)

{

if(root == NULL)

{

return;

}

printf("%d ", root->data);

preOrder(root->left);

preOrder(root->right);

}

```

在这个函数中，我们首先输出根节点的数据，然后递归遍历它的左右子树。这样就实现了前序遍历。

* 中序遍历：先遍历左子树，然后访问根节点，最后遍历右子树。

```

void inOrder(TreeNode* root)

{

if(root == NULL)

{

return;

}

inOrder(root->left);

printf("%d ", root->data);

inOrder(root->right);

}

```

在这个函数中，我们先递归遍历左子树，然后输出根节点的数据，最后递归遍历右子树。这样就实现了中序遍历。

* 后序遍历：先遍历左右子树，然后访问根节点。

```

void postOrder(TreeNode* root)

{

if(root == NULL)

{

return;

}

postOrder(root->left);

postOrder(root->right);

printf("%d ", root->data);

}

```

在这个函数中，我们先递归遍历左右子树，然后输出根节点的数据。这样就实现了后序遍历。

综上所述，通过定义二叉树节点结构体、递归方法和遍历函数，我们就可以很方便地实现C二叉树的建立和遍历了。