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

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

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

例子：

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}首先, 在继续解决方案之前。

方法：以下步骤是：

将具有偶数和奇数的节点的指针添加到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 = 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;
}

输出如下：