创建二叉树/ void CreatBiTree(BiTree& T) { char ch; scanf("%c", &ch); getchar(); if (ch == '#') { T = NULL; } else { T = (BiTNode*)malloc(sizeof(BiTNode)); T->data = ch; printf("请输入%c的左子树:\n", ch); CreatBiTree(T->lchild); printf("请输入%c的右子树:\n", ch); CreatBiTree(T->rchild); } }
时间: 2024-04-22 10:22:20 浏览: 19
这是一个递归函数,用于创建一个二叉树。它的参数是一个指向二叉树根节点的指针。函数中通过读入字符来创建二叉树,如果读入的字符是 '#',则表示该节点为空,否则就创建一个新的节点,并为其赋值。然后递归调用函数来创建该节点的左右子树。整个过程是按照前序遍历的顺序进行的,即先创建根节点,再创建左子树,最后创建右子树。
相关问题
void creat(BiTree &Tree)//构建二叉树 void PostOrder(BiTree Tree)//输出后缀表达式
好的,我可以为你提供一个C++的实现。
首先,我们需要定义二叉树的节点结构体。
```cpp
struct TreeNode {
char val; // 节点的值,这里假设是字符类型
TreeNode* left; // 左子节点
TreeNode* right; // 右子节点
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
```
然后,我们可以按照前缀表达式的顺序构建二叉树。
```cpp
void creat(TreeNode* &Tree) {
char val;
cin >> val;
if (val == '#') { // 如果输入的是 #,表示这个节点是空节点
Tree = nullptr;
} else {
Tree = new TreeNode(val); // 创建一个新的节点
creat(Tree->left); // 构建左子树
creat(Tree->right); // 构建右子树
}
}
```
最后,我们可以按照后序遍历的顺序输出后缀表达式。
```cpp
void PostOrder(TreeNode* Tree) {
if (Tree == nullptr) {
return;
}
PostOrder(Tree->left); // 输出左子树的后缀表达式
PostOrder(Tree->right); // 输出右子树的后缀表达式
cout << Tree->val << " "; // 输出根节点的值
}
```
完整的代码如下:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
void creat(TreeNode* &Tree) {
char val;
cin >> val;
if (val == '#') {
Tree = nullptr;
} else {
Tree = new TreeNode(val);
creat(Tree->left);
creat(Tree->right);
}
}
void PostOrder(TreeNode* Tree) {
if (Tree == nullptr) {
return;
}
PostOrder(Tree->left);
PostOrder(Tree->right);
cout << Tree->val << " ";
}
int main() {
TreeNode* root;
creat(root);
PostOrder(root);
return 0;
}
```
当你输入前缀表达式并按回车键后,程序会输出后缀表达式。注意,输入的表达式中操作数必须是单个字符,操作符可以是加减乘除等常见的运算符,但是不支持括号。
用C语言写void InOrder(BiTree Tree)//中序遍历 void creat(BiTree &Tree)//构建二叉树
下面是用C语言实现的中序遍历函数和构建二叉树函数的代码:
```
//定义二叉树结构体
typedef struct BiTNode {
char data;
struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;
//中序遍历函数
void InOrder(BiTree Tree) {
if (Tree) {
InOrder(Tree->lchild);
printf("%c ", Tree->data);
InOrder(Tree->rchild);
}
}
//构建二叉树函数(先序遍历输入)
void creat(BiTree &Tree) {
char ch;
scanf("%c", &ch);
if (ch == '#') {
Tree = NULL;
} else {
Tree = (BiTree)malloc(sizeof(BiTNode));
Tree->data = ch;
creat(Tree->lchild);
creat(Tree->rchild);
}
}
```
在构建二叉树时,我们采用先序遍历的方式输入二叉树的结点,如果输入的结点值为`#`,表示该结点为空,否则就创建一个新的结点,并将该结点的左右子树递归构建。在中序遍历时,我们按照“左子树-根结点-右子树”的顺序遍历二叉树,并输出每个结点的值。