建立一个二叉树,并能分别利用先序、中序、后序和层次四种不同的遍历方法输出结点元素。
时间: 2024-05-11 09:19:23 浏览: 47
首先,我们需要定义二叉树的结构体和结点结构体:
```c
typedef struct TreeNode{
char data; // 结点元素
struct TreeNode* left; // 左子树指针
struct TreeNode* right; // 右子树指针
}TreeNode, *BiTree;
```
其中,`data` 为结点的元素,`left` 和 `right` 分别为左子树和右子树的指针。
接下来,我们可以通过递归的方式实现二叉树的建立:
```c
BiTree createTree(){
char ch;
scanf("%c", &ch); // 读入一个字符
if(ch == '#'){ // 如果是 #,表示该结点为空结点,返回 NULL
return NULL;
}
BiTree root = (BiTree)malloc(sizeof(TreeNode)); // 创建一个新结点
root->data = ch; // 将字符赋值给结点元素
root->left = createTree(); // 递归创建左子树
root->right = createTree(); // 递归创建右子树
return root; // 返回根结点
}
```
其中,`#` 表示空结点。
接下来,我们分别实现先序、中序、后序和层次遍历:
```c
// 先序遍历
void preOrder(BiTree root){
if(root == NULL){ // 如果结点为空,返回
return;
}
printf("%c ", root->data); // 输出结点元素
preOrder(root->left); // 递归遍历左子树
preOrder(root->right); // 递归遍历右子树
}
// 中序遍历
void inOrder(BiTree root){
if(root == NULL){ // 如果结点为空,返回
return;
}
inOrder(root->left); // 递归遍历左子树
printf("%c ", root->data); // 输出结点元素
inOrder(root->right); // 递归遍历右子树
}
// 后序遍历
void postOrder(BiTree root){
if(root == NULL){ // 如果结点为空,返回
return;
}
postOrder(root->left); // 递归遍历左子树
postOrder(root->right); // 递归遍历右子树
printf("%c ", root->data); // 输出结点元素
}
// 层次遍历
void levelOrder(BiTree root){
if(root == NULL){ // 如果结点为空,返回
return;
}
queue<BiTree> q; // 创建一个队列存储结点
q.push(root); // 将根结点入队
while(!q.empty()){
BiTree node = q.front(); // 取出队首结点
q.pop();
printf("%c ", node->data); // 输出结点元素
if(node->left != NULL){ // 如果左子树不为空,将左子树入队
q.push(node->left);
}
if(node->right != NULL){ // 如果右子树不为空,将右子树入队
q.push(node->right);
}
}
}
```
最后,我们可以在 `main()` 函数中调用这些函数进行测试:
```c
int main(){
BiTree root = createTree(); // 创建二叉树
printf("先序遍历:");
preOrder(root); // 先序遍历
printf("\n中序遍历:");
inOrder(root); // 中序遍历
printf("\n后序遍历:");
postOrder(root); // 后序遍历
printf("\n层次遍历:");
levelOrder(root); // 层次遍历
printf("\n");
return 0;
}
```
阅读全文