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

#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>#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");}。

二叉树中所有节点的左右子树相互交换递归与非递归程序(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);}二叉树左右子树交换(麻烦)/*对任意一颗二叉树，是将其说有结点的左右子树交换，并将交换前后不同二叉树分别用层序、前序，中序三种不同的方法进行遍历。

『NOIP2018普及组题解』<更新提⽰><第⼀次更新><正⽂>标题统计题⽬描述凯凯刚写了⼀篇美妙的作⽂，请问这篇作⽂的标题中有多少个字符？注意：标题中可能包含⼤、⼩写英⽂字母、数字字符、空格和换⾏符。

统计标题字符数时，空格和换⾏符不计算在内。

输⼊格式输⼊⽂件只有⼀⾏，⼀个字符串 s。

输出格式输出⽂件只有⼀⾏，包含⼀个整数，即作⽂标题的字符数（不含空格和换⾏符）。

样例数据input1234output13input2Ca 45output24样例说明样例 1 ：标题中共有 3 个字符，这 3 个字符都是数字字符。

样例 2 ：标题中共有 5 个字符，包括 1 个⼤写英⽂字母， 1 个⼩写英⽂字母和 2 个数字字符，还有 1 个空格。

由于空格不计⼊结果中，故标题的有效字符数为 4 个。

数据规模与约定规定∣s∣表⽰字符串 s 的长度（即字符串中的字符和空格数）。

对于 %40 的数据，1 ≤ |s| ≤ 5，保证输⼊为数字字符及⾏末换⾏符。

对于 %80 的数据，1 ≤ |s| ≤ 5，输⼊只可能包含⼤、⼩写英⽂字母、数字字符及⾏末换⾏符。

对于 %100 的数据，1 ≤ |s| ≤ 5，输⼊可能包含⼤、⼩写英⽂字母、数字字符、空格和⾏末换⾏符。

时间限制：1s空间限制：256MB解析T1和往年⼀样，还是签到题。

不过这⼀次好像更注重考察语⾔了，不少不熟悉语⾔的⼩伙伴可能就没有分了啦。

⼤概是考察如何处理输⼊吧，会⽤getline()的基本都⽤了getline()了吧，当然，不会⽤的还有其他的办法，主要是while(cin>>str)和scanf()读到换⾏符为⽌。

这样的话，只要暴⼒统计⼀下就可以了啦。

Code:#include<bits/stdc++.h>using namespace std;string s;int ans=0;int main(void){freopen("title.in","r",stdin);freopen("title.out","w",stdout);getline(cin,s);for(int i=0;i<s.size();i++){if(s[i]!=' ')ans++;}printf("%d\n",ans);return 0;}#include<bits/stdc++.h>using namespace std;char s;int ans=0;int main(){freopen("title.in","r",stdin);freopen("title.out","w",stdout);while (cin>>s){if(s>='0'&&s<='9'||s>='a'&&s<='z'||s>='A'&&s<='Z')ans++;}cout<<ans<<endl;return 0;}龙虎⽃题⽬描述轩轩和凯凯正在玩⼀款叫《龙虎⽃》的游戏，游戏的棋盘是⼀条线段，线段上有 n个兵营（⾃左⾄右编号 1 ∼n），相邻编号的兵营之间相隔1 厘⽶，即棋盘为长度为 n-1 厘⽶的线段。

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语言代码实现示例。

交换左右⼦树可能编译时会有些语法⼩错误（⽐如分号，->，等），很容易就⾃⼰纠正了哦，思路绝对是完全正确的，所以⽤的话就⾃⼰试着改改吧，直接复制粘贴，就正确，岂不是太没写代码体验了，⾃⼰改改才印象更加深刻的呢(▽)~~~~；交换左右⼦树//算法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;}。

//交换左右子树的程序代码#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. 树最适合用来表示（）。

九、编写算法交换二叉树中所有结点的左右子树#include"stdio.h"#include"malloc.h"#define maxsize 10#define NULL 0typedef struct node{char data;struct node *lchild,*rchild;}Bintree;Bintree *Q[maxsize]; //队列Q为指针类型，保存已输入的结点的地址///////////////建立二叉树，返回根指针Bintree *creatree(){char ch;int front=1,rear=0; //置空队列Bintree *T,*S;T=NULL; //置空二叉树ch=getchar(); //输入第一个结点信息while(ch!='#'){ //判断是否为结束符“#”S=NULL; //如果输入的是虚结点，则无需为虚结点申请空间if(ch!='@'){ //“@”表示虚结点，不是虚结点时建立新结点S=(Bintree *)malloc(sizeof(Bintree));S->data=ch;S->lchild=S->rchild=NULL;}rear++;Q[rear]=S; //将虚结点指针NULL或新结点地址入队if(rear==1) T=S; //输入的第一个结点为根结点else{ if(S!=NULL&&Q[front]!=NULL) //孩子和双亲结点均不是虚结点if(rear%2==0) Q[front]->lchild=S;else Q[front]->rchild=S;if(rear%2==1) front++; //结点*Q[front]的两个孩子处理完毕后，front++ }ch=getchar();}return T;}/////////////////先序遍历输出结点数据void printree(Bintree *T){if(T){ printf("%2c",T->data);printree(T->lchild);printree(T->rchild);}}/////////////////后序遍历交换左右子树void changetree(Bintree *T){if(T){ Bintree *A;changetree(T->lchild);changetree(T->rchild);A=T->lchild;T->lchild=T->rchild;T->rchild=A;}}//////////////////////////主函数的实现void main(){Bintree *TR;printf("创建二叉树：");TR=creatree(); //建立二叉链表printf("先序遍历输出初始化二叉树为：");printree(TR); //输出原表printf("\n");changetree(TR); //交换左右子树printf("先序遍历输出交换左右子树后的二叉树为："); printree(TR); //输出新表printf("\n");}。

二叉树的5种遍历方式一、前序遍历前序遍历是指在二叉树中，先访问根节点，然后按照先左后右的顺序遍历左右子树。

具体步骤如下：1. 访问根节点；2. 递归遍历左子树；3. 递归遍历右子树。

前序遍历的应用场景非常广泛。

例如，在二叉搜索树中，前序遍历可以用来实现树的查找操作；在表达式树中，前序遍历可以用来将表达式转换为前缀表达式。

二、中序遍历中序遍历是指在二叉树中，先按照中序遍历左子树，然后访问根节点，最后按照中序遍历右子树的顺序遍历整个二叉树。

具体步骤如下：1. 递归遍历左子树；2. 访问根节点；3. 递归遍历右子树。

中序遍历的一个重要应用是对二叉搜索树进行排序，因为中序遍历可以按照升序输出二叉搜索树中的节点值。

三、后序遍历后序遍历是指在二叉树中，先按照后序遍历左子树，然后按照后序遍历右子树，最后访问根节点的顺序遍历整个二叉树。

具体步骤如下：1. 递归遍历左子树；2. 递归遍历右子树；3. 访问根节点。

后序遍历的一个常见应用是计算表达式树的值，因为后序遍历可以按照逆波兰表达式的顺序遍历表达式树。

四、层序遍历层序遍历是指按照从上到下、从左到右的顺序逐层遍历二叉树的节点。

具体步骤如下：1. 将根节点入队；2. 循环执行以下步骤，直到队列为空：a. 出队一个节点，访问该节点；b. 将该节点的左子节点入队（如果存在）；c. 将该节点的右子节点入队（如果存在）。

层序遍历可以用来按层打印二叉树的节点值，也可以用来判断二叉树的深度。

五、深度优先遍历深度优先遍历是指在二叉树中，先访问根节点，然后按照深度优先的顺序遍历左右子树。

具体步骤如下：1. 访问根节点；2. 递归遍历左子树；3. 递归遍历右子树。

深度优先遍历的一个常见应用是判断二叉树是否对称。

通过比较左子树和右子树的节点值，可以判断二叉树是否对称。

深度优先遍历还可以用来解决一些搜索问题，例如在二叉树中查找路径等。

在实际应用中，根据具体的问题场景和需求，选择合适的遍历方式非常重要。

数据结构课程设计实验报告题目名称：实现二叉树中所有节点左右子树的交换学院：信息科学与工程学院专业班级：计算机科学与技术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);}。

写出二叉树中左右节点互换的算法精品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）的方法，它按照树的层级从上到下访问每个节点。

练习及参考答案一选择题：A．二叉树中任何一个结点的度都为2.＿B.二叉树的度为2C.一棵二叉树的度可小于2D.任何一棵二叉树中至少有一个结点的度为22.以二叉链表作为二叉树的存储结构，在具有n个结点的二叉链表中（n＞0），空链域的个数为（:C )。

A. 2n-1B. n-1C. n+1D. 2n+13.线索化二叉树中，某结点*p没有孩子的充要条件是（B)。

A. p->lchild=NULLB. p->ltag二1且p->rtag=1C. p -> ltag=0D. p->lchild=NULL且p->ltag=14.如果结点A有3个兄弟，而且B是A的双亲，则B的度是（B)。

A. 3B. 4C. 5D. 15.某二叉树T有n个结点，设按某种顺序对T中的每个结点进行编号，编号值为1,2，…，n，且有如下性质：T中任意结点v，其编号等于左子树上的最小编号减1，而v的右子树的结点中，其最小编号等于v左子树上结点的最大编号加1。

这是按（B)编号的。

A.中序遍历序列B.先序遍历序列．C.后序遍历序列D.层次顺序6.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，B中右指针域为空的结点有（C)个。

A. n-1B. nC. n＋1D. n＋27.一棵完全二叉树上有1001个结点，其中叶子结点的个数是（C)。

A. 500B. 501C. 490D. 4958.设森林F中有3棵树，第一，第二，第三棵树的结点个数分别为N1，N2和N3。

与森林F 对应的二叉树根结点的右子树上的结点个数是（D)。

A. N1B. N1＋N2C. N2D. N2＋N39.任何一棵二叉树的叶结点在先序、中序、后序遍历序列中的相对次序（A)。

A.不发生改变B发生改变 C.不能确定D:以上都不对10.若一棵二叉树的后序遍历序列为dabec，中序遍历序列为debac，则先序遍历序列为（D)。

A. cbedB. decabC. deabcD. cedba11.若一棵二叉树的先序遍历序列为abdgcefh;中序遍历的序列为dgbaechf,则后序遍霎历的结果为（D）。

数据结构习题及解析第6 章树和二叉树基础知识题6.1①已知一棵树边的集合为{ <I,M>,<I,N> <E,I><B,E><B,D><A,B><G,J><G,K><C,G><C,F>，<H,L><C,H><A,C>}请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？（3）哪个是结点G的双亲？（4）哪些是结点G的祖先？（5）哪些是结点G的孩子？（6）哪些是结点E的子孙？（7）哪些是结点E的兄弟？哪些是结点F的兄弟？（8）结点B和N的层次号分别是什么？（9）树的深度是多少？（10）以结点C为根的子树的深度是多少？6.2①一棵度为2的树与一棵二叉树有何区别？6.3①试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

6.4③一棵深度为H的满k叉树有如下性质；第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次顺序从1开始对全部结点的编号，问：（1）各层的结点树目是多少？（2）编号为p的结点的父结点（若存在）的编号是多少？（3）编号为p的结点的第i 个儿子结点（若存在）的编号是多少？（4）编号为p的结点有右兄弟的条件什么？其右兄弟的编号是多少？6.5②已知一棵树为k的树中有n1个度为1的结点，n2个度为2的结点,…n k个度为k 的结点,问该树中有多少个叶子结点?6.6③已知在一棵含有n个结点的树中,只有度为k的分支结点和度为0的叶子结点.试求该树含有的叶子结点的数目.6.7③一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？6.8④证明：一棵满k叉树上的叶子结点数n0和非叶子结点数n1 之间满足以下关系：n0 =（k - 1）n1+ 16.9②试分别推导出含有n个结点和含有n0个叶子结点的完全三叉树的深度H。