在C ++中将二叉树转换为圆形双链表
在本教程中，我们将讨论将二进制树转换为圆形双向链表的程序。
为此，我们将提供一个二叉树。我们的任务是将左节点和右节点分别转换为左元素和右元素。并以二叉树的顺序为循环链表的顺序
示例
#include<iostream>
using namespace std;
//二叉树的节点结构
struct Node{
struct Node *left, *right;
int data;
};
//将rightlist附加到leftlist的末尾
Node *concatenate(Node *leftList, Node *rightList){
//如果一个列表为空，则返回另一个列表
if (leftList == NULL)
return rightList;
if (rightList == NULL)
return leftList;
Node *leftLast = leftList->left;
Node *rightLast = rightList->left;
//连接左列表到右列表
leftLast->right = rightList;
rightList->left = leftLast;
leftList->left = rightLast;
rightLast->right = leftList;
return leftList;
}
//转换为循环链表并返回head-
Node *bTreeToCList(Node *root){
if (root == NULL)
return NULL;
Node *left = bTreeToCList(root->left);
Node *right = bTreeToCList(root->right);
root->left = root->right = root;
return concatenate(concatenate(left, root), right);
}
//显示循环链表
void print_Clist(Node *head){
cout << "Circular Linked List is :\n";
Node *itr = head;
do{
cout << itr->data <<" ";
itr = itr->right;
}
while (head!=itr);
cout << "\n";
}
//创建新节点并返回地址
Node *newNode(int data){
Node *temp = new Node();
temp->data = data;
temp->left = temp->right = NULL;
return temp;
}
int main(){
Node *root = newNode(10);
root->left = newNode(12);
root->right = newNode(15);
root->left->left = newNode(25);
root->left->right = newNode(30);
root->right->left = newNode(36);
Node *head = bTreeToCList(root);
print_Clist(head);
return 0;
}输出结果
Circular Linked List is : 25 12 30 10 36 15