/*编写算法函数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);}elsereturn 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 100extern 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;}
