下面这个程序是我看weiss的《数据结构与算法分析》的第四章的树里面的一个算法写的程序,具体可以看该书的第一版的71页这个给出我的实现,希望来者给出更加好的设计思路。
程序里面给出了8种遍历方式,欧拉遍历(其实就是中序加了两个括号而已),前序非递归,中序非递归,后序非递归,前序递归,中序递归,后序递归,
另外程序也添加了按层遍历二叉树,程序如下:
-
#include<ctype.h>
-
#include<malloc.h>
-
#include<stdio.h>
-
#include<queue>
-
usingnamespacestd;
-
typedefstructTreenode*ptrtonode;
- typedefptrtonodeTree;
-
structTreenode{
-
charx;
- Treelefttree;
- Treerighttree;
- }Treenode;
-
typedefstructList_Stack{
-
structList_Stack*next;
- Treemytree;
- }Node,*LS;
-
voidinitstack(LS*a){
-
(*a)=(LS)malloc(sizeof(Node));
- (*a)->next=NULL;
- }
-
boolstackempty(constLSa){
-
returna->next==NULL;
- }
-
-
-
voidpush(LS*lstack,Treea){
-
LSres=(LS)malloc(sizeof(Node));
- res->mytree=a;
- res->next=(*lstack)->next;
- (*lstack)->next=res;
- }
- Treepop(LS*lstack){
-
if(stackempty(*lstack)){
-
printf("Poperror,stackisempty!\n");
-
returnNULL;
- }
- LSp=(*lstack)->next;
- Treex=p->mytree;
- LSpnext=p->next;
-
- (*lstack)->next=pnext;
-
returnx;
- }
-
boolisoperator(chara){
-
if(a=='-'||a=='+'||a=='*'||a=='/')
-
return1;
-
else
-
return0;
- }
-
Treechartotree(chara){
-
Treemytree=(Tree)malloc(sizeof(Treenode));
- mytree->x=a;
- mytree->lefttree=mytree->righttree=NULL;
-
returnmytree;
- }
-
boolexnode(Treex){
-
if((x->righttree==NULL)&&(x->lefttree==NULL)){
-
return1;
- }
-
else
-
return0;
- }
-
boolinnode(Treex){
-
return!exnode(x);
- }
-
-
voideulervisit(Treex){
-
if(exnode(x)){
-
printf("%c",x->x);
- }
-
else{
-
printf("(");
- eulervisit(x->lefttree);
-
printf("%c",x->x);
- eulervisit(x->righttree);
-
printf(")");
- }
- }
-
-
boolmidvisit(Treex){
-
if(x){
-
if(midvisit(x->lefttree))
-
if(printf("%c",x->x))
-
if(midvisit(x->righttree))
-
return1;
-
return0;
- }
-
else
-
return1;
- }
-
-
boolprevisit(Treex){
-
if(x){
-
if(printf("%c",x->x))
-
if(previsit(x->lefttree))
-
if(previsit(x->righttree))
-
return1;
-
return0;
- }
-
else
-
return1;
- }
-
-
voidpostvisit(Treex){
-
if(x){
- postvisit(x->lefttree);
- postvisit(x->righttree);
-
printf("%c",x->x);
- }
- }
-
-
voidpreordervisit(Treex){
- LSa;
- initstack(&a);
- Treep=x;
-
while(p||!stackempty(a))
- {
-
if(p)
- {
- push(&a,p);
-
printf("%c",p->x);
- p=p->lefttree;
- }
-
else{
- p=pop(&a);
- p=p->righttree;
- }
- }
- }
-
-
voidinordervisit(Treex){
- LSa;
- initstack(&a);
- Treep=x;
-
while(p||!stackempty(a))
- {
-
if(p)
- {
- push(&a,p);
- p=p->lefttree;
- }
-
else{
- p=pop(&a);
-
printf("%c",p->x);
- p=p->righttree;
- }
- }
- }
-
-
-
-
voidpostordervisit(Treex){
- Treestack[100],p;
-
inttag[100],top;
- top=0;
- p=x;
-
do
- {
-
while(p!=NULL)
- {
- top++;
- stack[top]=p;
-
tag[top]=0;
- p=p->lefttree;
- }
-
if(top>0)
- {
-
if(tag[top]==1)
- {
-
printf("%c",stack[top]->x);
- top--;
- }
-
else{
- p=stack[top];
-
if(top>0)
- {
- p=p->righttree;
- tag[top]=1;
- }
- }
- }
-
}while((p!=NULL)||(top!=0));
- }
-
Treecreatetree(char*a){
- LSx;
- initstack(&x);
-
char*p=a;
-
while(*p!='\0'){
- Treea,b;
- Treemytree;
-
if(isalpha(*p)){
- mytree=chartotree(*p);
- push(&x,mytree);
- }
-
if(isoperator(*p)){
- mytree=chartotree(*p);
- a=pop(&x);
- b=pop(&x);
- mytree->righttree=a;
- mytree->lefttree=b;
- push(&x,mytree);
- }
- p++;
- }
- Treeroot=pop(&x);
-
returnroot;
- }
-
voiddeletenode(Tree*p){
- queue<Tree>que;
- que.push(*p);
- Treetemp;
-
while(!que.empty()){
- temp=que.front();
- que.pop();
-
if(temp->lefttree)
- que.push(temp->lefttree);
-
if(temp->righttree)
- que.push(temp->righttree);
-
-
printf("%c",temp->x);
- temp=NULL;
- }
- }
-
intmain(intargc,char*argv[])
- {
- LSx;
- initstack(&x);
-
if(stackempty(x))
-
printf("stackisempty!\n");
-
else
-
printf("stackisfull!\n");
-
printf("%c\n",pop(&x));
-
char*p="abc*+b-";
- Treeroot=createtree(p);
-
-
- eulervisit(root);
-
puts("\n中序递归");
- midvisit(root);
-
puts("\n中序非递归");
- inordervisit(root);
-
puts("\n前序递归");
- previsit(root);
-
puts("\n前序非递归");
- preordervisit(root);
-
puts("\n后序递归");
- postvisit(root);
-
puts("\n后序非递归");
- postordervisit(root);
- deletenode(&root);
-
return0;
- }
分享到:
相关推荐
(1) ReadExpre(E)- _以字符序列的形式输入语法正确的前缀表达式并构造表达式E。(2) WriteExpre(E)- 用带括弧的中缀表达式输出表达式E。 (3) Assign(V,c)-实现对变量 V的赋值(V=c), 变量的初值为0。 (4) Value(E)-对...
1、设计一个程序,根据二叉树的先根序列和中根序列创建一棵用左右指针表示的二叉树 例如:先根序列为 ABDGCEF#, 中根序列为 DGBAECF# (#表示结束)。然后用程序构造一棵二叉树。注意程序的通用性(也就是说上述只是...
1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目/叶结点数目;(选做) 4. 将二叉树每个结点的左右子树...
对于任意给出的前缀或中缀或后缀表达式,构造一棵表达式二叉树并表示出来,对于构造好的二叉树,输出相应的前中后缀表达式。
(5) CompoundExpr (P, E1,E2) -_构造-一个新的复合表达式(E1) P (E2) [测试数据] (1)分别输入 0; a; -91; +a*bc; +*5^x2*8x; +++*3^x3*2^x2x6 并输出。 (2)每当输入一个表达式后,对其中的变量赋值,然后对表达式...
1. ReadExpr(E)——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2. WriteExpr(E)——用带括号的中缀表示式输出表达式E。 3. Assign(V,c)——实现对变量V的赋值(V=c),变量的初值为0。 4. Value...
(1)ReadExpr(E)――以字符序列的形式输入语法正确的前缀表达式并构造表达式E。 (2)WriteExpr(E)――用带括号的中缀表达式输出表达式E。 (3)Assign(V,c)――实现对变量V的赋值(V=c),变量的初值为0。 ...
1. ReadExpr(E)——以字符序列的形式输入语法正确的前缀表示式并构造表达式E。 2. WriteExpr(E)——用带括号的中缀表示式输出表达式E。 3. Assign(V,c)——实现对变量V的赋值(V=c),变量的初值为0。 4. Value...
已知前序中序 构造二叉树,并求后序遍历 判断是否为平衡二叉树
数据结构课设,用c语言编写的单链表, 表达式求值, 二叉树 ,二叉排序树 ,Huffman编码,五个做成菜单,只有一个main函数
c#实现的二叉树构造,遍历,二叉树后缀表达式求值等算法。可以用于数据结构教学
根据括号表达式构造二叉树,对二叉树进行前序,中序,后序,层序遍历,并用树形方式打印输出,有详细注释,供C++数据结构课程学习与交流使用。
构造表达式二叉树,实现二叉树的递归与非递归的先序、中序、后序遍历,求二叉树的宽度、深度、结点的父子结点等。
1 实验一 线性链表及应用 1 1.1 实验目的 1 1.2 实验要求 1 1.3 实验内容 1 1.3.1 线性链表ADT定义及其实现 1 1.3.2 线性链表ADT测试程序 3 1.3.3 线性链表的应用 4 1.4 线性链表实现与测试总结 5 2 实验二 栈及应用...
1.输入一个中缀表达式,构造表达式树,以文本方式输出树结构。 输入:例如,输入a+b+c*(d+e) 输出:以缩进表示二叉树的层次,左(根),右(叶),上(右子树),下(左子树) 2.编写二叉树类的成员函数,分别实现...
这是严蔚敏《数据结构》配套习题册上的题目:将逆波兰式转换成波兰式,并提示错误(作为简化,只处理"+-*/"和0~9的数字)。... 算法是根据后根遍历的序列构造一个表达式树,进而先根遍历此树获得波兰式表达式。
有关二叉树计数问题的探讨论文,二叉树计数问题是指由n 个节点所构造出的不 同二叉树的数目。这种计数方法与n+ 1 个矩阵连乘 和栈排列n 个数得到的结论是一致的。本文由易到 难叙述问题同解的必然性和可能性, 并给出...
1、 实验目的:采用算符优先分析法对表达式进行分析,掌握算符优先分析法的基本原理和实现过程。 2、 实验要求: 文法:无二义性的算术表达式的文法 ...(6)生成一棵语法树(5分)用二叉树的形式表示出来
2019/11/20 21:49 2,021 二叉树.cpp 2019/09/22 22:58 1,305 复数.cpp 2019/09/25 11:20 1,750 带头结点链表.cpp 2019/11/11 19:51 11,164 广义表.cpp 2019/11/11 20:30 1,917 数组.cpp 2019/09/28 16:28 1,879...
2、(必做题)对于一棵二叉树,请实现: (1)计算二叉树的叶子数目; (2)计算二叉树的深度。 3、(选做题)给定n个权值,请构造它们的最优二叉树(赫夫曼树)。 期末大实验: 一、任意长十进制整数加法 二、...