树的应用（不是二叉树）
用C语言实现树与二叉树的转换，树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，且包含建树的实现。
注意是树不是二叉树，希望有源代码
此回答引用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;
}
https://blog.csdn.net/weixin_42545675/article/details/97647275
你要的功能都包含了
https://blog.csdn.net/rather_than/article/details/126467086
该回答引用ChatGPT
该算法使用了一个栈来模拟递归过程。首先将根节点压入栈中，然后循环执行以下步骤：弹出栈顶节点，输出它的值，然后将右子节点和左子节点按照相反的顺序压入栈中。这样可以保证下一次弹出的节点是左子节点，从而实现前序遍历的顺序。
#include <stdio.h>
#include <stdlib.h>
//定义树节点结构体
struct TreeNode {
int data;
struct TreeNode* firstChild; //指向第一个子节点的指针
struct TreeNode* nextSibling; //指向下一个兄弟节点的指针
};
//定义二叉树节点结构体
struct BinaryTreeNode {
int data;
struct BinaryTreeNode* left; //指向左子树的指针
struct BinaryTreeNode* right; //指向右子树的指针
};
//创建树节点
struct TreeNode* createTreeNode(int data) {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->data = data;
node->firstChild = NULL;
node->nextSibling = NULL;
return node;
}
//创建二叉树节点
struct BinaryTreeNode* createBinaryTreeNode(int data) {
struct BinaryTreeNode* node = (struct BinaryTreeNode*)malloc(sizeof(struct BinaryTreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
//将树转换成二叉树
struct BinaryTreeNode* treeToBinaryTree(struct TreeNode* root) {
if (root == NULL) {
return NULL;
}
struct BinaryTreeNode* binaryRoot = createBinaryTreeNode(root->data);
if (root->firstChild != NULL) {
binaryRoot->left = treeToBinaryTree(root->firstChild);
}
struct TreeNode* sibling = root->firstChild;
struct BinaryTreeNode* binarySibling = binaryRoot->left;
while (sibling != NULL) {
binarySibling->right = treeToBinaryTree(sibling);
sibling = sibling->nextSibling;
binarySibling = binarySibling->right;
}
return binaryRoot;
}
//将二叉树转换成树
struct TreeNode* binaryTreeToTree(struct BinaryTreeNode* root) {
if (root == NULL) {
return NULL;
}
struct TreeNode* treeRoot = createTreeNode(root->data);
if (root->left != NULL) {
treeRoot->firstChild = binaryTreeToTree(root->left);
}
struct BinaryTreeNode* sibling = root->left;
struct TreeNode* treeSibling = treeRoot->firstChild;
while (sibling != NULL) {
treeSibling->nextSibling = binaryTreeToTree(sibling->right);
sibling = sibling->right;
treeSibling = treeSibling->nextSibling;
}
return treeRoot;
}
//树的前序遍历递归算法
void treePreorderRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
struct TreeNode* child = root->firstChild;
while (child != NULL) {
treePreorderRecursive(child);
child = child->nextSibling;
}
}
//树的前序遍历非递归算法
void treePreorderNonRecursive(struct TreeNode* root) {
if (root == NULL) {
return;
}
struct TreeNode* stack[100];
int top = -1;
stack[++top] = root;
while (top >= 0) {
struct TreeNode* node = stack[top--];
printf("%d ", node->val);
if (node->right != NULL) {
stack[++top] = node->right;
}
if (node->left != NULL) {
stack[++top] = node->left;
}
}
}
下面是C语言实现树与二叉树转换、树的前序、后序递归、非递归算法，以及层次序非递归算法的源代码。事例代码中使用结构体定义了树的节点类型，节点中包含了该节点的值、子树数量以及指向该节点的子节点的指针。希望能帮到你。
事例1：
事例2：
首先是建树的实现，下面是一个示例代码：
以上代码定义了树节点的结构体，包含节点值、指向第一个子节点的指针和指向下一个兄弟节点的指针。createTreeNode()函数用于创建一个树节点，参数为节点值，返回新创建的节点指针。addChild()函数用于将子节点添加到父节点下，参数为父节点指针和子节点指针。buildTree()函数用于创建一个示例树，并返回根节点的指针。
下面是将树转换为二叉树的实现，代码如下：
C语言实现树与二叉树的转换，可以通过将树的每个节点的左右子树，分别放在它的左右指针中，即可实现。
1. 树的前序、后序的递归算法实现：
1.1 前序遍历：从根节点开始，先访问根节点，再访问其左子树，最后访问其右子树。
递归实现：
void preOrder(Node* root) {
if (root == NULL) return;
printf("%d ", root->data);
preOrder(root->left);
preOrder(root->right);
}
1.2 后序遍历：从根节点开始，先访问其左子树，再访问其右子树，最后访问根节点。
递归实现：
void postOrder(Node* root) {
if (root == NULL) return;
postOrder(root->left);
postOrder(root->right);
printf("%d ", root->data);
}
2.树的前序、后序的非递归算法实现：
2.1 前序遍历：从根节点开始，先访问根节点，再访问其左子树，最后访问其右子树。
非递归实现：
void preOrderNonRecursive(Node* root) {
if (root == NULL) return;
stack> s;
s.push(root);
while (!s.empty()){
Node* curr = s.top();
s.pop();
printf ("%d ", curr->data);
if (curr->right) s.push(curr->right);
if (curr->left) s.push(curr->left);
}
}
2.2后序遍历：从根节点开始，先访问其左子树，再访问其右子树，最后访问根节点。
非递归实现：
void postOrderNonRecursive(Node* root) {
if (root == NULL) return;
stack> s1, s2;
s1.push(root);
Node* node;
while (!s1.empty()){
node = s1.top();
s1.pop();
s2.push(node);
if (node->left)
s1.push(node->left);
if (node->right)
s1.push(node->right);
}
while (!s2.empty()){
node = s2.top();
s2.pop();
printf("%d ", node->data);
}
}
3.层次序的非递归算法实现：从根节点开始，按照层次从上到下遍历每个节点，从左到右访问。
3.1非递归实现：
void levelOrder(Node* root) {
if (root == NULL) return;
queue> q;
q.push(root);
while (!q.empty()){
int n = q.size();
for (int i = 0; i < n; i++){
Node* curr = q.front();
q.pop();
printf("%d ", curr->data);
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
}
printf("\n");
}
}
建树的实现：可以使用前序遍历的方法，先将根节点放进树中，然后依次将左右子树放进树中，以此类推，即可建立一棵树。
- 建议你看下这篇博客👉 ：解决二叉树的编程问题
- 另外, 我还从CSDN技能树中找了一些相关资料给你, 你可以学习下:
- 相关参考资料: leetcode 100 相同的树
#include <stdio.h>
#include <stdlib.h>
#define NULL 0
#define M 100
//定义结构体
// 定义一个用于存储节点的二叉树，用于数据的存储，和后面遍历取值
typedef struct node
{
int data;
int count;//count是为了计数用。在后序遍历中，子树的根节点在第一次遍历的时候不会输出，只有在第二次遍历的时候才输出。
struct node *lchild;
struct node *rchild;
}binaryTree;
// 定义一个储存树节点的栈，方便遍历的时候追踪到树的地址。
typedef struct stack
{
binaryTree *elements[M];
int top;
}sequenceStack;
// 定义一个存储树节点的队列
typedef struct queue {
binaryTree *queueNum[M];
int front;
int rear;
}sequenceQueue;
// 定义操作变量
binaryTree *root;//定义一个树根
sequenceStack s;//定义栈
sequenceQueue q;//定义队列
//操作栈的一些方法
//初始化栈
void setNull()
{
s.top =0;
}
//入栈操作，就是将元素加入定义好的栈中
void push(binaryTree *temp)
{
s.elements[s.top++] = temp;
}
binaryTree *pop()//取栈顶并出栈顶
{
return s.elements[--s.top];//先计算，再取值
}
int empty()//判断空栈
{
return s.top == 0;
}
//操作队列的一些方法
//初始化队列
void initialQueue() {
q.front = 0;
q.rear = 0;
}
//入队列
void pushElement(binaryTree * temp) {
q.queueNum[q.rear++] = temp;
}
//出队列
binaryTree *popElement() {
return q.queueNum[q.front++];
}
int emptyQueue() {
return q.front == q.rear;
}
// 构建二叉树
binaryTree *creatBinaryTree(){
binaryTree *t;
int x;
scanf("%d",&x);
// 当我们输入的数字为 0 时，就将其对应的节点置空，放到了二叉树的最后
if(x==0){
t=NULL; /*以x=0表示输入结束*/
} else {
//动态生成结点t,分别给结点t的数据域、左右孩子域
t=(binaryTree*)malloc(sizeof(binaryTree));
t->data=x;
//赋值,给左右孩子域赋值时用到了递归的思想。
t->lchild=creatBinaryTree();
t->rchild=creatBinaryTree();
}
return t;
}
//前序遍历的非递归算法
void preOrderWithoutRecursion(binaryTree *t)
{
binaryTree *temp = t;//定义一个树节点，用它来遍历
while(temp != NULL || s.top != 0)
{
while(temp != NULL)//先遍历左孩子，并输出。
{
printf("%5d",temp->data);
//这里将不停的入栈，是为了在遍历完左子树，之后遍历右子树时，进行根节点的查找
push(temp);
temp = temp->lchild;
}
//当左孩子遍历完后，取栈顶，找右孩子。此时循环还没有结束，再遍历它的左孩子，直至孩子全部遍历结束。
// 这里判断栈中是否还有元素，如果有的话，说明，右子树不为空，继续进行非递归前序遍历
if(s.top != 0)
{
//这里的弹栈和上面的入栈操作是一一对应的，
temp = pop();
temp = temp->rchild;
}
}
printf("\n");
}
//中序遍历的非递归算法
void inOrderWithoutRecursion(binaryTree *t)
{
binaryTree *temp = t;
while(temp != NULL||s.top != 0)
{
while(temp != NULL)//先把左孩子入栈，所有左孩子入栈结束
{
push(temp);
temp = temp->lchild;
}
if(s.top != 0)//左孩子入栈结束，取栈顶，输出栈顶元素，遍历右孩子
{
temp = pop();
printf("%5d",temp->data);
temp = temp->rchild;
}
}
printf("\n");
}
//后序遍历的非递归算法
void postOrderWithoutRecursion(binaryTree *root)
{
binaryTree *temp = root;
while(temp!=NULL||s.top!=0) {
while(temp!= NULL) {
//当元素首次被访问时，我们将该元素进行标记，说明它是首次访问
temp->count=1;
push(temp);
temp=temp->lchild;
}
if(s.top!=0) {
//弹栈
temp=pop();
//说明该元素是第一次出现在栈中
if(temp->count == 1) {
temp->count++;
//再次入栈，并将标志位加一
push(temp);
temp=temp->rchild;
}
else {
//进行判读当前节点的访问状态，
//如果是 2，就说明已经遍历了该结点的左子树，也就是能够进行后序遍历输出的操作
if(temp->count==2) {
printf("%5d",temp->data);
temp=NULL;
}
}
}
}
printf("\n");
}
//前序遍历的递归算法
void preOrderWithRecursion(binaryTree *t) {
if (t == NULL) {
return;
}
printf("%5d\t",t->data);
preOrderWithRecursion(t->lchild);
preOrderWithRecursion(t->rchild);
}
//中序遍历的递归算法
void inOrderWithRecursion(binaryTree *t) {
if (t == NULL) {
return;
}
inOrderWithRecursion(t->lchild);
printf("%5d\t",t->data);
inOrderWithRecursion(t->rchild);
}
//后序遍历的递归算法
void postOrderWithRecursion(binaryTree *t){
if (t == NULL) {
return;
}
postOrderWithRecursion(t->lchild);
postOrderWithRecursion(t->rchild);
printf("%5d\t",t->data);
}
//层次序的非递归遍历算法
void levelOrderWithoutRecursion(binaryTree *t) {
binaryTree *temp;
pushElement(t);
while (!emptyQueue()) {
temp = popElement();
printf("%5d\t", temp->data);
if(temp->lchild) {
pushElement(temp->lchild);
}
if(temp->rchild) {
pushElement(temp->rchild);
}
}
}
//main方法
int main()
{
binaryTree *root;//创建根
setNull();//制空栈
root=creatBinaryTree();//创建二叉树:尝试输入：1 2 3 0 0 4 0 0 5 6 0 0 7 0 0
printf("非递归前序遍历:\n");
preOrderWithoutRecursion(root);
printf("非递归中序遍历:\n");
inOrderWithoutRecursion(root);
printf("非递归后序遍历:\n");
postOrderWithoutRecursion(root);
printf("**********************************************************************");
printf("\n");
printf("递归前序遍历:\n");
preOrderWithRecursion(root);
printf("\n递归中序遍历:\n");
inOrderWithRecursion(root);
printf("\n递归后序遍历:\n");
postOrderWithRecursion(root);
printf("\n**********************************************************************");
printf("\n层次序非递归遍历结果：\n");
levelOrderWithoutRecursion(root);
return 0;
}
以下是用C语言实现树与二叉树的转换，树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，以及建树的实现代码。
c
#include <stdio.h> #include <stdlib.h> // 树节点定义 typedef struct node { int data; struct node *firstChild; struct node *nextSibling; } Node; // 树转换为二叉树 Node* treeToBinaryTree(Node *root) { if (root == NULL) { return NULL; } Node *p = root->firstChild; if (p == NULL) { return root; } Node *q = treeToBinaryTree(p); root->firstChild = q; while (q != NULL && q->nextSibling != NULL) { q = treeToBinaryTree(q->nextSibling); } return q; } // 前序遍历的递归实现 void preorderRecursive(Node *root) { if (root == NULL) { return; } printf("%d ", root->data); Node *p = root->firstChild; while (p != NULL) { preorderRecursive(p); p = p->nextSibling; } } // 前序遍历的非递归实现 void preorderNonRecursive(Node *root) { if (root == NULL) { return; } Node *stack[100]; int top = 0; stack[top++] = root; while (top > 0) { Node *p = stack[--top]; printf("%d ", p->data); Node *q = p->firstChild; while (q != NULL) { stack[top++] = q; q = q->nextSibling; } } } // 后序遍历的递归实现 void postorderRecursive(Node *root) { if (root == NULL) { return; } Node *p = root->firstChild; while (p != NULL) { postorderRecursive(p); p = p->nextSibling; } printf("%d ", root->data); } // 后序遍历的非递归实现 void postorderNonRecursive(Node *root) { if (root == NULL) { return; } Node *stack1[100]; Node *stack2[100]; int top1 = 0; int top2 = 0; stack1[top1++] = root; while (top1 > 0) { Node *p = stack1[--top1]; stack2[top2++] = p; Node *q = p->firstChild; while (q != NULL) { stack1[top1++] = q; q = q->nextSibling; } } while (top2 > 0) { Node *p = stack2[--top2]; printf("%d ", p->data); } } // 层次遍历的非递归实现 void levelOrderNonRecursive(Node *root) { if (root == NULL) { return; } Node *queue[100]; int front = 0; int rear = 0; queue[rear++] = root; while (front <
#include <stdio.h>
#include <stdlib.h>
// 定义树的结构体
typedef struct tree_node {
int data; // 数据
struct tree_node* child; // 子节点链表
struct tree_node* next; // 兄弟节点
} Tree;
// 定义二叉树的结构体
typedef struct binary_tree_node {
int data; // 数据
struct binary_tree_node* left; // 左子树
struct binary_tree_node* right; // 右子树
} BinaryTree;
// 创建树
Tree* create_tree(int data) {
Tree* node = (Tree*)malloc(sizeof(Tree));
node->data = data;
node->child = NULL;
node->next = NULL;
return node;
}
// 插入子节点
void insert_child(Tree* parent, Tree* child) {
if (parent == NULL || child == NULL) {
return;
}
if (parent->child == NULL) {
parent->child = child;
} else {
Tree* node = parent->child;
while (node->next != NULL) {
node = node->next;
}
node->next = child;
}
}
// 将树转换为二叉树
BinaryTree* tree_to_binary_tree(Tree* root) {
if (root == NULL) {
return NULL;
}
BinaryTree* node = (BinaryTree*)malloc(sizeof(BinaryTree));
node->data = root->data;
node->left = NULL;
node->right = NULL;
if (root->child != NULL) {
node->left = tree_to_binary_tree(root->child);
}
if (root->next != NULL) {
node->right = tree_to_binary_tree(root->next);
}
return node;
}
// 树的前序遍历（递归算法）
void pre_order_tree_recursive(Tree* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
Tree* child = root->child;
while (child != NULL) {
pre_order_tree_recursive(child);
child = child->next;
}
}
// 树的前序遍历（非递归算法）
void pre_order_tree_nonrecursive(Tree* root) {
if (root == NULL) {
return;
}
Tree* stack[100];
int top = -1;
stack[++top] = root;
while (top != -1) {
Tree* node = stack[top--];
printf("%d ", node->data);
Tree* child = node->child;
while (child != NULL) {
stack[++top] = child;
child = child->next;
}
}
}
// 树的后序遍历（递归算法）
void post_order_tree_recursive(Tree* root) {
if (root == NULL) {
return;
}
Tree* child = root->child;
while (child != NULL) {
post_order_tree_recursive(child);
child = child->next;
}
printf("%d ",
以下是使用 C 语言实现树与二叉树的转换，以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，并包含建树的源代码。其中树的节点结构体 TreeNode 包含节点值和指向其子节点的指针数组，二叉树的节点结构体 BinaryTreeNode 包含节点值和指向其左右子节点的指针。这里的实现中假设树或二叉树节点值为整数。
#include <stdio.h>
#include <stdlib.h>
// 树的节点结构体
typedef struct TreeNode {
int val;
struct TreeNode** children;
int num_children;
} TreeNode;
// 二叉树的节点结构体
typedef struct BinaryTreeNode {
int val;
struct BinaryTreeNode* left;
struct BinaryTreeNode* right;
} BinaryTreeNode;
// 树转换为二叉树
BinaryTreeNode* tree_to_binary_tree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
BinaryTreeNode* binary_root = (BinaryTreeNode*) malloc(sizeof(BinaryTreeNode));
binary_root->val = root->val;
binary_root->left = NULL;
binary_root->right = NULL;
if (root->num_children > 0) {
binary_root->left = tree_to_binary_tree(root->children[0]);
BinaryTreeNode* curr = binary_root->left;
int i;
for (i = 1; i < root->num_children; i++) {
curr->right = tree_to_binary_tree(root->children[i]);
curr = curr->right;
}
}
return binary_root;
}
// 建树
TreeNode* build_tree() {
int num_children;
printf("Enter the value of the root node: ");
int val;
scanf("%d", &val);
TreeNode* root = (TreeNode*) malloc(sizeof(TreeNode));
root->val = val;
printf("Enter the number of children for the root node: ");
scanf("%d", &num_children);
root->num_children = num_children;
if (num_children > 0) {
root->children = (TreeNode**) malloc(num_children * sizeof(TreeNode*));
int i;
for (i = 0; i < num_children; i++) {
printf("Enter the value of child %d of the root node: ", i + 1);
root->children[i] = build_tree();
}
} else {
root->children = NULL;
}
return root;
}
// 前序遍历
void pre_order(TreeNode* root) {
if (root != NULL) {
printf("%d ", root->val);
int i;
for (i = 0; i < root->num_children; i++) {
pre_order(root->children[i]);
}
}
}
// 前序遍历非递归实现
void pre_order_iter(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[100];
int top = -1;
stack[++top] = root;
while (top >= 0) {
TreeNode* curr = stack[top--];
printf("%d ", curr->val);
int i;
for (i = curr->num_children
#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* leftChild;
struct BinaryTreeNode* rightChild;
} BinaryTreeNode;
// 用递归方式将一棵树转换为二叉树
BinaryTreeNode* treeToBinaryTree(TreeNode* root) {
if (root == NULL) {
return NULL;
}
BinaryTreeNode* binaryRoot = (BinaryTreeNode*) malloc(sizeof(BinaryTreeNode));
binaryRoot->data = root->data;
binaryRoot->leftChild = NULL;
binaryRoot->rightChild = NULL;
// 将子树的最右边的结点作为二叉树结点的右孩子
if (root->firstChild != NULL) {
BinaryTreeNode* binaryRightChild = treeToBinaryTree(root->firstChild);
binaryRoot->rightChild = binaryRightChild;
TreeNode* child = root->firstChild->nextSibling;
while (child != NULL) {
BinaryTreeNode* binaryChild = treeToBinaryTree(child);
binaryChild->rightChild = binaryRightChild;
binaryRightChild = binaryChild;
child = child->nextSibling;
}
binaryRoot->leftChild = binaryRightChild;
}
return binaryRoot;
}
// 树的前序遍历（递归）
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
printf("%d ", root->data);
TreeNode* child = root->firstChild;
while (child != NULL) {
preOrder(child);
child = child->nextSibling;
}
}
// 树的后序遍历（递归）
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* child = root->firstChild;
while (child != NULL) {
postOrder(child);
child = child->nextSibling;
}
printf("%d ", root->data);
}
// 树的前序遍历（非递归）
void preOrderNonRecursive(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* child = node->firstChild;
while (child != NULL) {
stack[++top] = child;
child = child->nextSibling;
}
}
}
// 树的后序遍历（非递归）
void postOrderNonRecursive(TreeNode* root) {
if (root == NULL) {
return;
}
TreeNode* stack[100];
int top = -1;
TreeNode* lastVisited = NULL;