1.先序遍历创建二叉树; 2.中序线索化二叉树; 3.分别通过 找前驱 和 找后继 的方式,遍历中序线索二叉树。
时间: 2024-01-23 20:05:38 浏览: 29
好的,我分别为你介绍一下这三个问题的解决方案。
1. 先序遍历创建二叉树
先序遍历创建二叉树的过程是先访问当前节点,然后递归地创建左子树和右子树。具体的实现方法如下:
```
// 先序遍历创建二叉树
void createTree(Node* &node) {
int value;
cin >> value;
if (value == -1) {
node = nullptr;
} else {
node = new Node(value);
createTree(node->left);
createTree(node->right);
}
}
```
其中,-1 表示空节点。我们可以通过输入先序遍历序列来创建一棵二叉树,示例输入如下:
```
1 2 4 -1 -1 5 -1 -1 3 -1 -1
```
2. 中序线索化二叉树
中序线索化二叉树的过程是为每个节点添加前驱指针和后继指针,使其可以跨越指向空节点的指针进行遍历。具体的实现方法如下:
```
// 中序线索化二叉树
void inOrderThread(Node* &node, Node* &pre) {
if (node == nullptr) return;
inOrderThread(node->left, pre);
if (node->left == nullptr) {
node->left = pre;
node->isLeftThread = true;
}
if (pre != nullptr && pre->right == nullptr) {
pre->right = node;
pre->isRightThread = true;
}
pre = node;
inOrderThread(node->right, pre);
}
```
其中,pre 是指当前节点的前驱节点。在遍历过程中,如果当前节点的左子节点为空,则将其左子节点指向前驱节点,同时设置 isLeftThread 标记为 true;如果前驱节点的右子节点为空,则将其右子节点指向当前节点,同时设置 isRightThread 标记为 true。
3. 分别通过找前驱和找后继的方式,遍历中序线索二叉树
通过找前驱和找后继的方式遍历中序线索二叉树的过程是,先找到第一个节点,然后不断根据前驱指针或后继指针遍历整棵树。具体的实现方法如下:
```
// 找到中序遍历的第一个节点
Node* firstNodeInOrderThread(Node* node) {
while (node != nullptr && !node->isLeftThread) {
node = node->left;
}
return node;
}
// 找到中序遍历的最后一个节点
Node* lastNodeInOrderThread(Node* node) {
while (node != nullptr && !node->isRightThread) {
node = node->right;
}
return node;
}
// 找到节点的前驱节点
Node* findPredecessor(Node* node) {
if (node->isLeftThread) {
return node->left;
} else {
return lastNodeInOrderThread(node->left);
}
}
// 找到节点的后继节点
Node* findSuccessor(Node* node) {
if (node->isRightThread) {
return node->right;
} else {
return firstNodeInOrderThread(node->right);
}
}
// 中序线索二叉树的中序遍历(通过找前驱实现)
void inOrderTraversalByPredecessor(Node* root) {
Node* node = firstNodeInOrderThread(root);
while (node != nullptr) {
cout << node->val << " ";
node = findSuccessor(node);
}
cout << endl;
}
// 中序线索二叉树的中序遍历(通过找后继实现)
void inOrderTraversalBySuccessor(Node* root) {
Node* node = firstNodeInOrderThread(root);
while (node != nullptr) {
cout << node->val << " ";
node = findSuccessor(node);
}
cout << endl;
}
```
其中,firstNodeInOrderThread 函数用于找到中序遍历的第一个节点;lastNodeInOrderThread 函数用于找到中序遍历的最后一个节点;findPredecessor 函数用于找到节点的前驱节点;findSuccessor 函数用于找到节点的后继节点。
通过调用 inOrderTraversalByPredecessor 或 inOrderTraversalBySuccessor 函数,可以分别通过找前驱和找后继的方式遍历中序线索二叉树。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)