建立二叉树,并用递归和非递归两种方法实现二叉树的先序、中序、后序遍历。用C语言
时间: 2024-03-12 13:45:14 浏览: 22
好的,我会根据你的要求回答你的问题。
首先,我们需要定义二叉树的结构体,包括节点值、左右子树指针:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
接下来,我们定义一个函数来创建二叉树,该函数需要输入一个数组和数组的长度,返回一个指向根节点的指针。我们的二叉树是按照完全二叉树的形式存储的,即从上到下,从左到右逐层存储。
```c
TreeNode* createTree(int* arr, int len) {
TreeNode* root = NULL;
for (int i = 0; i < len; i++) {
TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = arr[i];
node->left = NULL;
node->right = NULL;
if (root == NULL) {
root = node;
}
else {
TreeNode* parent = root;
int flag = 0;
while (parent != NULL) {
if (i % 2 == 0) {
parent = parent->left;
}
else {
parent = parent->right;
}
flag++;
i /= 2;
}
if (flag > 2) {
i *= 2;
flag /= 2;
parent = root;
while (flag > 1) {
if (i % 2 == 0) {
parent = parent->left;
}
else {
parent = parent->right;
}
flag--;
i /= 2;
}
if (i % 2 == 0) {
parent->left = node;
}
else {
parent->right = node;
}
}
else {
if (i % 2 == 0) {
parent->left = node;
}
else {
parent->right = node;
}
}
}
}
return root;
}
```
接下来是二叉树的递归遍历,分别实现先序遍历、中序遍历、后序遍历:
```c
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->val);
preorderTraversal(root->left);
preorderTraversal(root->right);
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->val);
inorderTraversal(root->right);
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf("%d ", root->val);
}
```
接下来是二叉树的非递归遍历,同样分别实现先序遍历、中序遍历、后序遍历:
```c
void preorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[1000];
int top = -1;
stack[++top] = root;
while (top != -1) {
TreeNode* node = stack[top--];
printf("%d ", node->val);
if (node->right != NULL) {
stack[++top] = node->right;
}
if (node->left != NULL) {
stack[++top] = node->left;
}
}
}
void inorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[1000];
int top = -1;
TreeNode* node = root;
while (node != NULL || top != -1) {
while (node != NULL) {
stack[++top] = node;
node = node->left;
}
node = stack[top--];
printf("%d ", node->val);
node = node->right;
}
}
void postorderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[1000];
int top = -1;
TreeNode* node = root;
TreeNode* pre = NULL;
while (node != NULL || top != -1) {
while (node != NULL) {
stack[++top] = node;
node = node->left;
}
node = stack[top];
if (node->right == NULL || node->right == pre) {
printf("%d ", node->val);
top--;
pre = node;
node = NULL;
}
else {
node = node->right;
}
}
}
```
以上就是建立二叉树并实现递归和非递归遍历的全部内容,希望能对你有所帮助。