数据结构（五）——树和⼆叉树之⼆叉树遍历、先序和中序构建⼆叉树、⼆叉树
的的结构对称判断
代码中所⽤到的结构体定义
typedef struct Node
{
char ch;//存放数据
struct Node *lchild,*rchild;
struct Node *next;
} TreeNode,*BiTree;//定义树节点的结构体
⼆叉树的交互式建⽴及⼆叉树的三种遍历
⼆叉树的交互式建⽴
⼆叉树的交互式建⽴运⽤了递归的算法，以先输⼊数据，判断是否合法，再以（L R T）的形式进⾏⼆叉树的建⽴，其中，以‘#’作为递归结束符。
BiTree createBiTree()//建⽴⼆叉树
{
char e;
房屋无偿使用证明scanf("%c",&e);//输⼊数据
getchar();
if(e=='#')//判断是否有后续结点
return NULL;
el
{
BiTree n=(BiTree)malloc(sizeof(TreeNode));//申请空间
n->lchild=NULL;
n->rchild=NULL;
n->ch=e;
printf("Plea enter the left child of %c\n",e);
n->lchild=createBiTree();//创建左⼉⼦
printf("Plea enter the right child of %c\n",e);
n->rchild=createBiTree();//创建右⼉⼦
return n;
}
}
⼆叉树的前序遍历（T L R）
void preOrderTraver(BiTree p)//前序遍历
{
if(p==NULL)//判断是否遍历到底结点
return;
el
{
printf("%c",p->ch);
preOrderTraver(p->lchild);//遍历左⼦树
preOrderTraver(p->rchild);//遍历右⼦树
}渡口网络
}
⼆叉树的中序遍历（L T R）
void inOrderTraver(BiTree p)//中序遍历
{
if(p->lchild!=NULL)//判断是否存在左⼉⼦
{
inOrderTraver(p->lchild);//向左⼉⼦⾛⼀步
}
printf("%c",p->ch);
if(p->rchild!=NULL)//判断是否存在右⼉⼦
{
inOrderTraver(p->rchild);
return;
}
el if(p->rchild==NULL)
{
return;
}
}
⼆叉树的后序遍历（L R T）
void postOrderTraver(BiTree p)//后序遍历
我想变成一只小鸟{
if(p->lchild!=NULL)//判断是否存在左⼉⼦
{
postOrderTraver(p->lchild);//左⾛⼀步
}
if(p->rchild!=NULL)//判断是否存在右⼉⼦
{
postOrderTraver(p->rchild);//右⾛⼀步
}
医药师printf("%c",p->ch);
return;
}
根据前序与中序序列构造⼆叉树，并返回根节点
解决思想
可以运⽤递归的⽅法，解决⽅向是，在先序遍历中，找到根节点，即第⼀个数据为根节点。
再寻找中序排列中与前序序列第⼀个⼀样的数据，即寻找树的根节点。
寻找到后，以根节点为中⼼，将中序序列分成左⼦树的序列和右⼦树的序列，同时也将先序序列分成左⼦树序列和右⼦树序列。
进⾏递归，在递归过程中，将当前根结点的左⼉⼦指针指向左⼦树返回的根节点，右⼉⼦指针指向右⼦树返回来的根结点。
直到递归结束。
BiTree*BinaryTreeFromOrderings(char inorder[],char preorder[],int inorder_index,int preorder_index,int length)
{
//函数功能：根据前序与中序序列构造⼆叉树，并返回根节点
/
/参数说明：inorder：中序序列字符数组，preorder：前序序列字符数组,inorder_index：记录中序序列索引,preorder_index：记录前序序列索引，length：序列长度int i,j,k,l,m,n,i1,j1;
int x,y;
char e1;
char pr1[100],pr2[100];
char in1[100],in2[100];
memt(pr2,0,100);
memt(pr1,0,100);
memt(in1,0,100);
memt(in2,0,100);
BiTree n2,bt1,bt2;
e1=preorder[0];
for(i=0;i<strlen(inorder);i++)
{
if(inorder[i]==e1)//寻找中序排列中与前序序列第⼀个⼀样的数据
{
x=i;
民主生活会剖析材料break;
}
}女性人体摄影
n2=(BiTree)malloc(sizeof(TreeNode));
n2->lchild=NULL;
n2->rchild=NULL;
n2->ch=e1;//建⽴根节点
for(j=0;j<x;j++)
{
in1[j]=inorder[j];//复制中序排列中根结点左边的数据
}
y=x+1;
for(k=1,n=0;k<x+1;n++,k++)
{
pr1[n]=preorder[k];//复制先序排列中根结点左边的数据
}
if(x!=0)//如果根节点左边存在数据，则将当前根结点的左⼉⼦指向该数据的根结点
{
n2->lchild=BinaryTreeFromOrderings(in1,pr1,0,0,strlen(pr1));
}
for(l=y,m=0;l<strlen(inorder);m++,l++)//复制中序排列中根结点右⼦树的数据
{
in2[m]=inorder[l];
}
for(i1=0,j1=y;j1<strlen(inorder);i1++,j1++)//复制前序排列中根结点右⼦树的数据
{
pr2[i1]=preorder[j1];
}
if(m!=0)//如果根节点右边存在数据，则将当前根结点的右⼉⼦指向该数据的根结点
{
n2->rchild=BinaryTreeFromOrderings(in2,pr2,0,0,strlen(pr2));
}
return n2;
}
职业者
⼆叉树的结构对称判断和数据对称判断
⼆叉树的结构对称
其实结构对称的思想很简单，只需先遍历⼀下根节点，将树分为左⼦树和右⼦树，借助队列，两棵⼦树均以层次遍历的⽅法进⾏遍历，只是左⼦树的遍历顺序为从左到右，右⼦树的顺序为从右到左，只要保证每⼀步的遍历结果⼀样，直到遍历结束，则表⽰结构对称。
int isSymmetrical(BiTree root)
{
{
//判断以root为根节点的⼆叉树是否是镜像对称的
int left1=0,right1=0;
int left2=0,right2=0;
BiTree root1,root2;
pQueue que;
que=InitQueue();//初始化队列
que->back=EnQueue(que,root);
root=DeQueue(que);
if(root->lchild!=NULL)//左⼉⼦不空则标记
{
left1=1;
}
if(root->rchild!=NULL)//右⼉⼦不空则标记
{
right1=1;
}
if(left1!=0&&right1!=0)//判断该结点左右是否相等都有⼉⼦
{
left1=0;//清空
right1=0;//清空
que->back=EnQueue(que,root->lchild);
que->back=EnQueue(que,root->rchild);
while(isEmpty(que))//使⽤两个对称结点，判断是否对称，当队列为空时，退出循环{
root1=DeQueue(que);
root2=DeQueue(que);
if(root1->lchild!=NULL)
{
left1=1;
}
if(root2->rchild!=NULL)
{
right2=1;
}
if((left1==1)&&(right2==1))
{
que->back=EnQueue(que,root1->lchild);
que->back=EnQueue(que,root2->rchild);
}
if(left1!=right2)
{
return0;
}
if(root1->rchild!=NULL)
{
right1=1;
}
if(root2->lchild!=NULL)
{
left2=1;
}
if((right1==1)&&(left2==1))//两个结点是否镜像对称
{
que->back=EnQueue(que,root1->rchild);
que->back=EnQueue(que,root2->lchild);
}
if(right1!=left2)
{
return0;
}
挣多音字组词语left1=0;
left2=0;
right1=0;
right2=0;
}
}
if(isEmpty(que)==0)//队列为空，返回1
{
return1;
}
}
el if(right1==0&&left1==0)//只有根结点时
{
return1;
}
el
{
return0;
}
}
⼆叉树的数据对称
由于上⾯已经对⼆叉树的结构进⾏判断，故只需在结构对称的基础下，对⼆叉树的L T R遍历结果等于R T L的遍历结果，即可判断其为数据对称的⼆叉树
int isSymmetricalPlus(BiTree root)//判断⼆叉树的数据和结构是否镜像对称
{
int i;
postOrderTraverPlus1(root);//LRT遍历
postOrderTraverPlus2(root);//RLT遍历
for(i=0;i<strlen(a);i++)//判断遍历结果是否⼀样
{
if(a[i]!=b[i])
break;
}
if(i==strlen(a))//全部相等
{
return1;
}
el
{
return0;
}
}
整个程序的源代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<asrt.h>
char a[100];//⽤于存放按L R T遍历的数据
int i0=0;
char b[100];//⽤于存放按R L T遍历的数据
int j0=0;
typedef struct Node
{
char ch;//存放数据
struct Node *lchild,*rchild;
struct Node *next;
} TreeNode,*BiTree;//定义树节点的结构体
typedef struct queue{
/* 队列 */
BiTree front;//队⾸指针
BiTree back;//队尾指针
/
* 可⾃由添加需要⽤的变量 */
