1.先序遍历创建二叉树; 2.中序线索化二叉树; 3.分别通过 找前驱 和 找后继 的方式,遍历中序线索二叉树。
时间: 2024-01-23 14:05:55 浏览: 74
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
5星 · 资源好评率100%
好的,我明白了。您的问题是关于二叉树的操作和遍历的。我来一一回答您的问题:
1. 先序遍历创建二叉树。先序遍历创建二叉树的思路是:先遍历根节点,然后递归构建左子树和右子树。具体实现可以使用递归算法,代码如下:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode* buildTree(vector<int>& preorder, int& i) {
int n = preorder.size();
if (i >= n || preorder[i] == -1) {
return nullptr;
}
TreeNode* root = new TreeNode(preorder[i++]);
root->left = buildTree(preorder, i);
root->right = buildTree(preorder, i);
return root;
}
```
2. 中序线索化二叉树。中序线索化二叉树的思路是:对于每个节点,将其左子树的最右节点指向该节点的前驱(中序遍历的前一个节点),将其右子树的最左节点指向该节点的后继(中序遍历的后一个节点)。具体实现可以使用递归算法,代码如下:
```c++
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
bool left_threaded;
bool right_threaded;
TreeNode(int x) : val(x), left(nullptr), right(nullptr), left_threaded(false), right_threaded(false) {}
};
void inorderThread(TreeNode* root, TreeNode*& pre) {
if (!root) {
return;
}
inorderThread(root->left, pre);
if (!root->left) {
root->left_threaded = true;
root->left = pre;
}
if (pre && !pre->right) {
pre->right_threaded = true;
pre->right = root;
}
pre = root;
inorderThread(root->right, pre);
}
TreeNode* inorderThread(TreeNode* root) {
TreeNode* dummy = new TreeNode(-1);
dummy->right = root;
TreeNode* pre = dummy;
inorderThread(root, pre);
pre->right = dummy;
pre->right_threaded = true;
dummy->left = pre;
return dummy;
}
```
3. 遍历中序线索二叉树。遍历中序线索二叉树的思路是:从根节点开始,先找到中序遍历的第一个节点,然后不断找它的后继,直到找到最后一个节点。具体实现可以使用循环算法,代码如下:
```c++
void inorderTraversal(TreeNode* root) {
TreeNode* p = root;
while (p) {
while (p->left_threaded == false) {
p = p->left;
}
cout << p->val << " ";
while (p->right_threaded == true) {
p = p->right;
cout << p->val << " ";
}
p = p->right;
}
}
```
希望我的回答能够帮到您!
阅读全文