实现二叉树中所有节点左右子树的交换

#include<stdio.h>#include<malloc.h>#include<conio.h>typedef struct BiTreeNode{int data;struct BiTreeNode *lchild,*rchild;}BiTreeNode,*Bitree;void Inorder(BiTreeNode *Bt){if(Bt!=NULL){Inorder(Bt->lchild);printf("%d ",Bt->data);Inorder(Bt->rchild);}}void InsertBST(BiTreeNode *&Bt,int k){if(Bt==NULL){Bt=(BiTreeNode *)malloc(sizeof(BiTreeNode));Bt->data=k;Bt->lchild=NULL;Bt->rchild=NULL;}else{if(Bt->data>k){InsertBST(Bt->lchild,k);}if(Bt->data<k){InsertBST(Bt->rchild,k);}}}void Exchang(BiTreeNode *&Bt){if(Bt!=NULL){BiTreeNode *r;Bt->lchild=Bt->rchild;Bt->rchild=r;Exchang(Bt->lchild);Exchang(Bt->rchild);}}main(){BiTreeNode *Bt=NULL;printf("please input data and end with 0:\n");int k;scanf("%d",&k);while(k!=0){InsertBST(Bt,k);scanf("%d",&k);}Inorder(Bt);printf("\nthe order after exchanging is:\n");#include<stdio.h>#include<malloc.h>#include<conio.h>typedef struct BiTreeNode{int data;struct BiTreeNode *lchild,*rchild;}BiTreeNode,*Bitree;void Inorder(BiTreeNode *Bt){if(Bt!=NULL){Inorder(Bt->lchild);printf("%d ",Bt->data);Inorder(Bt->rchild);}}void InsertBST(BiTreeNode *&Bt,int k){if(Bt==NULL){Bt=(BiTreeNode *)malloc(sizeof(BiTreeNode));Bt->data=k;Bt->rchild=NULL;}else{if(Bt->data>k){InsertBST(Bt->lchild,k);}if(Bt->data<k){InsertBST(Bt->rchild,k);}}}void Exchang(BiTreeNode *&Bt){if(Bt!=NULL){BiTreeNode *r;r=Bt->lchild;Bt->lchild=Bt->rchild;Bt->rchild=r;Exchang(Bt->lchild);Exchang(Bt->rchild);}}main(){BiTreeNode *Bt=NULL;printf("please input data and end with 0:\n");int k;scanf("%d",&k);while(k!=0){InsertBST(Bt,k);scanf("%d",&k);}Inorder(Bt);printf("\nthe order after exchanging is:\n");Exchang(Bt);Inorder(Bt);getch(); Exchang(Bt);Inorder(Bt);getch();}。

实现二叉树中所有节点左右子树的交换在二叉树中，交换每个节点的左右子树可以通过递归算法实现。

让我们来看看如何实现这个功能。

首先，我们需要定义一个二叉树的节点类（Node），该类包含一个值属性和左右子树属性。

我们还可以添加一些其他方法来获取和设置节点的值以及左右子树。

```pythonclass Node:def __init__(self, value):self.value = valueself.left = Noneself.right = None```接下来，我们可以定义一个函数来交换每个节点的左右子树。

遍历二叉树的每个节点，并通过交换节点的左右子树来实现。

```pythondef swap_tree(node):if node is None:returntemp = node.leftnode.left = node.rightnode.right = tempswap_tree(node.left)swap_tree(node.right)```我们可以使用先序遍历的方法来遍历二叉树，即先访问根节点，然后递归地遍历左子树和右子树。

在遍历每个节点时，我们交换其左右子树。

最后，我们可以在一个示例二叉树上测试我们的代码。

假设我们有以下二叉树：```/\23/\\456```下面是测试代码和输出结果：```python#创建二叉树root = Node(1)root.left = Node(2)root.right = Node(3)root.left.left = Node(4)root.left.right = Node(5)root.right.right = Node(6)#交换每个节点的左右子树swap_tree(root)#打印交换后的二叉树#输出结果：132654def print_tree(node):if node is None:returnprint(node.value, end=" ")print_tree(node.left)print_tree(node.right)print_tree(root)```以上代码将输出交换后的二叉树的先序遍历结果：132654、可以看到，通过交换每个节点的左右子树，我们成功地改变了二叉树的结构。

//交换左右子树的程序代码#include<stdio.h>#include<malloc.h>//二叉链表的结构类型定义const int maxsize=1024;typedef char datatype;typedef struct node{datatype data;struct node *lchild,*rchild;}bitree;bitree*creattree();void preorder(bitree*);void swap(bitree*);void main(){bitree*pb;pb=creattree();preorder(pb);printf("\n");swap(pb);preorder(pb);printf("\n");}//二叉树的建立bitree*creattree(){char ch;bitree*Q[maxsize];int front,rear;bitree*root,*s;root=NULL;front=1;rear=0;printf("按层次输入二叉树，虚结点输入'@'，以'#'结束输入：\n");while((ch=getchar())!='#'){s=NULL;if(ch!='@'){s=(bitree*)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;}rear++;Q[rear]=s;if(rear==1)root=s;else{if(s&&Q[front])if(rear%2==0)Q[front]->lchild=s;else Q[front]->rchild=s;if(rear%2==1)front++;}}return root;}//先序遍历按层次输出二叉树void preorder(bitree*p){if(p!=NULL){printf("%c",p->data);if(p->lchild!=NULL||p->rchild!=NULL){printf("(");preorder(p->lchild);if(p->rchild!=NULL)printf(",");preorder(p->rchild);printf(")");}}}//交换左右子树void swap(bitree*p){bitree*t;if(p!=NULL){if(p->lchild!=NULL&&p->rchild!=NULL&&p->lchild->data>p->rchild->data){t=p->lchild;p->lchild=p->rchild;p->rchild=t;}swap(p->lchild);swap(p->rchild);}}。

第五章树11．不含任何结点的空树( )A）是一棵树 B）是一棵二叉树Ｃ）既不是树也不是二叉树 D）是一棵树也是一棵二叉树12．二叉树是非线性数据结构，所以( )A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储;C）顺序存储结构和链式存储结构都能存储; D）顺序存储结构和链式存储结构都不能使用13．把一棵树转换为二叉树后，这棵二叉树的形态是( )A）唯一的 B）有多种C）有多种，但根结点都没有左孩子 D）有多种，但根结点都没有右孩子9. 11 ， 8 ， 6 ， 2 ， 5 的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A) 24 B) 72 C) 48 D) 5310.一棵含18个结点的二叉树的高度至少为( )A) 3 B) 4 C) 6 D) 511.下面的二叉树中，( C )不是完全二叉树。

10. 设结点x和结点y是二叉树T中的任意两个结点，若在前序序列中x在y之前，而在中序序列中x在y之后，则x和y的关系是（）A）x是y的左兄弟 B）x是y的右兄弟C）y是x的祖先 D）y是x的孩子11.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是（）A） 6 B） 5 C） 4 D） 37．下列陈述中正确的是（）A）二叉树是度为2的有序树B）二叉树中结点只有一个孩子时无左右之分C）二叉树中必有度为2的结点D）二叉树中最多只有两棵子树，并且有左右之分8. 树最适合用来表示（）A）有序数据元素 B）无序数据元素C）元素之间具有分支层次关系的数据 D）元素之间无联系的元素9. 3个结点有（）不同形态的二叉树A） 2 B） 3 C） 4 D） 56．二叉树是非线性数据结构，( )A）它不能用顺序存储结构存储; B）它不能用链式存储结构存储;C）顺序存储结构和链式存储结构都能存储;D）顺序存储结构和链式存储结构都不能使用7．二叉树上叶结点数等于( )A ) 分支结点数加1B ) 单分支结点数加1C ) 双分支结点数加1D ) 双分支结点数减18．如将一棵有n个结点的完全二叉树按顺序存放方式，存放在下标编号为0, 1,…, n-1的一维数组中，设某结点下标为k(k>0)，则其双亲结点的下标是( )A ) (k-1)/2B ) (k+1)/2C ) k/2D ) k-18. 树最适合用来表示（）。

二叉树和树的转换算法二叉树和树之间的转换算法涉及将一个数据结构转换为另一个数据结构的过程。

在这里，我们将讨论将树转换为二叉树和将二叉树转换为树的算法。

首先，让我们来讨论将树转换为二叉树的算法。

树是一种非线性数据结构，它包含一个根节点以及零个或多个子树，每个子树也是一棵树。

而二叉树是一种特殊的树，每个节点最多有两个子节点。

因此，将树转换为二叉树的算法需要考虑如何安排节点的子节点，以便符合二叉树的定义。

一种常见的将树转换为二叉树的算法是使用前序遍历。

具体步骤如下：1. 从树的根节点开始，将其作为二叉树的根节点。

2. 对于树的每个子树，将其第一个子节点作为二叉树的左子节点，将其余的子节点作为左子节点的右子节点。

3. 递归地对每个子树执行上述步骤，直到整棵树都被转换为二叉树。

接下来，让我们来讨论将二叉树转换为树的算法。

二叉树是一种特殊的树，每个节点最多有两个子节点。

而树是一种非线性数据结构，每个节点可以有任意数量的子节点。

因此，将二叉树转换为树的算法需要考虑如何将二叉树的节点重新组织成树的节点。

一种常见的将二叉树转换为树的算法是使用后序遍历。

具体步骤如下：1. 从二叉树的根节点开始，将其作为树的根节点。

2. 对于二叉树的每个节点，如果该节点有右子节点，将其右子节点作为树节点的子节点。

3. 递归地对每个节点执行上述步骤，直到整棵二叉树都被转换为树。

需要注意的是，在进行树和二叉树的转换时，可能会涉及到节点的重新连接和指针的调整，需要仔细处理节点之间的关系，确保转换后的数据结构仍然保持原始树或二叉树的结构特点。

总之，树和二叉树之间的转换算法涉及到对节点的重新组织和连接，需要根据具体的数据结构特点来设计相应的算法。

希望这些信息能够帮助你理解树和二叉树之间的转换过程。

交换左右⼦树可能编译时会有些语法⼩错误（⽐如分号，->，等），很容易就⾃⼰纠正了哦，思路绝对是完全正确的，所以⽤的话就⾃⼰试着改改吧，直接复制粘贴，就正确，岂不是太没写代码体验了，⾃⼰改改才印象更加深刻的呢(▽)~~~~；交换左右⼦树//算法5.5 计算⼆叉树的深度，增加左右⼦数交换等功能#include<iostream>using namespace std;//⼆叉树的⼆叉链表存储表⽰typedef struct BiNode{char data; //结点数据域struct BiNode *lchild,*rchild; //左右孩⼦指针}BiTNode,*BiTree;//⽤算法5.3建⽴⼆叉链表void CreateBiTree(BiTree &T){//按先序次序输⼊⼆叉树中结点的值（⼀个字符），创建⼆叉链表表⽰的⼆叉树Tchar ch;cin >> ch;if(ch=='#') T=NULL; //递归结束，建空树else{T=new BiTNode;T->data=ch; //⽣成根结点CreateBiTree(T->lchild); //递归创建左⼦树CreateBiTree(T->rchild); //递归创建右⼦树} //else} //CreateBiTreeint Depth(BiTree T){int m,n;if(T == NULL ) return 0; //如果是空树，深度为0，递归结束else{m=Depth(T->lchild); //递归计算左⼦树的深度记为mn=Depth(T->rchild); //递归计算右⼦树的深度记为nif(m>n) return(m+1); //⼆叉树的深度为m 与n的较⼤者加1else return (n+1);}}void InOrderTraverse(BiTree T){//中序遍历⼆叉树T的递归算法if(T){InOrderTraverse(T->lchild);cout << T->data;InOrderTraverse(T->rchild);}}void inChangeLR(BiTree &T){BiTree temp;if(T){if(T->lchild==NULL&&T->rchild==NULL){return;} else{temp=T->lchild;T->lchild = T->rchild;T->rchild=temp;}inChangeLR(T->lchild);inChangeLR(T->rchild);}}void preChangeLR(BiTree &T){BiTree temp;if(T){inChangeLR(T->lchild);if(T->lchild==NULL&&T->rchild==NULL){return;} else{temp=T->lchild;T->lchild = T->rchild;T->rchild=temp;}inChangeLR(T->rchild);}}void postChangeLR(BiTree &T){BiTree temp;if(T){inChangeLR(T->lchild);inChangeLR(T->rchild);if(T->lchild==NULL&&T->rchild==NULL){ return;} else{temp=T->lchild;T->lchild = T->rchild;T->rchild=temp;}}}int main(){BiTree tree;cout<<"请输⼊建⽴⼆叉链表的序列：\n";CreateBiTree(tree);InOrderTraverse(tree);cout<<"数的深度为："<<Depth(tree)<<endl; cout<<"中序遍历的结果为：\n";InOrderTraverse(tree);cout<<"\n";//以下三种执⾏其中⼀种cout<<"交换后中序遍历的结果为：\n";inChangeLR(tree);InOrderTraverse(tree);cout<<"\n";cout<<"交换后前序序遍历的结果为：\n";preChangeLR(tree);InOrderTraverse(tree);cout<<"\n";cout<<"交换后后序遍历的结果为：\n";postChangeLR(tree);InOrderTraverse(tree);return 0;}。

写出二叉树中左右节点互换的算法精品1.递归实现：递归是一种常见的解决树相关问题的方法。

对于二叉树的左右节点互换，我们可以按照以下步骤进行递归实现：1)如果当前节点为空，则返回。

2)交换当前节点的左子树和右子树。

3)递归调用左子树。

4)递归调用右子树。

以下是递归实现的示例代码：```javapublic void invertTree(TreeNode root)if (root == null)return;}//交换当前节点的左子树和右子树TreeNode temp = root.left;root.left = root.right;root.right = temp;//递归调用左子树和右子树invertTree(root.left);invertTree(root.right);```这个算法是比较简单和直观的，对于每个节点，我们交换其左子树和右子树，然后递归交换其左子节点和右子节点。

2.非递归实现:使用非递归的方式实现二叉树中左右节点互换可以通过迭代算法，即使用栈或队列来辅助完成。

下面是一种常见的基于栈的非递归实现方法：首先将根节点入栈，然后进入循环直到栈为空。

在循环中，首先弹出栈顶节点，然后交换其左子节点和右子节点。

如果弹出的节点存在左子节点，则将左子节点入栈；如果弹出的节点存在右子节点，则将右子节点入栈。

重复这个过程直到栈为空。

以下是非递归实现的示例代码：```javapublic void invertTree(TreeNode root)if (root == null)return;}//创建一个栈，并将根节点入栈Stack<TreeNode> stack = new Stack<>(;stack.push(root);while (!stack.empty()TreeNode node = stack.pop(;//交换当前节点的左子树和右子树TreeNode temp = node.left;node.left = node.right;node.right = temp;//如果当前节点存在左子节点，则将左子节点入栈if (node.left != null)stack.push(node.left);}//如果当前节点存在右子节点，则将右子节点入栈if (node.right != null)stack.push(node.right);}}```3.层序遍历实现：层序遍历是一种广度优先（BFS）的方法，它按照树的层级从上到下访问每个节点。

c交换左右子树的算法非递归前言：本文旨在介绍一种非递归的交换左右子树的算法，通过该算法，可以在C语言中实现树结构的左右子树交换操作。

树是一种常见的数据结构，广泛应用于计算机科学中，而交换左右子树是树操作中的一种常见操作。

本文将详细介绍该算法的实现过程和代码示例。

一、算法描述：非递归交换左右子树算法的基本思路是使用栈来模拟递归过程。

首先，将根节点入栈，同时将根节点的左子树和右子树分别压入另一个栈中。

然后，依次弹出左子树和右子树的节点，并交换它们的左右子节点。

当所有节点都被弹出后，再将根节点从另一个栈中弹出，并交换其左右子树。

二、代码实现：以下是一个基于上述算法的C语言代码实现示例：```c#include <stdio.h>#include <stdlib.h>// 定义树节点结构体typedef struct TreeNode {int val;struct TreeNode* left;struct TreeNode* right;} TreeNode;// 非递归交换左右子树函数void swap_subtrees(TreeNode* root) {// 创建一个空栈来模拟递归过程TreeNode* stack[100];int top = -1;stack[++top] = root; // 将根节点入栈while (top >= 0) {TreeNode* node = stack[top--]; // 弹出当前节点if (node->left) { // 如果当前节点有左子树，将其压入另一个栈中stack[++top] = node->left;}if (node->right) { // 如果当前节点有右子树，将其压入另一个栈中stack[++top] = node->right;}}// 交换左右子树TreeNode* temp = root->left; // 保存当前节点的左子树root->left = root->right; // 交换当前节点的左右子树root->right = temp; // 将保存的左子树重新赋值给当前节点的右子树}```三、使用示例：以下是一个简单的使用示例，展示如何使用上述代码实现交换左右子树的操作：```cint main() {// 创建一棵二叉树并初始化数据TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));root->val = 1;root->left = (TreeNode*)malloc(sizeof(TreeNode));root->left->val = 2;root->right = (TreeNode*)malloc(sizeof(TreeNode));root->right->val = 3;root->left->left = NULL; // 左子树为空树结构root->right->right = NULL; // 右子树为空树结构// 交换左右子树并输出结果swap_subtrees(root);printf("交换后的二叉树为：\n");print_tree(root); // 输出二叉树结构，以验证交换结果是否正确return 0;}```四、总结：本文介绍了非递归的交换左右子树的算法，并给出了相应的C语言代码实现示例。

#include <stdio.h>#include <malloc.h>#include <conio.h>#include<stdlib.h>#define MaxSize 100typedef char ElemType;typedef struct node{ElemType data;//数据元素struct node *lchild; //指向左孩子struct node *rchild; //指向右孩子} BTNode;void CreateBTNode(BTNode *&b,char *str)//创建二叉树{BTNode *st[MaxSize],*p=NULL;//BTNode *st[MaxSize]定义了一个栈，以栈的方式来实现二叉树元素的录入int top=-1,k,j=0;char ch;b=NULL;ch=str[j];while(ch!='\0'){switch(ch){case'(':top++;st[top]=p;k=1;break;case')':top--;break;case',':k=2;break;default:p=(BTNode *)malloc(sizeof(BTNode));p->data=ch;p->lchild=p->rchild=NULL;if(b==NULL){b=p;}else{switch(k){case 1:st[top]->lchild=p;break;case 2:st[top]->rchild=p;break;}}}j++;ch=str[j];}}BTNode *findNode(BTNode *b,ElemType x)//查找结点,找到结点后返回其指针，否则返回空指针{BTNode *p;if(b==NULL){return NULL;}else{if(b->data==x){return b;}else{p=findNode(b->lchild,x);if(p!=NULL){return p;}else{return findNode(b->rchild,x);}}}}int nodes(BTNode *b){int num1,num2;if(b==NULL)//原错误语句：b->data==NULL{return 0;}else{num1=nodes(b->lchild);num2=nodes(b->rchild);return (num1+num2+1);}}int yezinodes(BTNode *b)//叶子结点个数{int num1,num2;if(b==NULL){return 0;}else{if(b->lchild==NULL&&b->rchild==NULL){return 1;}else{num1=yezinodes(b->lchild);num2=yezinodes(b->rchild);return(num1+num2);}}}void parent(BTNode *b,ElemType x)//查找双亲{BTNode *t;if(b==NULL){return;}else{if(b->data==x){printf("此结点是根结点，无双亲！\n");return;}else{if(b->lchild!=NULL&&b->lchild->data==x||b->rchild!=NULL&&b->rchild->data==x) {t=b;printf("此结点的双亲为：%c\n",t->data);return;}else{parent(b->lchild,x);parent(b->rchild,x);}}}}void BTreeChange(BTNode *&b)//交换左右孩子算法{BTNode *p;if(b==NULL){return;}else{if(b->lchild==NULL&&b->rchild==NULL){return ;}else{p=b->lchild;b->lchild=b->rchild;b->rchild=p;BTreeChange(b->lchild);BTreeChange(b->rchild);}}}BTNode *LchildNode(BTNode *p)//找左孩子结点问题：这边的函数该如何引用{return p->lchild;}BTNode *RchildNode(BTNode *p)//找右孩子结点{return p->rchild;}int BTNodeHeight(BTNode *b)//求树的高度{int lchild,rchild;if(b==NULL){return (0);}else{lchild=BTNodeHeight(b->lchild);rchild=BTNodeHeight(b->rchild);return (lchild>rchild)?(lchild+1):(rchild+1);}}void DispBTNode(BTNode *b)//输出二叉树{if(b!=NULL){printf("%c",b->data);if(b->lchild!=NULL||b->rchild!=NULL){printf("(");DispBTNode(b->lchild);if(b->rchild!=NULL){printf(",");}DispBTNode(b->rchild);printf(")");}}}void PreOrder(BTNode *b, int i)//前序遍历{if(b!=NULL){printf("%c %d \n",b->data,i);PreOrder(b->lchild,i+1);PreOrder(b->rchild,i+1);}}void InOrder(BTNode *b)//中序遍历{if(b!=NULL){InOrder(b->lchild);printf("%c",b->data);InOrder(b->rchild);}}void PostOrder(BTNode *b)//后序遍历{if(b!=NULL){PostOrder(b->lchild);PostOrder(b->rchild);printf("%c",b->data);}}void main(){char cc[]={"A(B(D(,G)),C(E,F))"};BTNode *b;BTNode *q;BTNode *t;char c;int p;printf("创建二叉树！\n");CreateBTNode(b,cc); //CreateBTNode函数用于根据括号表示法构建二叉链表，此函数在实验指导书上printf("创建二叉树成功！\n");printf("1.二叉树的括号表示法为：\n");DispBTNode(b);printf("\n");p=BTNodeHeight(b);printf("2.二叉树的深度为：%d\n",p);printf("3.二叉树的结点总数为：%d\n",nodes(b));printf("4.二叉树的叶子结点个数为：%d\n",yezinodes(b));printf("5.请输入一个结点：\n");scanf("%c",&c);t=findNode(b,c);if(t==NULL){printf("二叉树为空！\n");}else{if(t->lchild!=NULL){printf("此结点的左孩子是：%c\n",LchildNode(t)->data);}else{printf("此结点的左孩子不存在！\n");}if(t->rchild!=NULL){printf("此结点的右孩子是：%c\n",RchildNode(t)->data);}else{printf("此结点的右孩子不存在！\n");}}parent(b,c);printf("\n");printf("6.二叉树的前序遍历为:\n");PreOrder(b,0);printf("\n");printf("7.二叉树的中序遍历为:\n");InOrder(b);printf("\n");printf("8.二叉树的后序遍历为:\n");PostOrder(b);printf("\n");BTreeChange(b);printf("交换后的二叉树输出如下：\n");DispBTNode(b);printf("\n");}。

数据结构课程设计实验报告题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院专业班级：计算机科学与技术1003班姓名：叶成功学号：指导教师：陈国良教授李立三教授日期：2012年7月3日目录二、基本要求 .............................................................................................................................三、数据结构的设计 .................................................................................................................1、结点的数据结构 ...............................................................................................................2、基本操作 ...........................................................................................................................四、软件模块结构图 .................................................................................................................五、程序设计思想 .....................................................................................................................1、程序设计基本思想 ...........................................................................................................2、程序设计基本思想 ...........................................................................................................六、程序流程图 .........................................................................................................................1、创建函数 ...........................................................................................................................2、前序遍历函数 ...................................................................................................................3、中序遍历函数 ...................................................................................................................4、后序遍历函数 ...................................................................................................................5、层序遍历函数 ...................................................................................................................6、左右子树交换函数 ...........................................................................................................7、二叉树打印函数 ...............................................................................................................8、遍历调用函数 ...................................................................................................................9、菜单函数 ...........................................................................................................................10、主函数 .............................................................................................................................七、源程序代码 .........................................................................................................................八、调试分析 .............................................................................................................................九、数据测试 .............................................................................................................................1、主菜单界面 .......................................................................................................................2、建立一棵有二十个结点的完全二叉树 ...........................................................................3、打印二叉树 .......................................................................................................................4、遍历二叉树 .......................................................................................................................5、二叉树左右子树交换 .......................................................................................................6、交换后打印二叉树 ...........................................................................................................7、交换后二叉树的遍历 .......................................................................................................8、退出程序 ...........................................................................................................................十、用户使用手册 .....................................................................................................................十一、心得体会 .........................................................................................................................一、问题描述二叉树是一种常见的特殊的树型结构，在计算机领域有着极为广泛的应用。

⼆叉树五种遍历⽅法以及之间的转换1. 前序遍历：根左右　中序遍历：左根右　后序遍历：左右根2.深度优先遍历：（先进去的后出来）利⽤栈：先压右⼦树，再压左⼦树　⼴度优先遍历：（先进去的先出来）利⽤队列：先压左⼦树，再压右⼦树3.利⽤前中序重建⼆叉树：node *root = new node; //注意要new空间（不然⽆法运⾏）#include<iostream>#include<cstring>#include<stack>#include<queue>using namespace std;struct node{char c;node *lc;node *rc;};node* rebuild(char pre[],char in[],int len){ //已知前中序重建⼆叉树if(len==0)return NULL;node *root = new node; //注意要new空间root->c = pre[0];int i=0;for(;i<len;i++){if(in[i]==pre[0]) break;}root->lc = rebuild(pre+1,in,i);root->rc = rebuild(pre+i+1,in+i+1,len-i-1);return root;}void dfs(node *root){ //栈，先压右节点，再压左节点stack<node *> s;s.push(root);while(!s.empty()){root=s.top();cout<<root->c<<"";s.pop();if(root->rc!=NULL){s.push(root->rc);}if(root->lc!=NULL){s.push(root->lc);}}}void bfs(node *root){//队列：先压左节点，再压右节点queue<node *> q;q.push(root);while(!q.empty()){root=q.front();cout<<root->c<<"";q.pop();if(root->lc){q.push(root->lc);}if(root->rc){q.push(root->rc);}}}void pre_order(node* root){ //前序遍历if(root != NULL){cout<<root->c<<"";pre_order(root->lc);pre_order(root->rc);}}void in_order(node* root){ //中序遍历if(root != NULL){in_order(root->lc);cout<<root->c<<"";in_order(root->rc);}}void post_order(node* root){ //后序遍历if(root != NULL){post_order(root->lc);post_order(root->rc);cout<<root->c<<"";}}int main(){char pre[50] = "ABDHLEKCFG"; //前序序列char in[50] = "HLDBEKAFCG"; //中序序列int len=strlen(in);node *root = rebuild(pre,in,len);pre_order(root);cout<<endl;post_order(root);cout<<endl;dfs(root);cout<<endl;bfs(root);}。

二叉树中所有节点的左右子树相互交换递归与非递归程序(2006-10-11 11:24:09)转载分类：数据结构//将二叉树中所有节点的左右子树相互交换BiNode* Exchange(BiNode* T){BiNode* p;if(NULL==T || (NULL==T->lchild && NULL==T->rchild)) return T;p = T->lchild;T->lchild = T->rchild;T->rchild = p;if(T->lchild){T->lchild = Exchange(T->lchild);}if(T->rchild){T->rchild = Exchange(T->rchild);}return T;}//将二叉树中所有节点的左右子树相互交换//不使用递归void NonRecursive_Exchange(BiNode* T){Stack s;BiNode* p;if(NULL==T)return;InitStack(&s);Push(&s,T);while(!isEmpty(&s)){T = Pop(&s);p = T->lchild;T->lchild = T->rchild;T->rchild = p;if(T->rchild)Push(&s,T->rchild);if(T->lchild)Push(&s,T->lchild); }DestroyStack(&s);}//递推形式的前续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记void Iteration_Mark_PreOrderTraverse(BiPMNode* T) {if(NULL == T)return;while(NULL != T){if(0 == T->mark){T->mark ++;printf("%d ",T->data);while(NULL != T->lchild){T = T->lchild;T->mark ++;printf("%d ",T->data);}T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(1 == T->mark){T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(2 == T->mark){T = T->parent;}}}//递推形式的中续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记void Iteration_Mark_InOrderTraverse(BiPMNode* T) {if(NULL == T)return;while(NULL != T){if(0 == T->mark){T->mark ++;while(NULL != T->lchild){T = T->lchild;T->mark ++;}printf("%d ",T->data);T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(1 == T->mark){printf("%d ",T->data);T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(2 == T->mark){T = T->parent;}}}//递推形式的后续遍历，不使用递归和堆栈，//但每个节点增加了一个parent指针和Mark标记void Iteration_Mark_PostOrderTraverse(BiPMNode* T) {if(NULL == T)return;while(NULL != T){if(0 == T->mark){T->mark ++;while(NULL != T->lchild){T = T->lchild;T->mark ++;}T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(1 == T->mark){T->mark ++;if(NULL != T->rchild)T = T->rchild;continue;}if(2 == T->mark){printf("%d ",T->data);T = T->parent;}}}二叉树层次遍历(2006-10-10 11:12:31)转载分类：数据结构//二叉树的层次遍历，使用队列实现void LayerOrderTraverse(BiNode* T) {Queue q;if(NULL == T)return;InitQueue(&q);EnQueue(&q,T);while(!isQueueEmpty(&q)){T = DeQueue(&q);printf("%d ",T->data);if(T->lchild)EnQueue(&q,T->lchild);if(T->rchild)EnQueue(&q,T->rchild);}DestroyQueue(&q);}typedef struct _QNode{BiNode* data;struct _QNode* next;}QNode;typedef struct _queue{QNode* front;QNode* rear;}Queue;void InitQueue(Queue* q){q->front = q->rear = (QNode*)malloc(sizeof(QNode)); q->front->next = NULL;}bool isQueueEmpty(Queue* q){if(q->front == q->rear)return true;elsereturn false;}void EnQueue(Queue* q, BiNode* data){QNode* pNode;pNode = (QNode*)malloc(sizeof(QNode));pNode->data = data; pNode->next = NULL;q->rear->next = pNode;q->rear = pNode;}BiNode* DeQueue(Queue* q){QNode* pNode;BiNode* pData;assert(q->front != q->rear); pNode = q->front->next;q->front->next = pNode->next; if(q->rear == pNode){q->rear = q->front;}pData = pNode->data;free(pNode);return pData;}void DestroyQueue(Queue* q) {while(NULL != q->front){q->rear = q->front->next;free(q->front);q->front = q->rear;}}二叉排序树-创建(2006-10-10 10:05:04)转载分类：数据结构typedef struct BiNode{int data;struct BiNode *lchild;struct BiNode *rchild;}BiNode;BiNode* Insert(BiNode* T, int data){if(NULL == T){T = (BiNode*)malloc(sizeof(BiNode));T->data = data;T->lchild = NULL;T->rchild = NULL;return T;}if(data <= T->data)T->lchild = Insert(T->lchild, data);elseT->rchild = Insert(T->rchild, data);return T;}//创建一个二叉排序树, input -1 to endBiNode* createBiSortTree(){BiNode *root = NULL;int data;while(1){scanf("%d",&data);if(-1 == data)break;root = Insert(root, data);}return root;}查看文章交换二叉树所有节点的左右子树2010-12-03 21:44//实验题目：已知二叉树以二叉链表作为存储结构，写一个算法来交换二叉树的所有节点的左右子树//先建立二叉树的二叉链表存储结构，再完成算法，注意结果的输出形式#include <stdio.h>#include <malloc.h>#include <windows.h>#define STACK_INIT_SIZE 100;#define STACKINCREMENT 10;//定义二叉树数据类型typedef char TElemtype;typedef struct BiTNode{TElemtype data;struct BiTNode *lchild,*rchild;}BiTNode,*BiTree;//-------二叉树基本操作-------//初始化二叉树bool InitBiTree(BiTree &T){T=(BiTree)malloc(sizeof(BiTNode));T->data=NULL;T->lchild=NULL;T->rchild=NULL;return true;}//创建二叉树void CreateBiTree(BiTree &T){TElemtype c=' ';c=getchar();getchar();if(c==' '){T=NULL;}else{InitBiTree(T);T->data=c;CreateBiTree(T->lchild);CreateBiTree(T->rchild); }}//操作函数---输出bool Visit(TElemtype e){if(e!=NULL){printf("%c ",e);return true;}else{return false;}//先序遍历二叉树bool PreOrderTraverse(BiTree T,bool Visit(TElemtype)) {if(T){if(Visit(T->data)){if (PreOrderTraverse(T->lchild,Visit)){if (PreOrderTraverse(T->rchild,Visit)){return true;}}}return false;}else{return true;}}//----------------------------//定义栈的数据类型typedef struct{TElemtype *base;TElemtype *top;int stacksize;}SqStack;//交换左右子树void exchange(BiTree &rt){BiTree temp = NULL;if(rt->lchild == NULL && rt->rchild == NULL)return;else{temp = rt->lchild;rt->lchild = rt->rchild;rt->rchild = temp;}if(rt->lchild)exchange(rt->lchild);if(rt->rchild)exchange(rt->rchild);}//-------Main函数----void main(){BiTree T;MessageBox(NULL,"请按照先序遍历输入二叉树！","提示",MB_OK|MB_ICONWARNING); MessageBox(NULL,"请输入数据！(空格表示结束)","提示",MB_OK|MB_ICONWARNING); CreateBiTree(T);MessageBox(NULL,"输入结束！","提示",MB_OK|MB_ICONWARNING);printf("\n按先序输出\n");PreOrderTraverse(T,Visit);MessageBox(NULL,"输出结束！","提示",MB_OK|MB_ICONWARNING);printf("\n交换后\n");exchange(T);PreOrderTraverse(T,Visit);}二叉树左右子树交换(麻烦)/*对任意一颗二叉树，是将其说有结点的左右子树交换，并将交换前后不同二叉树分别用层序、前序，中序三种不同的方法进行遍历。

c语言递归翻转二叉树C语言是一种非常常用且强大的编程语言，递归是C语言中的一种重要的编程技巧。

而翻转二叉树是递归的一种典型应用，本文将详细介绍如何使用C语言递归来翻转二叉树。

我们需要了解什么是二叉树。

二叉树是一种非常常见的数据结构，它由一组节点组成，每个节点最多有两个子节点。

其中，根节点是二叉树的最上面的节点，左子节点和右子节点分别是根节点的左边和右边的子节点。

现在，我们来看一下如何使用递归来翻转二叉树。

翻转二叉树的意思就是将二叉树中的每个节点的左子节点和右子节点交换位置。

具体的实现方法如下：我们需要定义一个递归函数来完成翻转操作，函数的参数是一个二叉树的根节点。

在这个函数中，我们首先需要判断根节点是否为空，如果为空，则直接返回。

如果不为空，则需要交换根节点的左子节点和右子节点，并分别递归调用翻转函数来翻转左子树和右子树。

具体的代码如下所示：```c#include<stdio.h>#include<stdlib.h>// 定义二叉树的结构体typedef struct TreeNode {int data;struct TreeNode* left;struct TreeNode* right;} TreeNode;// 定义翻转函数void invertTree(TreeNode* root) {// 判断根节点是否为空if (root == NULL) {return;}// 交换根节点的左子节点和右子节点TreeNode* temp = root->left;root->left = root->right;root->right = temp;// 递归调用翻转函数来翻转左子树和右子树 invertTree(root->left);invertTree(root->right);}// 创建二叉树TreeNode* createTree() {TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode)); root->data = 1;TreeNode* node2 = (TreeNode*)malloc(sizeof(TreeNode)); node2->data = 2;TreeNode* node3 = (TreeNode*)malloc(sizeof(TreeNode)); node3->data = 3;TreeNode* node4 = (TreeNode*)malloc(sizeof(TreeNode)); node4->data = 4;TreeNode* node5 = (TreeNode*)malloc(sizeof(TreeNode)); node5->data = 5;root->left = node2;root->right = node3;node2->left = node4;node2->right = node5;node3->left = NULL;node3->right = NULL;node4->left = NULL;node4->right = NULL;node5->left = NULL;node5->right = NULL;return root;}// 遍历二叉树void traversalTree(TreeNode* root) { if (root == NULL) {return;}printf("%d ", root->data);traversalTree(root->left);traversalTree(root->right);}int main() {// 创建二叉树TreeNode* root = createTree(); // 输出原始二叉树printf("原始二叉树：");traversalTree(root);printf("\n");// 翻转二叉树invertTree(root);// 输出翻转后的二叉树printf("翻转后的二叉树：");traversalTree(root);printf("\n");return 0;}```在上面的代码中，我们首先定义了一个二叉树的结构体，并且创建了一个函数来创建一个二叉树。