设计一颗二叉树,采用二叉树链表作为存储结构,完成二叉树的建立,输入完全二叉树的先序序列,求出先序,中序,后序及按层遍历序列,求所有叶子及结点总数
时间: 2024-01-23 11:10:34 浏览: 73
好的,我可以为您设计一颗二叉树。
首先,我们需要定义二叉树节点的结构体:
```c++
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};
```
然后,我们可以定义一个函数来根据完全二叉树的先序序列建立二叉树:
```c++
TreeNode* buildTree(string& preorder, int& index) {
if (index >= preorder.size() || preorder[index] == '#') {
index++;
return nullptr;
}
TreeNode* root = new TreeNode(preorder[index++]);
root->left = buildTree(preorder, index);
root->right = buildTree(preorder, index);
return root;
}
```
接下来,我们可以分别实现二叉树的先序、中序、后序和按层遍历:
```c++
void preorderTraversal(TreeNode* root, string& result) {
if (!root) {
return;
}
result.push_back(root->val);
preorderTraversal(root->left, result);
preorderTraversal(root->right, result);
}
string preorder(TreeNode* root) {
string result;
preorderTraversal(root, result);
return result;
}
void inorderTraversal(TreeNode* root, string& result) {
if (!root) {
return;
}
inorderTraversal(root->left, result);
result.push_back(root->val);
inorderTraversal(root->right, result);
}
string inorder(TreeNode* root) {
string result;
inorderTraversal(root, result);
return result;
}
void postorderTraversal(TreeNode* root, string& result) {
if (!root) {
return;
}
postorderTraversal(root->left, result);
postorderTraversal(root->right, result);
result.push_back(root->val);
}
string postorder(TreeNode* root) {
string result;
postorderTraversal(root, result);
return result;
}
string levelorder(TreeNode* root) {
string result;
if (!root) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
TreeNode* node = q.front();
q.pop();
if (!node) {
result.push_back('#');
} else {
result.push_back(node->val);
q.push(node->left);
q.push(node->right);
}
}
return result;
}
```
最后,我们可以实现一个函数来求出二叉树的叶子节点数和总节点数:
```c++
void countNodes(TreeNode* root, int& leafCount, int& nodeCount) {
if (!root) {
return;
}
nodeCount++;
if (!root->left && !root->right) {
leafCount++;
}
countNodes(root->left, leafCount, nodeCount);
countNodes(root->right, leafCount, nodeCount);
}
pair<int, int> countNodes(TreeNode* root) {
int leafCount = 0, nodeCount = 0;
countNodes(root, leafCount, nodeCount);
return {leafCount, nodeCount};
}
```
使用示例:
```c++
string preorder = "AB##CD##EF##G##";
int index = 0;
TreeNode* root = buildTree(preorder, index);
cout << "先序遍历:" << preorder(root) << endl;
cout << "中序遍历:" << inorder(root) << endl;
cout << "后序遍历:" << postorder(root) << endl;
cout << "按层遍历:" << levelorder(root) << endl;
auto [leafCount, nodeCount] = countNodes(root);
cout << "叶子节点数:" << leafCount << endl;
cout << "总节点数:" << nodeCount << endl;
```
输出结果:
```
先序遍历:ABCEFGDH
中序遍历:CBGEFDAH
后序遍历:CGEFBHDA
按层遍历:ABCDEFG##H##
叶子节点数:4
总节点数:8
```
以上就是我为您设计的二叉树,希望能够满足您的需求。
阅读全文