/*
编写算法函数void preorder1(bintree t)实现二叉树t的非递归前序遍历。
*/
#include "bintree.h"
char *a="ABC##D#E##F##"; /*扩充二叉树序树t的前序序列*/
/*函数preorder1()的功能是非递归前序遍历二叉树t，请将函数补充完整并调试运行*/
void preorder1(bintree t)
{
seqstack s;//顺序栈s
s.top=0;
while((t) || (s.top!=0)) //当前处理的子树不为空或栈不为空则循环
{
if(t)
{
printf("%c ",t->data);
push(&s,t);
t=t->lchild;
}
else
{
t=pop(&s);
t=t->rchild;
}
}
}
int main()
{ bintree t;
t=creatbintree(); /*建立二叉树t的存储结构*/
printf("二叉树的前序序列为：\n");
preorder1(t); /*前序非递归遍历二叉树*/
return 0;
}
/*
编写算法函数void levelbintree(bintree t)，实现二叉树的层次遍历。
*/
#include "bintree.h"
char *a="ABC##D#E##F##"; /*扩充二叉树序树t的前序序列*/
void levelbintree(bintree t)
{
bintree queue[100];
int f=0,r=1;
bintree p;
queue[0]=t;
while(f<r)
{
p=queue[f]; f++; printf("%c",p->data);
if(p->lchild)
queue[r++]=p->lchild;
if(p->rchild)
queue[r++]=p->rchild;
}
}
int main()
{ bintree t;
t=creatbintree(); /*建立二叉树t的存储结构*/
printf("二叉树的层次序列为：\n");
levelbintree(t); /*层次遍历二叉树*/
return 0;
}
/*
编写函数bintree prelist(bintree t)，bintree postfirst(bintree t)，
分别返回二叉树t在前序遍历下的最后一个结点地址和后序遍历下的第一个结点地址。
*/
#include "bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
bintree prelast(bintree t)
{ //右下叶子结点
bintree p;
if(t)
{
p=t;
while(p&&p->lchild||p->rchild)
{
if(p->rchild)
{
p=p->rchild;
}
else
{
p=p->lchild;
}
}
}
return p; //返回前序序列最后一个结点G
}
bintree postfirst(bintree t)
{ //后序遍历是左子树-右子树-根结点 ,二叉树的左下叶子结点是第一个
bintree p;
if(t)
{
while(p&&p->lchild||p->rchild)
{
if(p->lchild)
{
p=p->lchild;
}
else
{
p=p->rchild;
}
}
}
return p;//返回后序序列第一个结点 C
}
int main()
{ bintree t,p,q;
t=creatbintree(); /*建立二叉树t的存储结构*/
p=prelast(t);
//q=postfirst(t);
if (t!=NULL)
{ printf("前序遍历最后一个结点为：%c\n",p->data);
// printf("后序遍历第一个结点为：%c\n",q->data);
}
else printf("二叉树为空！");
return 0;
}
/*
假设二叉树采用链式方式存储，t为其根结点，编写一个函数int Depth(bintree t, char x)，求值为x的结点在二叉树中的层次。
*/
#include "bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
/*
函数Depth，功能：求结点x所在的层次
*/
int Depth(bintree t,char x)
{
int num1,num2,n;//num1,num2分别记录在左子树，右子树中查找到x的层数,n记录最终返回的结果层数
if(t==NULL)
{
return 0;
}
else
{
if(t->data==x)
{
return 1;
}
num1=Depth(t->lchild,x);
num2=Depth(t->rchild,x);
n=num1+num2; //num1和num2之中必有一个为0
if(num1!=0||num2!=0) //找到了x ，往回数
{
n++;
}
}
return n;
}
int main()
{ bintree root;
char x;
int k=0;
root=creatbintree();
printf("请输入树中的1个结点值：\n");
scanf("%c",&x);
k=Depth(root,x);
printf("%c结点的层次为%d\n",x,k);
}
/*
试编写一个函数，将一棵给定二叉树中所有结点的左、右子女互换。
*/
#include "bintree.h"
char *a="ABC##D##EF#G###"; /*扩充二叉树序树t的前序序列*/
/*请将本函数补充完整，并进行测试*/
void change(bintree t)
{
bintree p;
if(t)
{
p=t->lchild; //交换
t->lchild=t->rchild;
t->rchild=p;
change(t->lchild); //继续递归
change(t->rchild);
}
}
int main()
{ bintree root;
root=creatbintree();
change(root);
preorder(root);
}
/*
试编写一个递归函数bintree buildBintree(char *pre, char *mid, int length)，
根据二叉树的前序序列pre、中序序列mid和前序序列长度length，构造二叉树的二叉链表存储结构，
函数返回二叉树的树根地址。
*/
#include "bintree.h"
#include <string.h>
char *a="";
/*请将本函数补充完整，并进行测试*/
bintree buildBintree(char *pre, char *mid,int length)
{
bintree t;
int i=0;
if(length)
{
t=(bintree)malloc(sizeof(binnode)); //生成新结点
t->data=pre[i];
while(i<length&&mid[i]!=pre[0]) //在中序遍历中查找根结点的位置
i++;
t->lchild=buildBintree(pre+1,mid,i);
t->rchild=buildBintree(pre+i+1,mid+i+1,length-i-1);
}
else
return NULL;
return t;
}
int main()
{ bintree root;
char pre[100],mid[100];
puts("请输入前序序列：");
gets(pre);
puts("请输入中序序列：");
gets(mid);
root=buildBintree(pre,mid,strlen(pre));
puts("后序序列是：");
postorder(root);
}
/*bintree.h头文件*/
#include<stdio.h>
#include<stdlib.h>
#define N 100
extern char *a;
typedef struct node
{
char data;
struct node *lchild, *rchild;
}binnode;
typedef binnode *bintree;
/*函数creatbintree(根据扩充二叉树的前序序列(字符a)建立二叉树t的存储结构)*/
binnode creatbintree()
{
char ch = *a++;
bintree t;
if (ch == '#') t = NULL;
else
{
t = (bintree)malloc(sizeof(binnode));
t->data = ch;
t->lchild = creatbintree();
t->rchild = creatbintree();
}
return t;
}
