数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究将二叉树转换为穿针二叉树 | 在 C++ 中使用队列的集合 1
在本教程中，我们将讨论一个使用队列数据结构将二叉树转换为穿针二叉树的程序。
为此，我们将提供一棵二叉树。我们的任务是通过在队列数据结构的帮助下添加额外的路由来将这棵特定的二叉树转换为穿针二叉树，以实现更快速的顺序遍历。
示例
#include <iostream>
#include <queue>
using namespace std;
//node structure for threaded tree
struct Node {
int key;
Node *left, *right;
bool isThreaded;
};
//putting the inorder pattern into a queue
void convert_queue(Node* root, std::queue<Node*>* q){
if (root == NULL)
return;
if (root->left)
convert_queue(root->left, q);
q->push(root);
if (root->right)
convert_queue(root->right, q);
}
//traversing the queue and making threaded tree
void create_threadedtree(Node* root, std::queue<Node*>* q){
if (root == NULL)
return;
if (root->left)
create_threadedtree(root->left, q);
q->pop();
if (root->right)
create_threadedtree(root->right, q);
//if right pointer in NUll, point it to
//inorder successor
else {
root->right = q->front();
root->isThreaded = true;
}
}
//finally taking the tree and converting it into threaded
void createThreaded(Node* root){
std::queue<Node*> q;
convert_queue(root, &q);
create_threadedtree(root, &q);
}
Node* leftMost(Node* root){
while (root != NULL && root->left != NULL)
root = root->left;
return root;
}
//performing inorder traversal of threaded tree
void inOrder(Node* root){
if (root == NULL)
return;
Node* cur = leftMost(root);
while (cur != NULL) {
cout << cur->key << " ";
//if threaded node, move to inorder successor
if (cur->isThreaded)
cur = cur->right;
else
cur = leftMost(cur->right);
}
}
Node* newNode(int key){
Node* temp = new Node;
temp->left = temp->right = NULL;
temp->key = key;
return temp;
}
int main(){
Node* root = newNode(1);
root->left = newNode(2);
root->right = newNode(3);
root->left->left = newNode(4);
root->left->right = newNode(5);
root->right->left = newNode(6);
root->right->right = newNode(7);
createThreaded(root);
cout << "Traversing threaded tree :\n";
inOrder(root);
return 0;
}输出
Traversing threaded tree : 4 2 5 1 6 3 7
更新日期： 2020 年 1 月 2 日
330 次浏览
广告