#include
#include
#include
typedef struct Node /* 树结点类型*/
{
int info; /* 数据域*/
struct Node* parent; /* 父结点*/
struct Node* lchild; /* 左孩子结点*/ struct Node* rchild; /* 右孩子结点*/ }PNode;
struct Stack /* 栈结点类型*/
{
int* pre;
int* in;
int n;
PNode parent;
};
PNode *Init_tree(int *pre,int *in,int n);//声明
/* 前序遍历*/
void pre_order(PNode *root)
{
if (root != NULL)
{
printf("%d ",root->info);
pre_order(root->lchild);
pre_order(root->rchild);
}
}
/* 中序遍历*/
void in_order(PNode *root)
{
if (root != NULL)
{
in_order(root->lchild);
printf("%d ",root->info);
in_order(root->rchild);
}
}
/* 后序遍历*/
void post_order(PNode *root)
{
if (root != NULL)
{
post_order(root->lchild);
post_order(root->rchild);
printf("%d ",root->info);
}
}
int main(void)
{
PNode *root;
int pre[50]={1,2,4,8,10,5,9,3,6,7};
int in[ 50]={8,10,4,2,5,9,1,6,3,7} ;
/* 建树*/
root = Init_tree(pre,in,10);
printf("\n前序遍历结果：\n");
pre_order(root);
printf("\n中序遍历结果：\n");
in_order(root);
printf("\n后序遍历结果：\n");
post_order(root);
printf("\n");
return 0;
}
PNode *Init_tree(int *pre,int *in,int n) {
PNode *root;
int *p,*q,i,j,m;
if(n<=0)
return (NULL);
root=(PNode*)malloc(sizeof(PNode));
root->info=pre[0];
root->lchild=root->rchild=NULL;
i=0;
while(i { if(pre[0]==in[i]) break; ++i; } p=pre+1; q=in; root->lchild=Init_tree(p,q,i); p=pre+i+1; q=in+i+1; root->rchild=Init_tree(p,q,n-i-1); return(root); } 树的形状 1 / \ 2 3 / \ / \ 4 5 6 7 / \ 8 9 \ 10 这种题一般有二种形式，共同点是都已知中序序列。如果没有中序序列，是无法唯一确定一棵树的，证明略。 一、已知二叉树的前序序列和中序序列，求解树。 1、确定树的根节点。树根是当前树中所有元素在前序遍历中最先出现的元素。 2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。 3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。 二、已知二叉树的后序序列和中序序列，求解树。 1、确定树的根。树根是当前树中所有元素在后序遍历中最后出现的元素。 2、求解树的子树。找出根节点在中序遍历中的位置，根左边的所有元素就是左子树，根右边的所有元素就是右子树。若根节点左边或右边为空，则该方向子树为空；若根节点左边和右边都为空，则根节点已经为叶子节点。 3、递归求解树。将左子树和右子树分别看成一棵二叉树，重复1、2、3步，直到所有的节点完成定位。 举例说明：根据已知求解二叉树 中序序列HLDBEKAFCG 后序序列LHDKEBFGCA 1、在后序序列LHDKEBFGCA中最后出现的元素为A，HLDBEK|A|FCG 2、在后序序列LHDKEB中最后出现的元素为B，HLD|B|EK|A|FCG 3、在后序序列LHD中最后出现的元素为D，HL|D|B|EK|A|FCG 4、在后序序列LH中最后出现的元素为H，H|L|D|B|EK|A|FCG 5、在后序序列KE中最后出现的元素为E，H|L|D|B|E|K|A|FCG 5、在后序序列FGC中最后出现的元素为C，H|L|D|B|E|K|A|F|C|G 6、所有元素都已经定位，二叉树求解完成。 A / \ B C / \ / \ D E F G / \ H K \ L 代码的运行结果 数学与计算机学院计算机系实验报告 课程名称： 数据结构 年级：2010 实验成绩： 指导教师： 黄襄念 姓名： 实验教室：6A-413 实验名称：二叉树前序或中序或后序遍历 学号： 实验日期：2012/6/10 实验序号：实验3 实验时间：8:00—11:40 实验学时：4 一、实验目的 1. 熟悉的掌握树的创建，和树的前序、中序、后序遍历。 二、实验环境 1. 操作系统：Windows7 2. 开发软件：Microsoft Visual C++ 6.0 三、实验内容 ● 程序功能 本程序完成了以下功能： 1. 前序遍历 2. 中序遍历 3. 后序遍历 ● 数据结构 本程序中使用的数据结构（若有多个，逐个说明）： 1. 它的优缺点 1） 可以快速的查找数据。 2） 让数据层次更加清晰。 2. 逻辑结构图 3. 存储结构图 、、、、、、、、、、、、、、、、、、、、 4.存储结构的C/C++ 语言描述 typedef struct node { DataType data; struct node *lchild; struct node *rchild; } BiTNode, *BiTree; typedef BiTree type; ●算法描述 本程序中采用的算法 1.算法名称：递归 2.算法原理或思想 是通过访问结点的左右孩子来进行循环查找的方法，拿中序遍历来说明：先从头结点开始，再去访问头结点的右孩子如果为空就访问头结点的左孩子，依次进行访问当结点的左右孩子都为空时，就访问上一级，到了最后。 3.算法特点 它能将查找进行2分，体现出了更高效快捷的特点，并且层次很清晰。 ●程序说明 1. 2. 1）前序遍历模块：将树进行从头结点开始再左孩子再右孩子。 代码：void InOrder(BiTree root) { Stack S(100); initStack(S); BiTNode *p = root; do { while(p != NULL) { Push(S, p); /*一下总结一些二叉树的常见操作：包括建立二叉树先/中/后序遍历二叉树求二叉树的叶子节点个数 求二叉树的单分支节点个数计算二叉树双分支节点个数计算二叉树的高度计算二叉树的所有叶子节点数*/ #include /*void preorder(Bitree T) //先序遍历 { if(T) { printf("%c-",T->data); preorder(T->lchild); preorder(T->rchild); } } */ /*下面先序遍历二叉树非递归算法设计*/ void preorder(Bitree T) //先序遍历非递归算法设计{ Bitree st[Maxsize];//定义循环队列存放节点的指针Bitree p; int top=-1; //栈置空 if(T) { top++; st[top]=T; //根节点进栈 while(top>-1) //栈不空时循环 { p=st[top]; //栈顶指针出栈 top--; printf("%c-",p->data ); if(p->rchild !=NULL) //右孩子存在进栈 { top++; st[top]=p->rchild ; } if(p->lchild !=NULL) //左孩子存在进栈 { top++; st[top]=p->lchild ; } } printf("\n"); } } C语言实现二叉树的前序遍历算法实现一： #include #include #include 实践三：树的应用 1.实验目的要求 通过本实验使学生深刻理解二叉树的性质和存储结构，熟练掌握二叉树的遍历算法。认识哈夫曼树、哈夫曼编码的作用和意义。 实验要求：建一个二叉树并按照前序、中序、后序三种方法遍历此二叉树，正确调试本程序。 能够建立一个哈夫曼树，并输出哈夫曼编码，正确调程序。写出实验报告。 2.实验主要内容 2.1 对二叉树进行先序、中序、后序递归遍历，中序非递归遍历。 2.2 根据已知的字符及其权值，建立哈夫曼树，并输出哈夫曼编码。 3．实验步骤 2.1实验步骤 ●输入p127二叉链表的定义 ●录入调试p131算法6.4，实现二叉树的构造函数 ●编写二叉树打印函数，可以通过递归算法将二叉树输出为广义表的 形式，以方便观察树的结构。 ●参考算法6.1，实现二叉树的前序、中序和后序的递归遍历算法。 为简化编程，可以将visit函数直接使用printf函数输出结点内容来 代替。 #include typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; // 构造栈的结构体 typedef BiTree SElemType; typedef struct{ SElemType *base; SElemType *top; int stacksize; }SqStack; Status InitStack(SqStack &S){ //构造一个空栈 S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType)); if(!S.base)exit(-2); S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; } Status StackEmpty(SqStack S){ //若栈S为空栈，则返回TRUE,否则返回FALSE if(S.top==S.base) return 1; else return 0; } #include 二叉树前序、中序、后序遍历相互求法今天来总结下二叉树前序、中序、后序遍历相互求法，即如果知道两个的遍历，如何求第三种遍历方法，比较笨的方法是画出来二叉树，然后根据各种遍历不同的特性来求，也可以编程求出，下面我们分别说明。 首先，我们看看前序、中序、后序遍历的特性： 前序遍历： 1.访问根节点 2.前序遍历左子树 3.前序遍历右子树 中序遍历： 1.中序遍历左子树 2.访问根节点 3.中序遍历右子树 后序遍历： 1.后序遍历左子树 2.后序遍历右子树 3.访问根节点 一、已知前序、中序遍历，求后序遍历 例： 前序遍历: GDAFEMHZ 中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。同理，遍历的右子树的第一个节点就是右子树的根节点。 第五步，观察发现，上面的过程是递归的。先找到当前树的根节点，然后划分为左子树，右子树，然后进入左子树重复上面的过程，然后进入右子树重复上面的过程。最后就可以还原一棵树了。该步递归的过程可以简洁表达如下： 1 确定根,确定左子树，确定右子树。 2 在左子树中递归。 实验目的 编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。 实验内容 编程序并上机调试运行。 编写一个程序，实现二叉树的先序遍历，中序遍历，后序遍历。编写程序 /***********二叉树的遍历**************/ #include } /*************************************************/ //先序遍历--递归算法 void PreOrderTraverse(BiTree T) { if(T) { printf("%c",T->data); PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); } } /*************************************************/ //中序遍历--递归算法 void InOrderTraverse(BiTree T) { if(T) { InOrderTraverse(T->lchild); printf("%c",T->data); InOrderTraverse(T->rchild); } } /*************************************************/ //后序遍历--递归算法 void PostOrderTraverse(BiTree T) { if(T) { PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); printf("%c",T->data); } } /*************************************************/ //main函数 void main() { 一、知道二叉树的先序/后序遍历和中序遍历（中序必须要知道，不然无法判断），要快速判断后序/先序遍历，首先要了解二叉树的遍历规律 二、二叉树遍历规律 1、三种遍历都有一个规律，就是：逆时针沿着二叉树外缘移动，即方向相同，如下图1： 图1 2、 3、不同的是他们出发点不同，下面说明他们的出发点和遍历顺序序列 三、二叉树三种遍历 1、先序遍历 先序遍历先从二叉树的根开始，然后到左子树，再到右子树,，如图2 图2 先序遍历序列是ABDCEF，重点是记住第一个字母“A”是根，出发点是根“A” 2、中序遍历 中序遍历先从左子树开始，然后到根，再到右子树，如图3 图3 即中序遍历序列是DBAECF，重点是记住中序遍历的根位置，是在序列的第一个字母和最后一个字母之间，出发点是左子树的最下边的左边的开始，（为什么到A之后直接跳过C呢？因为C也是E和F的根，所以按照中序遍历规律，先到 E再到C再到F） 3、后序遍历 后序遍历先从左子树开始，然后到右子树，再到根，如图4 图4 即后序遍历序列式DBECFA,重点是知道了根是最后面一个字母“A”，出发点是左子树的最下边左边，。 四、道了先序遍历和中序遍历，或者是后序遍历和中序遍历，判断出后序遍历，或者是先序遍历的方法 比如知道先序遍历是ABDCEF，中序遍历是DBAECF，那么可以从先序遍历知道这个二叉树的根是A，（如果是选择题，可以快速判断出后序遍历的序列最后面一个字母肯定是A，然后选择最后面有A的选项） 从中序遍历看出A把DB和ECF隔开，即DB \A \ECF，因此可以知道DB属于左子树，ECF属于右子树 如果是填空题就要写出该二叉树的图，先写出左子树，从中序遍历知道DB是右子树，把DB看成一个整体，则从先序遍历判断可以确定B是D的根，这样就确定出左子树的图是 把ECF右子树看成一个整体，则从先序遍历可以知道C是E和F的根，确定出右子树是 然后把两个子树连在根“A”的下面，再根据后序遍历规律读出序列就可以了 后面省略。。。。。。。。。。。 这是我参考网上的一些资料总结出来的，只要你理解了三个遍历的规律就很容易做出判断了，我觉得考试的重点是C 语言方面的，比如条件语句，分支结构，循环结构，逻辑判断，数组等，，，，，，，，我当时主要是靠c语言那块得分的，数据结构我也不是很懂，你可以从简单的开始，记一些基本的，祝你考试成功 https://www.doczj.com/doc/8d3560083.html,/link?url=b8c_4x48kZCaZsaz7UBkf6IuV27eXjYClCx1VpY_o06icCzcVRjmN_Rd9HtsPzs9 二叉树的前序遍历、中序遍历、后续遍历 （非递归法） 1、前序遍历（非递归）： #include else return; } } void main()//主函数 { struct BiTNode *p,*t; later(p); print(p); } 2、中序遍历（非递归） #include 二叉树的前、中、后序遍历 c程序如下： # include ; # include ; struct BTNode { char data; struct BTNode * pLchild; struct BTNode * pRchild; }; struct BTNode * creat_BTree(void); void pro_traverse(struct BTNode * pT); void mid_traverse(struct BTNode * pT); void rear_traverse(struct BTNode * pT); int main(void) { struct BTNode * pT = creat_BTree(); printf("二叉树前序遍历结果如下：\n"); pro_traverse(pT); printf("\n"); printf("二叉树中序遍历结果如下：\n"); mid_traverse(pT); printf("\n"); printf("二叉树后序遍历结果如下：\n"); rear_traverse(pT); printf("\n"); return 0; } void pro_traverse(struct BTNode * pT) { if(pT != NULL) { printf("%c ",pT->;data); if(NULL != pT->;pLchild) pro_traverse(pT->;pLchild); if(NULL != pT->;pRchild) pro_traverse(pT->;pRchild); } } void mid_traverse(struct BTNode * pT) { if(pT != NULL) { .先序遍历非递归算法 void PreOrderUnrec(Bitree *t) { Stack s; StackInit(s); Bitree *p=t; while (p!=NULL || !StackEmpty(s)) { while (p!=NULL) //遍历左子树 { visite(p->data); push(s,p); p=p->lchild; } if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历{ p=pop(s); p=p->rchild; }//endif }//endwhile } 2.中序遍历非递归算法 void InOrderUnrec(Bitree *t) { Stack s; StackInit(s); Bitree *p=t; while (p!=NULL || !StackEmpty(s)) { while (p!=NULL) //遍历左子树 { push(s,p); p=p->lchild; } if (!StackEmpty(s)) { p=pop(s); visite(p->data); //访问根结点 p=p->rchild; //通过下一次循环实现右子树遍历 }//endif }//endwhile } 3.后序遍历非递归算法 typedef enum{L,R} tagtype; typedef struct { Bitree ptr; tagtype tag; }stacknode; typedef struct { stacknode Elem[maxsize]; int top; }SqStack; void PostOrderUnrec(Bitree t) { SqStack s; stacknode x; StackInit(s); p=t; do { while (p!=null) //遍历左子树 { x.ptr = p; x.tag = L; //标记为左子树 push(s,x); p=p->lchild; } while (!StackEmpty(s) && s.Elem[s.top].tag==R) { x = pop(s); p = x.ptr; visite(p->data); //tag为R，表示右子树访问完毕，故访问根结点}二叉树前序或中序或后序遍历
二叉树的建立与先序中序后序遍历 求叶子节点个数 求分支节点个数 求二叉树的高度
C语言实现二叉树的前序遍历(递归)
C++二叉树的前序,中序,后序,层序遍历的递归算法55555
二叉树的遍历(先序、中序、后序)
遍历二叉树老师的程序(绝对正确,实现先序、中序、后序遍历)
二叉树前序、中序、后序遍历相互求法
二叉树的遍历(先序遍历、中序遍历、后序遍历全)实验报告
快速判断二叉树先序遍历 后序遍历
C语言实现二叉树的前序、中序、后续遍历(非递归法)
二叉树的前、中、后序遍历
二叉树先序、中序、后序遍历非递归算法
相关主题
文本预览