树的应用（不是二叉树）

Question

用C语言实现树与二叉树的转换，树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，且包含建树的实现。
注意是树不是二叉树，希望有源代码

Answer 1

此回答引用Chatgpt

#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;

// 树的前序遍历递归实现
void treePreOrderRecursive(TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->data);
        treePreOrderRecursive(root->firstChild);
        treePreOrderRecursive(root->nextSibling);
    }
}

// 树的前序遍历非递归实现
void treePreOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    stack[++top] = root;
    while (top >= 0) {
        TreeNode* node = stack[top--];
        printf("%d ", node->data);
        TreeNode* sibling = node->nextSibling;
        while (sibling != NULL) {
            stack[++top] = sibling;
            sibling = sibling->nextSibling;
        }
        TreeNode* child = node->firstChild;
        while (child != NULL) {
            stack[++top] = child;
            child = child->nextSibling;
        }
    }
}

// 树的后序遍历递归实现
void treePostOrderRecursive(TreeNode* root) {
    if (root != NULL) {
        treePostOrderRecursive(root->firstChild);
        printf("%d ", root->data);
        treePostOrderRecursive(root->nextSibling);
    }
}

// 树的后序遍历非递归实现
void treePostOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* stack[100];
    int top = -1;
    TreeNode* lastVisited = NULL;
    while (root != NULL || top >= 0) {
        while (root != NULL) {
            stack[++top] = root;
            root = root->firstChild;
        }
        TreeNode* node = stack[top];
        if (node->nextSibling == NULL || node->nextSibling == lastVisited) {
            printf("%d ", node->data);
            top--;
            lastVisited = node;
        } else {
            root = node->nextSibling;
        }
    }
}

// 树的层次遍历非递归实现
void treeLevelOrderNonRecursive(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    TreeNode* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front != rear) {
        TreeNode* node = queue[front++];
        printf("%d ", node->data);
        TreeNode* child = node->firstChild;
        while (child != NULL) {
            queue[rear++] = child;
            child = child->nextSibling;
        }
    }
}

// 树转二叉树的递归实现
void treeToBinaryTreeRecursive(TreeNode* root, BinaryTreeNode** binaryRoot) {
if (root == NULL) {
*binaryRoot = NULL;
} else {
binaryRoot = (BinaryTreeNode)malloc(sizeof(BinaryTreeNode));
(*binaryRoot)->data = root->data;
(*binaryRoot)->left = NULL;
(binaryRoot)->right = NULL;
TreeNode child = root->firstChild;
if (child != NULL) {
treeToBinaryTreeRecursive(child, &((binaryRoot)->left));
BinaryTreeNode binaryChild = (*binaryRoot)->left;
while (child->nextSibling != NULL) {
child = child->nextSibling;
treeToBinaryTreeRecursive(child, &((*binaryChild)->right));
binaryChild = binaryChild->right;
}
}
}
}

// 二叉树转树的递归实现
void binaryTreeToTreeRecursive(BinaryTreeNode* binaryRoot, TreeNode** root) {
if (binaryRoot == NULL) {
*root = NULL;
} else {
root = (TreeNode)malloc(sizeof(TreeNode));
(*root)->data = binaryRoot->data;
(*root)->firstChild = NULL;
(root)->nextSibling = NULL;
if (binaryRoot->left != NULL) {
binaryTreeToTreeRecursive(binaryRoot->left, &((root)->firstChild));
TreeNode node = (root)->firstChild;
while (node->nextSibling != NULL) {
node = node->nextSibling;
}
BinaryTreeNode binaryNode = binaryRoot->left->right;
while (binaryNode != NULL) {
TreeNode child = NULL;
binaryTreeToTreeRecursive(binaryNode, &child);
node->nextSibling = child;
node = node->nextSibling;
binaryNode = binaryNode->right;
}
}
}
}

// 建树的实现
void createTree(TreeNode** root) {
int data;
scanf("%d", &data);
if (data == -1) {
*root = NULL;
} else {
root = (TreeNode)malloc(sizeof(TreeNode));
(*root)->data = data;
createTree(&((*root)->firstChild));
createTree(&((*root)->nextSibling));
}
}
// 树转二叉树的递归实现
void treeToBinaryTreeRecursive(TreeNode* root, BinaryTreeNode** binaryRoot) {
if (root == NULL) {
*binaryRoot = NULL;
} else {
binaryRoot = (BinaryTreeNode)malloc(sizeof(BinaryTreeNode));
(*binaryRoot)->data = root->data;
(*binaryRoot)->left = NULL;
(binaryRoot)->right = NULL;
TreeNode child = root->firstChild;
if (child != NULL) {
treeToBinaryTreeRecursive(child, &((binaryRoot)->left));
BinaryTreeNode binaryChild = (*binaryRoot)->left;
while (child->nextSibling != NULL) {
child = child->nextSibling;
treeToBinaryTreeRecursive(child, &((binaryChild)->right));
binaryChild = binaryChild->right;
}
}
}
}

// 二叉树转树的递归实现
void binaryTreeToTreeRecursive(BinaryTreeNode* binaryRoot, TreeNode** root) {
if (binaryRoot == NULL) {
*root = NULL;
} else {
root = (TreeNode)malloc(sizeof(TreeNode));
(*root)->data = binaryRoot->data;
(*root)->firstChild = NULL;
(root)->nextSibling = NULL;
if (binaryRoot->left != NULL) {
binaryTreeToTreeRecursive(binaryRoot->left, &((root)->firstChild));
TreeNode node = (root)->firstChild;
while (node->nextSibling != NULL) {
node = node->nextSibling;
}
BinaryTreeNode binaryNode = binaryRoot->left->right;
while (binaryNode != NULL) {
TreeNode child = NULL;
binaryTreeToTreeRecursive(binaryNode, &child);
node->nextSibling = child;
node = node->nextSibling;
binaryNode = binaryNode->right;
}
}
}
}
// 续写建树的实现

void createTree(TreeNode** root) {
int data;
printf("请输入节点值（-1表示结束）：");
scanf("%d", &data);
if (data == -1) {
*root = NULL;
} else {
root = (TreeNode)malloc(sizeof(TreeNode));
(*root)->data = data;
printf("%d的第一个子节点：", data);
createTree(&((*root)->firstChild));
printf("%d的下一个兄弟节点：", data);
createTree(&((*root)->nextSibling));
}
}

int main() {
// 建树
TreeNode* root = NULL;
createTree(&root);
// 输出建立的树
printf("建立的树为：\n");
treeLevelOrderNonRecursive(root);
printf("\n");

// 树转二叉树
BinaryTreeNode* binaryRoot = NULL;
treeToBinaryTreeRecursive(root, &binaryRoot);

// 输出转换后的二叉树
printf("转换后的二叉树为：\n");
treeLevelOrderNonRecursive(binaryRoot);
printf("\n");

// 二叉树转树
TreeNode* newRoot = NULL;
binaryTreeToTreeRecursive(binaryRoot, &newRoot);

// 输出转换后的树
printf("转换后的树为：\n");
treeLevelOrderNonRecursive(newRoot);
printf("\n");

// 销毁树
// destroyTree(root);
// destroyTree(newRoot);

return 0;
}