用c语言编写一个程序,要求:建立以左右孩子链接结构表示的二叉树,实现二叉树的先序、中序、后序的递归和非递归方式遍历,分层遍历、统计树的高度
时间: 2024-02-12 09:09:02 浏览: 77
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
好的,这是一个比较典型的二叉树的遍历问题。我可以给您提供一个参考实现,帮助您理解二叉树的遍历。
首先,我们需要定义二叉树的结构体,包括节点的值、左右子节点的指针。代码如下:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
```
接下来,我们可以定义一个函数来创建二叉树,输入参数是一个整型数组,表示二叉树的层次遍历顺序,-1 表示空节点。这个函数的返回值是一个指向根节点的指针。代码如下:
```c
TreeNode* createTree(int* arr, int len) {
if (len == 0) {
return NULL;
}
TreeNode** nodes = (TreeNode**)malloc(len * sizeof(TreeNode*));
for (int i = 0; i < len; i++) {
if (arr[i] == -1) {
nodes[i] = NULL;
} else {
nodes[i] = (TreeNode*)malloc(sizeof(TreeNode));
nodes[i]->val = arr[i];
}
}
int j = 1;
for (int i = 0; i < len && j < len; i++) {
if (nodes[i]) {
nodes[i]->left = nodes[j++];
if (j < len) {
nodes[i]->right = nodes[j++];
}
}
}
TreeNode* root = nodes[0];
free(nodes);
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 preorderTraversalNonrecursive(TreeNode* root) {
if (root == NULL) {
return;
}
Stack* stack = createStack();
push(stack, root);
while (!isEmpty(stack)) {
TreeNode* node = (TreeNode*)pop(stack);
printf("%d ", node->val);
if (node->right) {
push(stack, node->right);
}
if (node->left) {
push(stack, node->left);
}
}
destroyStack(stack);
}
void inorderTraversalNonrecursive(TreeNode* root) {
if (root == NULL) {
return;
}
Stack* stack = createStack();
TreeNode* node = root;
while (node || !isEmpty(stack)) {
while (node) {
push(stack, node);
node = node->left;
}
node = (TreeNode*)pop(stack);
printf("%d ", node->val);
node = node->right;
}
destroyStack(stack);
}
void postorderTraversalNonrecursive(TreeNode* root) {
if (root == NULL) {
return;
}
Stack* stack = createStack();
push(stack, root);
Stack* result = createStack();
while (!isEmpty(stack)) {
TreeNode* node = (TreeNode*)pop(stack);
push(result, node);
if (node->left) {
push(stack, node->left);
}
if (node->right) {
push(stack, node->right);
}
}
while (!isEmpty(result)) {
TreeNode* node = (TreeNode*)pop(result);
printf("%d ", node->val);
}
destroyStack(stack);
destroyStack(result);
}
```
接下来,我们可以实现二叉树的分层遍历。这里我们需要借助一个队列来实现。代码如下:
```c
void levelOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
Queue* queue = createQueue();
enqueue(queue, root);
while (!isEmpty(queue)) {
int size = getSize(queue);
for (int i = 0; i < size; i++) {
TreeNode* node = (TreeNode*)dequeue(queue);
printf("%d ", node->val);
if (node->left) {
enqueue(queue, node->left);
}
if (node->right) {
enqueue(queue, node->right);
}
}
printf("\n");
}
destroyQueue(queue);
}
```
最后,我们可以实现统计二叉树的高度。这个问题可以比较直接地使用递归来解决。代码如下:
```c
int getHeight(TreeNode* root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return 1 + (leftHeight > rightHeight ? leftHeight : rightHeight);
}
```
以上就是一个比较完整的二叉树的遍历问题的实现。希望可以帮助到您!
阅读全文