在二叉树中创建偶数值和奇数值的循环 _创建偶数值和奇数值的循环

给定具有节点结构的二叉树, 该结构包含数据部分, 左右指针和任意指针(abtr)。节点的值可以是任何正整数。问题是在二叉树中创建奇数和偶数循环。奇数循环是连接所有具有奇数的节点的循环, 类似地, 偶数循环也用于具有偶数的节点。为了创建这样的循环, 使用每个节点的abtr指针。奇数节点(具有奇数的节点)的abtr指针指向树中的其他奇数节点。必须以这样的方式创建循环, 以便我们可以从任何节点遍历该节点所属的循环中的所有节点。
例子：

Consider the binary tree given below 1/\23 / \/\4567Now with the help of abtr pointers of node, we connect odd and even nodes as:Odd loop1 -> 5 -> 3 -> 7 -> 1(again pointing to first nodein the loop)Even loop2 -> 4 -> 6 -> 2(again pointing to first nodein the loop)Nodes in the respective loop can be arranged inany order. But from any node in the loop we should be able to traverse all the nodes in the loop.

推荐：请尝试以下方法{IDE}首先, 在继续解决方案之前。方法：以下步骤是：

将具有偶数和奇数的节点的指针添加到even_ptrs和奇怪的数组。通过任何树遍历, 我们都可以获取相应的节点指针。
对于两者even_ptrs和奇怪的数组, 执行：
- 由于数组包含节点指针, 因此考虑第ith个索引处的元素, 让它成为节点, 并在第(i + 1)个索引处分配结点-> abtr =元素。
- 对于数组的最后一个元素, node-> abtr =元素在索引0处。

//C++ implementation to create odd and even loops //in a binary tree #include < bits/stdc++.h> using namespace std; //structure of a node struct Node { int data; Node *left, *right, *abtr; }; //Utility function to create a new node struct Node* newNode( int data) { struct Node* node = new Node; node-> data = https://www.lsbin.com/data; node-> left = node-> right = node-> abtr = NULL; return node; }//preorder traversal to place the node pointer //in the respective even_ptrs or odd_ptrs list void preorderTraversal(Node *root, vector< Node*> *even_ptrs, vector< Node*> *odd_ptrs) { if (!root) return ; //place node ptr in even_ptrs list if //node contains even number if (root-> data % 2 == 0) (*even_ptrs).push_back(root); //else place node ptr in odd_ptrs list else (*odd_ptrs).push_back(root); preorderTraversal(root-> left, even_ptrs, odd_ptrs); preorderTraversal(root-> right, even_ptrs, odd_ptrs); }//function to create the even and odd loops void createLoops(Node *root) {vector< Node*> even_ptrs, odd_ptrs; preorderTraversal(root, & even_ptrs, & odd_ptrs); int i; //forming even loop for (i=1; i< even_ptrs.size(); i++) even_ptrs[i-1]-> abtr = even_ptrs[i]; //for the last element even_ptrs[i-1]-> abtr = even_ptrs[0]; //Similarly forming odd loop for (i=1; i< odd_ptrs.size(); i++) odd_ptrs[i-1]-> abtr = odd_ptrs[i]; odd_ptrs[i-1]-> abtr = odd_ptrs[0]; }//traversing the loop from any random //node in the loop void traverseLoop(Node *start) { Node *curr = start; do { cout < < curr-> data < <" " ; curr = curr-> abtr; } while (curr != start); }//Driver program to test above int main() { //Binary tree formation struct Node* root = NULL; root = newNode(1); /*1*/ root-> left = newNode(2); /*/\*/ root-> right = newNode(3); /*23*/ root-> left-> left = newNode(4); /*/\/ \*/ root-> left-> right = newNode(5); /*4567*/ root-> right-> left = newNode(6); root-> right-> right = newNode(7); createLoops(root); //traversing odd loop from any //random odd node cout < < "Odd nodes: " ; traverseLoop(root-> right); cout < < endl < < "Even nodes: " ; //traversing even loop from any //random even node traverseLoop(root-> left); return 0; }

【在二叉树中创建偶数值和奇数值的循环】输出如下：