完整代码:以c语言用二叉链实现二叉树的创建、二叉树的先序/中序/后序递归遍历、统计二叉树的高度、统计结点的个数、叶子结点的个数、先序/中序非递归遍历、层序遍历等运算。
时间: 2024-02-03 11:02:54 浏览: 104
二叉树的遍历.pptx
以下是完整的C语言代码,实现了二叉链表的创建、遍历、统计高度、结点个数、叶子结点个数、非递归遍历和层序遍历等操作。
```c
#include <stdio.h>
#include <stdlib.h>
struct TreeNode {
int data;
struct TreeNode *left;
struct TreeNode *right;
};
// 创建二叉树
struct TreeNode* createBinaryTree(){
int val;
printf("输入结点的值,-1表示空:");
scanf("%d", &val);
if(val == -1){
return NULL;
}else{
struct TreeNode *node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = val;
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}
}
// 先序遍历
void preOrderTraversal(struct TreeNode *root){
if(root != NULL){
printf("%d ", root->data);
preOrderTraversal(root->left);
preOrderTraversal(root->right);
}
}
// 中序遍历
void inOrderTraversal(struct TreeNode *root){
if(root != NULL){
inOrderTraversal(root->left);
printf("%d ", root->data);
inOrderTraversal(root->right);
}
}
// 后序遍历
void postOrderTraversal(struct TreeNode *root){
if(root != NULL){
postOrderTraversal(root->left);
postOrderTraversal(root->right);
printf("%d ", root->data);
}
}
// 层序遍历
void levelOrderTraversal(struct TreeNode *root){
if(root == NULL){
return;
}
struct TreeNode *queue[100];
int front = 0, rear = 0;
queue[rear++] = root;
while(front < rear){
struct TreeNode *node = queue[front++];
printf("%d ", node->data);
if(node->left != NULL){
queue[rear++] = node->left;
}
if(node->right != NULL){
queue[rear++] = node->right;
}
}
}
// 统计二叉树高度
int getHeight(struct TreeNode *root){
if(root == NULL){
return 0;
}else{
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
}
// 统计二叉树结点个数
int getNodeCount(struct TreeNode *root){
if(root == NULL){
return 0;
}else{
return getNodeCount(root->left) + getNodeCount(root->right) + 1;
}
}
// 统计二叉树叶子结点个数
int getLeafNodeCount(struct TreeNode *root){
if(root == NULL){
return 0;
}else if(root->left == NULL && root->right == NULL){
return 1;
}else{
return getLeafNodeCount(root->left) + getLeafNodeCount(root->right);
}
}
// 非递归先序遍历
void preOrderTraversalNonRecursive(struct TreeNode *root){
if(root == NULL){
return;
}
struct TreeNode *stack[100];
int top = -1;
stack[++top] = root;
while(top >= 0){
struct TreeNode *node = stack[top--];
printf("%d ", node->data);
if(node->right != NULL){
stack[++top] = node->right;
}
if(node->left != NULL){
stack[++top] = node->left;
}
}
}
// 非递归中序遍历
void inOrderTraversalNonRecursive(struct TreeNode *root){
if(root == NULL){
return;
}
struct TreeNode *stack[100];
int top = -1;
struct TreeNode *node = root;
while(top >= 0 || node != NULL){
while(node != NULL){
stack[++top] = node;
node = node->left;
}
node = stack[top--];
printf("%d ", node->data);
node = node->right;
}
}
int main(){
struct TreeNode *root = createBinaryTree();
printf("先序遍历:");
preOrderTraversal(root);
printf("\n");
printf("中序遍历:");
inOrderTraversal(root);
printf("\n");
printf("后序遍历:");
postOrderTraversal(root);
printf("\n");
printf("层序遍历:");
levelOrderTraversal(root);
printf("\n");
printf("二叉树高度:%d\n", getHeight(root));
printf("二叉树结点个数:%d\n", getNodeCount(root));
printf("二叉树叶子结点个数:%d\n", getLeafNodeCount(root));
printf("非递归先序遍历:");
preOrderTraversalNonRecursive(root);
printf("\n");
printf("非递归中序遍历:");
inOrderTraversalNonRecursive(root);
printf("\n");
return 0;
}
```
阅读全文