将森林转化为二叉树(森林采用孩子兄弟表示法的存储结构)的代码
时间: 2023-11-18 16:03:11 浏览: 67
以下是将森林转化为二叉树(森林采用孩子兄弟表示法的存储结构)的代码:
```
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct TreeNodeLink {
TreeNode *node;
struct TreeNodeLink *next;
} TreeNodeLink;
typedef struct TreeNodeQueue {
TreeNodeLink *front;
TreeNodeLink *rear;
} TreeNodeQueue;
void enqueue(TreeNodeQueue *queue, TreeNode *t) {
TreeNodeLink *newLink = (TreeNodeLink *)malloc(sizeof(TreeNodeLink));
newLink->node = t;
newLink->next = NULL;
if (queue->rear == NULL) { // if queue is empty
queue->front = newLink;
queue->rear = newLink;
} else {
queue->rear->next = newLink;
queue->rear = newLink;
}
}
TreeNode *dequeue(TreeNodeQueue *queue) {
TreeNodeLink *frontLink = queue->front;
TreeNode *result = frontLink->node;
queue->front = frontLink->next;
if (queue->front == NULL) { //if queue is empty
queue->rear = NULL;
}
free(frontLink);
return result;
}
void forestToBinaryTree(TreeNode *forestRoot) {
if (forestRoot == NULL) {
return;
}
TreeNode *currentSubtree = forestRoot;
while (currentSubtree != NULL) {
if (currentSubtree->left != NULL) { // if current subtree has a left child
TreeNode *leftChild = currentSubtree->left;
currentSubtree->left = leftChild->left; // left child becomes left subtree
leftChild->left = leftChild->right; // right child becomes sibling
leftChild->right = currentSubtree->right; // current subtree becomes right subtree
currentSubtree->right = leftChild; // left child becomes current subtree
}
currentSubtree = currentSubtree->right; // move to next subtree
}
}
void inorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%c ", root->data);
inorderTraversal(root->right);
}
int main(void) {
/* Create forest with the following structure:
*
* A---B E
* / \ \
* C D F
* |
* G
*/
TreeNode *c = (TreeNode *)malloc(sizeof(TreeNode));
c->data = 'C';
c->left = NULL;
c->right = NULL;
TreeNode *d = (TreeNode *)malloc(sizeof(TreeNode));
d->data = 'D';
d->left = NULL;
d->right = NULL;
TreeNode *b = (TreeNode *)malloc(sizeof(TreeNode));
b->data = 'B';
b->left = c;
b->right = d;
TreeNode *g = (TreeNode *)malloc(sizeof(TreeNode));
g->data = 'G';
g->left = NULL;
g->right = NULL;
TreeNode *f = (TreeNode *)malloc(sizeof(TreeNode));
f->data = 'F';
f->left = g;
f->right = NULL;
TreeNode *e = (TreeNode *)malloc(sizeof(TreeNode));
e->data = 'E';
e->left = NULL;
e->right = f;
TreeNode *a = (TreeNode *)malloc(sizeof(TreeNode));
a->data = 'A';
a->left = b;
a->right = e;
/* Convert forest to binary tree */
forestToBinaryTree(a);
/* Traverse binary tree in inorder */
inorderTraversal(a); // Output should be "C B D A G E F"
return 0;
}
```
注意:这段代码实现的是将森林全部转化为同一个树,如果需要单独转换某一个子树,需要修改相应的参数。