c语言实现树与二叉树的转换代码
时间: 2023-11-06 16:17:35 浏览: 94
以下是将一颗普通树转换为二叉树的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct TreeNode {
int data;
struct TreeNode *firstChild;
struct TreeNode *nextSibling;
} TreeNode;
typedef struct BinaryTreeNode {
int data;
struct BinaryTreeNode *left;
struct BinaryTreeNode *right;
} BinaryTreeNode;
BinaryTreeNode* convert(TreeNode *root) {
if (root == NULL) {
return NULL;
}
BinaryTreeNode *binaryRoot = (BinaryTreeNode *)malloc(sizeof(BinaryTreeNode));
binaryRoot->data = root->data;
binaryRoot->left = NULL;
binaryRoot->right = NULL;
if (root->firstChild != NULL) {
binaryRoot->left = convert(root->firstChild);
}
if (root->nextSibling != NULL) {
binaryRoot->right = convert(root->nextSibling);
}
return binaryRoot;
}
int main() {
// 构造一颗普通树
TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
root->data = 1;
root->firstChild = (TreeNode *)malloc(sizeof(TreeNode));
root->firstChild->data = 2;
root->firstChild->firstChild = (TreeNode *)malloc(sizeof(TreeNode));
root->firstChild->firstChild->data = 4;
root->firstChild->firstChild->firstChild = NULL;
root->firstChild->firstChild->nextSibling = NULL;
root->firstChild->nextSibling = (TreeNode *)malloc(sizeof(TreeNode));
root->firstChild->nextSibling->data = 5;
root->firstChild->nextSibling->firstChild = NULL;
root->firstChild->nextSibling->nextSibling = NULL;
root->nextSibling = (TreeNode *)malloc(sizeof(TreeNode));
root->nextSibling->data = 3;
root->nextSibling->firstChild = NULL;
root->nextSibling->nextSibling = NULL;
// 将普通树转换为二叉树
BinaryTreeNode *binaryRoot = convert(root);
return 0;
}
```
其中,`TreeNode` 表示普通树的节点,包含一个数据域和两个指针域,分别指向第一个孩子和兄弟节点;`BinaryTreeNode` 表示二叉树的节点,包含一个数据域和两个指针域,分别指向左子树和右子树。
`convert` 函数接受一个普通树的根节点作为参数,返回一个二叉树的根节点。在函数内部,我们先创建一个二叉树的根节点,将普通树的根节点的数据域赋值给二叉树的根节点的数据域。然后,如果普通树的根节点有第一个孩子,我们递归调用 `convert` 函数得到其左子树,并将其赋值给二叉树的根节点的左子树指针;如果普通树的根节点有兄弟节点,我们递归调用 `convert` 函数得到其右子树,并将其赋值给二叉树的根节点的右子树指针。最后,返回二叉树的根节点。