C++根据二叉树的先序序列和中序序列确定二叉树,并画出二叉树的形状,用/和\表示左右子树
时间: 2024-05-25 14:09:04 浏览: 15
根据二叉树的先序序列和中序序列确定二叉树的过程如下:
1. 先序序列的第一个元素是当前二叉树的根节点;
2. 在中序序列中找到该元素,该元素左边的部分是当前根节点的左子树,右边的部分是当前根节点的右子树;
3. 对左子树和右子树分别递归进行上述操作。
下面是一个例子,假设先序序列为ABDECFG,中序序列为DBEAFCG。则:
1. 先序序列的第一个元素为A,因此A是当前二叉树的根节点;
2. 在中序序列中找到A,A左边的部分为DBE,右边的部分为FCG。因此,A的左子树为DBE,右子树为FCG;
3. 对于左子树DBE,先序序列为BDE,中序序列为DBE。其中,B为当前二叉树的左子节点,D为B的右子节点,E为D的右子节点;
4. 对于右子树FCG,先序序列为CFG,中序序列为FCG。其中,C为当前二叉树的右子节点,F为C的左子节点,G为F的右子节点。
因此,该二叉树的形状如下:
```
A
/ \
B C
\ / \
D F G
\
E
```
相关问题
C++根据二叉树的先序序列和中序序列确定二叉树,并画出二叉树的形状,用/和\表示左右子树代码
确定一棵二叉树的过程如下:
1. 先序序列的第一个元素为根节点。
2. 在中序序列中找到根节点,根节点左边的为左子树的中序序列,右边的为右子树的中序序列。
3. 在先序序列中,根节点后面紧跟着的若干个元素为左子树的先序序列,剩余的为右子树的先序序列。
根据以上规则,可以递归构建整棵二叉树。
以下是C++代码实现:
```
#include <iostream>
#include <unordered_map>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
for (int i = 0; i < n; i++) {
map[inorder[i]] = i;
}
return build(preorder, inorder, 0, n - 1, 0, n - 1);
}
private:
unordered_map<int, int> map;
TreeNode* build(vector<int>& preorder, vector<int>& inorder, int preLeft, int preRight, int inLeft, int inRight) {
if (preLeft > preRight) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[preLeft]);
int inRoot = map[root->val];
int numsLeft = inRoot - inLeft;
root->left = build(preorder, inorder, preLeft + 1, preLeft + numsLeft, inLeft, inRoot - 1);
root->right = build(preorder, inorder, preLeft + numsLeft + 1, preRight, inRoot + 1, inRight);
return root;
}
};
void print(TreeNode* root, int space)
{
if (root == NULL)
return;
space += 5;
print(root->right, space);
cout << endl;
for (int i = 5; i < space; i++)
cout << " ";
cout << root->val << "\n";
print(root->left, space);
}
int main()
{
vector<int> preorder{ 1,2,4,5,3,6 };
vector<int> inorder{ 4,2,5,1,6,3 };
Solution s;
TreeNode* root = s.buildTree(preorder, inorder);
print(root, 0);
return 0;
}
```
输出结果如下:
```
3
6
1
5
2
4
```
用C++通过二叉树的先序序列和中序序列构建二叉树,求叶子结点个数的递归和非递归
1. 通过先序序列和中序序列构建二叉树
二叉树的先序遍历序列和中序遍历序列都是按照根节点、左子树、右子树的顺序遍历的。因此,我们可以通过先序序列找到根节点,再在中序序列中找到根节点的位置,从而确定左子树和右子树的中序遍历序列。接下来,我们可以递归地构建左子树和右子树。
代码实现如下:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) {
return NULL;
}
int rootVal = preorder[0];
TreeNode* root = new TreeNode(rootVal);
int rootIndex = 0;
for (int i = 0; i < inorder.size(); i++) {
if (inorder[i] == rootVal) {
rootIndex = i;
break;
}
}
vector<int> leftPreorder(preorder.begin() + 1, preorder.begin() + rootIndex + 1);
vector<int> leftInorder(inorder.begin(), inorder.begin() + rootIndex);
vector<int> rightPreorder(preorder.begin() + rootIndex + 1, preorder.end());
vector<int> rightInorder(inorder.begin() + rootIndex + 1, inorder.end());
root->left = buildTree(leftPreorder, leftInorder);
root->right = buildTree(rightPreorder, rightInorder);
return root;
}
```
2. 递归求叶子节点个数
二叉树的叶子节点是指没有左子树和右子树的节点。因此,我们可以通过递归遍历二叉树,统计叶子节点的个数。
代码实现如下:
```c++
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
if (root->left == NULL && root->right == NULL) {
return 1;
}
return countLeaves(root->left) + countLeaves(root->right);
}
```
3. 非递归求叶子节点个数
非递归求叶子节点个数需要使用栈来辅助遍历二叉树。我们可以采用深度优先遍历算法,遍历过程中统计叶子节点的个数。具体实现如下:
```c++
int countLeaves(TreeNode* root) {
if (root == NULL) {
return 0;
}
stack<TreeNode*> s;
s.push(root);
int count = 0;
while (!s.empty()) {
TreeNode* node = s.top();
s.pop();
if (node->left == NULL && node->right == NULL) {
count++;
}
if (node->right != NULL) {
s.push(node->right);
}
if (node->left != NULL) {
s.push(node->left);
}
}
return count;
}
```
以上就是用C++通过二叉树的先序序列和中序序列构建二叉树,以及递归和非递归求叶子结点个数的方法。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)