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

2021年5月13日16:42:22 发表评论 476 次浏览

``````Consider the binary tree given below

1
/   \
2        3
/ \     /\
4     5   6    7

Now with the help of abtr pointers of node, we connect odd and even nodes as:

Odd loop
1 -> 5 -> 3 -> 7 -> 1(again pointing to first node
in the loop)

Even loop
2 -> 4 -> 6 -> 2(again pointing to first node
in the loop)

Nodes in the respective loop can be arranged in
any order. But from any node in the loop we should
be able to traverse all the nodes in the loop.``````

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

1. 将具有偶数和奇数的节点的指针添加到even_ptrs和奇怪的数组。通过任何树遍历, 我们都可以获取相应的节点指针。
2. 对于两者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 = 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);            /*      2       3      */
root->left->left = newNode(4);       /*    /\    / \    */
root->left->right = newNode(5);      /*   4    5  6     7   */
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;
}``````

``````Odd nodes: 3 7 1 5
Even nodes: 2 4 6``````