将二叉树转换为穿针二叉树 | 在 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
广告