数组二叉树的遍历(用VB编写 二叉树的建立与遍历、二叉树的排序)
本文目录
- 用VB编写 二叉树的建立与遍历、二叉树的排序
- 一颗具有N个结点的完全二叉树以一维数组作为存储结构,试设计一个对该完全二叉树进行线序遍历的算法
- 完全二叉树 顺序储存 实现对其的先序遍历
- 一棵具有n个结点的完全二叉树以数组存储,试写一个非递归算法实现对该树的前序遍历
- 递归算法如何把二叉排序树遍历序列放入数组里面
- 在二叉树中有两个结点m和n,如果m是n的祖先,可以找到从m到n的路径的遍历方式是
- C语言的二叉树中序遍历问题
用VB编写 二叉树的建立与遍历、二叉树的排序
实验四 二叉树的建立和遍历一、实验名称 二叉树的建立和遍历。二、实验目的掌握二叉树的二叉链表存储结构及二叉树的建立方法。熟悉二叉树的遍历方法。三、实验内容(1)根据先序遍历和中序遍历的序列,建立一棵二叉树(二叉树用二叉链表存储)。(2)分别以先序和中序遍历二叉树,将假设结果与给定的先序和中序遍历序列进行比较,以证明建立二叉树的正确性。(3)给出后序遍历序列。四、实验步骤(1)编写一个过程,将给出的遍历序列读入一个数组;(2)编写一个过程,根据先序和中序遍历的序列建立一棵二叉树;(3)编写一个过程,进行先序遍历,并将结果存入一个数组。(4)编写一个过程,进行中序遍历,并将结果存入一个数组。(5) 编写一个函数,用以证明建立的二叉树的正确性。(6)编写一个过程,进行后序遍历,打印后序遍历结果(前面函数为真时);(7)调试程序:先序遍历序列为:ABDECF;中序遍历序列为:DBEACF;(8)将实验心得写在程序后面,作为实验报告进行文档备份。五、实验数据处理将原程序和实验结果存入计算机室服务器或软盘后,交由指导老师或有关实验人员保存。实验五 二叉树的排序一、实验名称 二叉树的排序。二、实验目的通过该实验,进一步熟悉二叉树的建立方法,掌握二叉排序树的建立和使用。三、实验内容(1)根据中序遍历,建立一棵二叉排序树用二叉链表存储;(2)给出先序遍历和后序遍历序列。四、实验步骤(1)编写一个过程,将给定的待排序数据读入一个数组;(2)编写一个过程,建立二叉排序树;(3)编写一个函数,用中序遍历以证明二叉排序树的正确性;(4)编写一个过程,进行先序遍历,并打印遍历结果(第3步必须确保正确);(5)编写一个过程,进行后序遍历,并打印遍历结果(第3步必须确保正确);(6)调试程序; 用以下数据调试程序:(58、48、77、42、64) (7)将实验心得写在程序后面,作为实验报告进行文档备份。五、实验数据处理将原程序和实验结果存入计算机室服务器或软盘后,交由指导老师或有关实验人员保存。jiuzheyang ban
一颗具有N个结点的完全二叉树以一维数组作为存储结构,试设计一个对该完全二叉树进行线序遍历的算法
preorder (R) //先序遍历二叉树Rint R;{ int root;SqStack *s; //s为一个指针栈,类型为seqstack,其中包含top域和数组datas-》top= -1; //s栈置空root=1;while ((root《=n) && (s-》top》-1)){ while (root《=n){ printf(R); s-》top++; s-》data=root; root=2*root;} if (s-》top》-1) //栈非空访问,遍历右子树 { root=s-》data*2+1; s-》top--;}}}
完全二叉树 顺序储存 实现对其的先序遍历
假设完全二叉树的顺序储存序列是10,15,20,25,30,50,定义数组:int BTree={10,15,20,25,30,50};完全二叉树的树形如下: 10 / \ 15 20 / \ / 25 30 50 相应的顺序号(也就是数组的下标)是: / \ / \ / =50根节点10的下标是n=0,其左节点下标是2*n+1=2*0+1=1,左节点就是=15,右节点下标是2*n+2=2*0+2=2,右节点就是=20节点15的下标是n=1,其左节点下标是2*n+1=2*1+1=3,左节点就是=25,右节点下标是2*n+2=2*1+2=4,右节点就是=30节点20的下标是n=2,其左节点下标是2*n+1=2*2+1=5,左节点就是=50,没有右节点.先序遍历就是遍历数组的下标.注:如果将根节点10的下标定为1,也就是=10,那么,其它节点的下标也相应加1. 根节点10的下标是n=1,其左节点下标是2*n=2*1=2,左节点就是=15, 右节点下标是2*n+1=2*1+1=3,右节点就是=20// 测试结果:// 输入完全二叉树的总节点数: 6// 输入6个节点的数值: 10 15 20 25 30 50// 先序遍历序列(递归法): 10 15 25 30 20 50// 先序遍历序列(非递归): 10 15 25 30 20 50#include 《stdio.h》#define MAXSIZE 100void preOrderByStack(int BT,int i,int n) //先序遍历(非递归){ int oneStack; //栈 int top=0; //栈顶,从top=1开始存入数据 int left,right; if(i》=n) { return; } top++; oneStack=i; //根节点的下标入栈 while(top!=0) { i=oneStack; //出栈 top--; printf("%d ",BT); left=i*2+1; right=i*2+2; if(right《n) { top++; oneStack=right; //右节点的下标入栈 } if(left《n) { top++; oneStack=left; //左节点的下标入栈 } }}void preOrder(int BT,int i,int n) //先序遍历(递归法){ if(i《n) { printf("%d ",BT); preOrder(BT,2*i+1,n); //左节点 preOrder(BT,2*i+2,n); //右节点 }}int main(){ int BTree; int n; int i; printf("输入完全二叉树的总节点数: "); scanf("%d",&n); printf("输入%d个节点的数值: ",n); for(i=0;i《n;i++) { scanf("%d",&BTree); } printf("先序遍历序列(递归法): "); preOrder(BTree,0,n); printf("\n"); printf("先序遍历序列(非递归): "); preOrderByStack(BTree,0,n); printf("\n"); return 0;}
一棵具有n个结点的完全二叉树以数组存储,试写一个非递归算法实现对该树的前序遍历
#include "stdafx.h"#include 《stack》#include 《iostream》using namespace std; int _tmain(int argc, _TCHAR* argv){ //构建完全二叉树,层数是三,7个节点 int a = {0,1,2,3,4,5,6}; //前序遍历,先访问左儿子,再访问自己,再访问右儿子 //左儿子的位置是自己游标*2+1,右儿子是自己的游标*2+2 //队列作为缓冲 stack《int》 Temp; Temp.push(0);//根节点 while(!Temp.empty()) { int node = Temp.top(); if(2*node+1 《6)//有左儿子 { Temp.push(2*node+1); } else { cout《《a《《endl; Temp.pop(); if(Temp.empty()) { getchar(); return 0; } int parent = Temp.top(); cout《《a《《endl; Temp.pop(); Temp.push(2*parent+2); } } getchar(); return 1;}
递归算法如何把二叉排序树遍历序列放入数组里面
创建二叉排序树,请输入结点的总数量: 7请连续输入7个结点的数据: 2 4 1 3 7 9 5先序遍历序列: 2 1 4 3 7 5 9中序遍历序列: 1 2 3 4 5 7 9后序遍历序列: 1 3 5 9 7 4 2输入要查找的结点的数值(0退出): 9该结点的层次是 4输入要查找的结点的数值(0退出): 7该结点的层次是 3 二叉树示意图: 2 / \ 1 4 / \ 3 7 / \ 5 9 #include "stdio.h"#include "stdlib.h"struct Tree{ int data; struct Tree *left; struct Tree *right;};typedef struct Tree TreeNode;typedef TreeNode *Bitree;//插入结点Bitree insertNode(Bitree root,int data){ Bitree newnode; Bitree current; Bitree back; newnode=(Bitree)malloc(sizeof(TreeNode)); if(newnode==NULL) { printf("\n动态分配内存出错.\n"); exit(1); } newnode-》data=data; newnode-》left=NULL; newnode-》right=NULL; if(root==NULL) { return newnode; } else { current=root; while(current!=NULL) { back=current; if(current-》data 》 data) { current=current-》left; } else { current=current-》right; } } if(back-》data 》 data) { back-》left=newnode; } else { back-》right=newnode; } } return root;}//创建二叉排序树(非递归)Bitree createTree(){ Bitree root=NULL; int len; int data; int i; printf("创建二叉排序树,请输入结点的总数量: "); scanf("%d",&len); printf("请连续输入%d个结点的数据: ",len); for(i=0;i《len;i++) { scanf("%d",&data); root=insertNode(root,data); } return root;}//先序遍历(递归法)void preOrder(Bitree ptr){ if(ptr!=NULL) { printf("%d ",ptr-》data); preOrder(ptr-》left); preOrder(ptr-》right); }}//中序遍历(递归法)void inOrder(Bitree ptr){ if(ptr!=NULL) { inOrder(ptr-》left); printf("%d ",ptr-》data); inOrder(ptr-》right); }}//后序遍历(递归法)void postOrder(Bitree ptr){ if(ptr!=NULL) { postOrder(ptr-》left); postOrder(ptr-》right); printf("%d ",ptr-》data); }}//计算结点的层次(非递归)int findLevel(Bitree root,int data){ Bitree current; int nLevel; if(root==NULL) { return -1; } else { current=root; nLevel=0; while(current!=NULL) { nLevel++; if(current-》data 》 data) { current=current-》left; } else if(current-》data 《 data) { current=current-》right; } else { return nLevel; } } } return 0;} int main(){ Bitree root=NULL; int data; int nLevel; root=createTree(); //创建二叉排序树 printf("先序遍历序列: "); preOrder(root); printf("\n"); printf("中序遍历序列: "); inOrder(root); printf("\n"); printf("后序遍历序列: "); postOrder(root); printf("\n"); while(1) { printf("输入要查找的结点的数值(0退出): "); scanf("%d",&data); if(data==0) { break; } //计算结点的层次(非递归) nLevel=findLevel(root,data); if(nLevel == -1) { printf("二叉树没有数据.\n"); } else if(nLevel == 0) { printf("二叉树没有该数据.\n"); } else { printf("该结点的层次是 %d\n",nLevel); } } printf("\n"); return 0;}
在二叉树中有两个结点m和n,如果m是n的祖先,可以找到从m到n的路径的遍历方式是
四、遍历二叉树二叉树是一种非线性的数据结构,在对它进行操作时,总是需要逐一对每个数据元素实施操作,这样就存在一个操作顺序问题,由此提出了二叉树的遍历操作。所谓遍历二叉树就是按某种顺序访问二叉树中的每个结点一次且仅一次的过程。这里的访问可以是输出、比较、更新、查看元素内容等等各种操作。二叉树的遍历方式分为两大类:一类按根、左子树和右子树三个部分进行访问;另一类按层次访问。下面我们将分别进行讨论。1、按根、左子树和右子树三部分进行遍历遍历二叉树的顺序存在下面6种可能:TLR(根左右),TRL(根右左)LTR(左根右),RTL(右根左)LRT(左右根),RLT(右左根)其中,TRL、RTL和RLT三种顺序在左右子树之间均是先右子树后左子树,这与人们先左后右的习惯不同,因此,往往不予采用。余下的三种顺序TLR、LTR和LRT根据根访问的位置不同分别被称为先序遍历、中序遍历和后序遍历。(1)先序遍历若二叉树为空,则结束遍历操作;否则访问根结点;先序遍历左子树;先序遍历右子树。(2)中序遍历若二叉树为空,则结束遍历操作;否则中序遍历左子树;访问根结点;中序遍历右子树。(3)后序遍历若二叉树为空,则结束遍历操作;否则后序遍历左子树;后序遍历右子树;访问根结点。例如。以下是一棵二叉树及其经过三种遍历所得到的相应遍历序列二叉树的两种遍历方法:(1)对一棵二叉树中序遍历时,若我们将二叉树严格地按左子树的所有结点位于根结点的左侧,右子树的所有结点位于根右侧的形式绘制,就可以对每个结点做一条垂线,映射到下面的水平线上,由此得到的顺序就是该二叉树的中序遍历序列(2)任何一棵二叉树都可以将它的外部轮廓用一条线绘制出来,我们将它称为二叉树的包线,这条包线对于理解二叉树的遍历过程很有用。由此可以看出:(1)遍历操作实际上是将非线性结构线性化的过程,其结果为线性序列,并根据采用的遍历顺序分别称为先序序列、中序序列或后序序列;(2)遍历操作是一个递归的过程,因此,这三种遍历操作的算法可以用递归函数实现。(1)先序遍历递归算法voidPreOrder(BTreeBT){if(BT){Visit(BT);PreOrder(BT-》Lchild);PreOrder(BT-》Rchild);}(2)中序遍历递归算法voidInOrder(BTreeBT){if(BT){InOrder(BT-》Lchild);Visit(BT);InOrder(BT-》Rchild);}}(3)后序遍历递归算法voidPostOrder(BTreeBT){if(BT){PostOrder(BT-》Lchild);PostOrder(BT-》Rchild);Visit(BT);}}2、按层次遍历二叉树实现方法为从上层到下层,每层中从左侧到右侧依次访问每个结点。下面我们将给出一棵二叉树及其按层次顺序访问其中每个结点的遍历序列。voidLevelOreder(QBTreeBT){for(i=1;iLchild){Visite(p-》Lchild);EnQueue(&Q,p-》Lchild);//处理左孩子if(!p-》Rchild){Visite(p-》Rchild);EnQueue(&Q,p-》Rchild);//处理右孩子}}五、典型二叉树的操作算法1、输入一个二叉树的先序序列,构造这棵二叉树为了保证唯一地构造出所希望的二叉树,在键入这棵树的先序序列时,需要在所有空二叉树的位置上填补一个特殊的字符,比如,’#’。在算法中,需要对每个输入的字符进行判断,如果对应的字符是’#’,则在相应的位置上构造一棵空二叉树;否则,创建一个新结点。整个算法结构以先序遍历递归算法为基础,二叉树中结点之间的指针连接是通过指针参数在递归调用返回时完成。算法:BTreePre_Create_BT(){getch(ch);if(ch==’#’)returnNULL;//构造空树else{BT=(BTree)malloc(sizeof(BTLinklist));//构造新结点BT-》data=ch;BT-》lchild=Pre_Create_BT();//构造左子树BT-》rchild=Pre_Create_BT();//构造右子树returnBT;}}2、计算一棵二叉树的叶子结点数目这个操作可以使用三种遍历顺序中的任何一种,只是需要将访问操作变成判断该结点是否为叶子结点,如果是叶子结点将累加器加1即可。下面这个算法是利用中序遍历实现的。算法:voidLeaf(BTreeBT,int*count){if(BT){Leaf(BT-》child,&count);//计算左子树的叶子结点个数if(BT-》lchild==NULL&&BT-》rchild==NULL)(*count)++;Leaf(BT-》rchild,&count);//计算右子树的叶子结点个数}}3、交换二叉树的左右子树许多操作可以利用三种遍历顺序的任何一种,只是某种遍历顺序实现起来更加方便一些。而有些操作则不然,它只能使用其中的一种或两种遍历顺序。将二叉树中所有结点的左右子树进行交换这个操作就属于这类情况。算法:voidchange_left_right(BTreeBT){if(BT){change_left_right(BT-》lchild);change_left_right(BT-》rchild);BT-》lchildBT-》rchild;}}4、求二叉树的高度这个操作使用后序遍历比较符合人们求解二叉树高度的思维方式。首先分别求出左右子树的高度,在此基础上得出该棵树的高度,即左右子树较大的高度值加1。算法:inthight(BTreeBT){//h1和h3分别是以BT为根的左右子树的高度if(BT==NULL)return0;else{h1=hight(BT-》lchild);h3=hight(BT-》right);returnmax{h1,h3}+1;}}六、树、森林与二叉树的转换1、树、森林转换成二叉树将一棵树转换成二叉树的方法:将一棵树转换成二叉树实际上就是将这棵树用孩子兄弟表示法存储即可,此时,树中的每个结点最多有两个指针:一个指针指向第一个孩子,另一个指针指向右侧第一个兄弟。当你将这两个指针看作是二叉树中的左孩子指针和孩子右指针时,就是一棵二叉树了。特点:一棵树转换成二叉树后,根结点没有右孩子。将森林转换成二叉树的方法与一棵树转换成二叉树的方法类似,只是把森林中所有树的根结点看作兄弟关系,并对其中的每棵树依依地进行转换。2、二叉树还原成树或森林这个过程实际上是树、森林转换成二叉树的逆过程,即将该二叉树看作是树或森林的孩子兄弟表示法。比如,若二叉树为空,树也为空;否则,由二叉树的根结点开始,延右指针向下走,直到为空,途经的结点个数是相应森林所含树的棵数;若某个结点的左指针非空,说明这个结点在树中必有孩子,并且从二叉树中该结点左指针所指结点开始,延右指针向下走,直到为空,途经的结点个数就是这个结点的孩子数目。第3节哈夫曼树及其应用1、哈夫曼树的定义及特点在二叉树中,一个结点到另一个结点之间的分支构成这两个结点之间的路径。这三棵二叉树的带权路径长度分别为:WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158哈夫曼树的一个重要特点是:没有度为1的结点。2、构造哈夫曼树的过程:(1)将给定的n个权值{w1,w2,,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,,Tn},其中每棵二叉树只有一个根结点;(2)在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树,新二叉树的根结点权值为这两棵树根的权值之和;(3)在森林中,将上面选择的这两棵根权值最小的二叉树从森林中删除,并将刚刚新构造的二叉树加入到森林中;(4)重复上面(2)和(3),直到森林中只有一棵二叉树为止。这棵二叉树就是哈夫曼树。例如:假设有一组权值{5,29,7,8,14,23,3,11},下面我们将利用这组权值演示构造哈夫曼树的过程。它的带权的路径长度为:WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2713.判定树在很多问题的处理过程中,需要进行大量的条件判断,这些判断结构的设计直接影响着程序的执行效率。例如,编制一个程序,将百分制转换成五个等级输出。大家可能认为这个程序很简单,并且很快就可以用下列形式编写出来:if(socre《60)printf("bad");elseif(socre《70)printf("pass");elseif(score《80)printf("general");elseif(score《90)printf("good");esleprintf("verygood");在实际应用中,往往各个分数段的分布并不是均匀的。下面就是在一次考试中某门课程的各分数段的分布情况:4.前缀编码在电文传输中,需要将电文中出现的每个字符进行二进制编码。在设计编码时需要遵守两个原则:(1)发送方传输的二进制编码,到接收方解码后必须具有唯一性,即解码结果与发送方发送的电文完全一样;(2)发送的二进制编码尽可能地短。下面我们介绍两种编码的方式。(1)等长编码这种编码方式的特点是每个字符的编码长度相同(编码长度就是每个编码所含的二进制位数)。假设字符集只含有4个字符A,B,C,D,用二进制两位表示的编码分别为00,01,10,11。若现在有一段电文为:ABACCDA,则应发送二进制序列:00010010101100,总长度为14位。当接收方接收到这段电文后,将按两位一段进行译码。这种编码的特点是译码简单且具有唯一性,但编码长度并不是最短的。(2)不等长编码在传送电文时,为了使其二进制位数尽可能地少,可以将每个字符的编码设计为不等长的,使用频度较高的字符分配一个相对比较短的编码,使用频度较低的字符分配一个比较长的编码。例如,可以为A,B,C,D四个字符分别分配0,00,1,01,并可将上述电文用二进制序列:000011010发送,其长度只有9个二进制位,但随之带来了一个问题,接收方接到这段电文后无法进行译码,因为无法断定前面4个0是4个A,1个B、2个A,还是2个B,即译码不唯一,因此这种编码方法不可使用。(1)利用字符集中每个字符的使用频率作为权值构造一个哈夫曼树;(2)从根结点开始,为到每个叶子结点路径上的左分支赋予0,右分支赋予1,并从根到叶子方向形成该叶子结点的编码。假设有一个电文字符集中有8个字符,每个字符的使用频率分别为{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11},现以此为例设计哈夫曼编码。哈夫曼编码设计过程为:(1)为方便计算,将所有字符的频度乘以100,使其转换成整型数值集合,得到{5,29,7,8,14,23,3,11};(2)以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树,如图5-27所示;(3)由此哈夫曼树生成哈夫曼编码,如图5-28所示。最后得出每个字符的编码为:比如,发送一段编码:0000011011010010,接收方可以准确地通过译码得到:⑥⑥⑦⑤②⑧。
C语言的二叉树中序遍历问题
#include 《stdio.h》#include 《stdlib.h》#define STACK_MAX_SIZE 30#define QUEUE_MAX_SIZE 30#ifndef elemTypetypedef char elemType;#endif/************************************************************************//* 以下是关于二叉树操作的11个简单算法 *//************************************************************************/struct BTreeNode{elemType data;struct BTreeNode *left;struct BTreeNode *right;};/* 1.初始化二叉树 */void initBTree(struct BTreeNode* *bt){*bt = NULL;return;}/* 2.建立二叉树(根据a所指向的二叉树广义表字符串建立) */void createBTree(struct BTreeNode* *bt, char *a){struct BTreeNode *p;struct BTreeNode *s;/* 定义s数组为存储根结点指针的栈使用 */int top = -1; /* 定义top作为s栈的栈顶指针,初值为-1,表示空栈 */int k; /* 用k作为处理结点的左子树和右子树,k = 1处理左子树,k = 2处理右子树 */int i = 0; /* 用i扫描数组a中存储的二叉树广义表字符串,初值为0 */*bt = NULL; /* 把树根指针置为空,即从空树开始建立二叉树 *//* 每循环一次处理一个字符,直到扫描到字符串结束符\0为止 */while(a != ’\0’){ switch(a){ case ’ ’: break; /* 对空格不作任何处理 */ case ’(’: if(top == STACK_MAX_SIZE - 1){ printf("栈空间太小!\n"); exit(1); } top++; s = p; k = 1; break; case ’)’: if(top == -1){ printf("二叉树广义表字符串错误!\n"); exit(1); } top--; break; case ’,’: k = 2; break; default: p = malloc(sizeof(struct BTreeNode)); p-》data = a; p-》left = p-》right = NULL; if(*bt == NULL){ *bt = p; }else{ if( k == 1){ s-》left = p; }else{ s-》right = p; } } } i++; /* 为扫描下一个字符修改i值 */}return;}/* 3.检查二叉树是否为空,为空则返回1,否则返回0 */int emptyBTree(struct BTreeNode *bt){if(bt == NULL){ return 1;}else{ return 0;}}/* 4.求二叉树深度 */int BTreeDepth(struct BTreeNode *bt){if(bt == NULL){ return 0; /* 对于空树,返回0结束递归 */}else{ int dep1 = BTreeDepth(bt-》left); /* 计算左子树的深度 */ int dep2 = BTreeDepth(bt-》right); /* 计算右子树的深度 */ if(dep1 》 dep2){ return dep1 + 1; }else{ return dep2 + 1; }}}/* 5.从二叉树中查找值为x的结点,若存在则返回元素存储位置,否则返回空值 */elemType *findBTree(struct BTreeNode *bt, elemType x){if(bt == NULL){ return NULL;}else{ if(bt-》data == x){ return &(bt-》data); }else{ /* 分别向左右子树递归查找 */ elemType *p; if(p = findBTree(bt-》left, x)){ return p; } if(p = findBTree(bt-》right, x)){ return p; } return NULL; }}}/* 6.输出二叉树(前序遍历) */void printBTree(struct BTreeNode *bt){/* 树为空时结束递归,否则执行如下操作 */if(bt != NULL){ printf("%c", bt-》data); /* 输出根结点的值 */ if(bt-》left != NULL || bt-》right != NULL){ printf("("); printBTree(bt-》left); if(bt-》right != NULL){ printf(","); } printBTree(bt-》right); printf(")"); } }return;}/* 7.清除二叉树,使之变为一棵空树 */void clearBTree(struct BTreeNode* *bt){if(*bt != NULL){ clearBTree(&((*bt)-》left)); clearBTree(&((*bt)-》right)); free(*bt); *bt = NULL;}return;}/* 8.前序遍历 */void preOrder(struct BTreeNode *bt){if(bt != NULL){ printf("%c ", bt-》data); /* 访问根结点 */ preOrder(bt-》left); /* 前序遍历左子树 */ preOrder(bt-》right); /* 前序遍历右子树 */}return;}/* 9.前序遍历 */void inOrder(struct BTreeNode *bt){if(bt != NULL){ inOrder(bt-》left); /* 中序遍历左子树 */ printf("%c ", bt-》data); /* 访问根结点 */ inOrder(bt-》right); /* 中序遍历右子树 */}return;}/* 10.后序遍历 */void postOrder(struct BTreeNode *bt){if(bt != NULL){ postOrder(bt-》left); /* 后序遍历左子树 */ postOrder(bt-》right); /* 后序遍历右子树 */ printf("%c ", bt-》data); /* 访问根结点 */}return;}/* 11.按层遍历 */void levelOrder(struct BTreeNode *bt){struct BTreeNode *p;struct BTreeNode *q;int front = 0, rear = 0;/* 将树根指针进队 */if(bt != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q = bt;}while(front != rear){ /* 队列非空 */ front = (front + 1) % QUEUE_MAX_SIZE; /* 使队首指针指向队首元素 */ p = q; printf("%c ", p-》data); /* 若结点存在左孩子,则左孩子结点指针进队 */ if(p-》left != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q = p-》left; } /* 若结点存在右孩子,则右孩子结点指针进队 */ if(p-》right != NULL){ rear = (rear + 1) % QUEUE_MAX_SIZE; q = p-》right; }}return;}/************************************************************************//*int main(int argc, char *argv){struct BTreeNode *bt; /* 指向二叉树根结点的指针 */char *b; /* 用于存入二叉树广义表的字符串 */elemType x, *px;initBTree(&bt);printf("输入二叉树广义表的字符串:\n");/* scanf("%s", b); */b = "a(b(c), d(e(f, g), h(, i)))";createBTree(&bt, b);if(bt != NULL)printf(" %c ", bt-》data);printf("以广义表的形式输出:\n");printBTree(bt); /* 以广义表的形式输出二叉树 */printf("\n");printf("前序:"); /* 前序遍历 */preOrder(bt);printf("\n");printf("中序:"); /* 中序遍历 */inOrder(bt);printf("\n");printf("后序:"); /* 后序遍历 */postOrder(bt);printf("\n");printf("按层:"); /* 按层遍历 */levelOrder(bt);printf("\n");/* 从二叉树中查找一个元素结点 */printf("输入一个待查找的字符:\n");scanf(" %c", &x); /* 格式串中的空格跳过空白字符 */px = findBTree(bt, x);if(px){ printf("查找成功:%c\n", *px);}else{ printf("查找失败!\n");}printf("二叉树的深度为:");printf("%d\n", BTreeDepth(bt));clearBTree(&bt);return 0;}
更多文章:
![美国总统大选机制(美国大选的流程和规则)](/static/images/nopic/25.jpg)
美国总统大选机制(美国大选的流程和规则)
2024年3月20日 10:50
![pessimism(pessimism是什么意思)](/static/images/nopic/2.jpg)
pessimism(pessimism是什么意思)
2024年4月21日 15:25
![rule用法(plan与rule的区别(用法上))](/static/images/nopic/19.jpg)
rule用法(plan与rule的区别(用法上))
2024年6月6日 01:09
![inarray方法(2个自定义的PHP in_array 函数,解决大量数据判断in_array的效率问题)](/static/images/nopic/24.jpg)
inarray方法(2个自定义的PHP in_array 函数,解决大量数据判断in_array的效率问题)
2023年11月11日 15:40
![linux系统软件(linux哪个操作系统好)](/static/images/nopic/10.jpg)
linux系统软件(linux哪个操作系统好)
2024年5月27日 14:19
![英语培训机构名称(寓意好的英语培训班名字)](/static/images/nopic/19.jpg)
英语培训机构名称(寓意好的英语培训班名字)
2024年3月12日 12:40
![ignite软件(如何配置hp ignite服务器端)](/static/images/nopic/23.jpg)
ignite软件(如何配置hp ignite服务器端)
2024年6月10日 06:50
![组织机构代码是什么(组织机构代码是指什么)](/static/images/nopic/7.jpg)
组织机构代码是什么(组织机构代码是指什么)
2024年6月6日 00:37
![iis如何配置?在iis中设置ftp的详细步骤越详细越好](/static/images/nopic/7.jpg)
iis如何配置?在iis中设置ftp的详细步骤越详细越好
2024年6月13日 02:48
![数据库中substring的用法(substring在SQL语句中是什么意思)](/static/images/nopic/19.jpg)
数据库中substring的用法(substring在SQL语句中是什么意思)
2024年6月20日 08:31
![潍坊网站定制模板建站(潍坊网站制作公司哪家好哪家最专业)](/static/images/nopic/28.jpg)
潍坊网站定制模板建站(潍坊网站制作公司哪家好哪家最专业)
2024年6月5日 05:38
![血色浪漫宁伟(他是《血色浪漫》宁伟,出道26年,演技扎实就是不红,他是谁)](/static/images/nopic/29.jpg)
血色浪漫宁伟(他是《血色浪漫》宁伟,出道26年,演技扎实就是不红,他是谁)
2023年6月13日 23:40
![microsoft visual c runtime下载(microsoft visual c++ runtime library R6034)](/static/images/nopic/4.jpg)
microsoft visual c runtime下载(microsoft visual c++ runtime library R6034)
2023年6月4日 08:00
![提交更改级别(刚才英语四六级网上报名,填完提交后发现应该报六级的,可是查看已报级别却是四级的,有什么没办法修改吗)](/static/images/nopic/17.jpg)
提交更改级别(刚才英语四六级网上报名,填完提交后发现应该报六级的,可是查看已报级别却是四级的,有什么没办法修改吗)
2024年5月18日 06:13
![sometimes的同义词(sometimes同义词两个词)](/static/images/nopic/23.jpg)
sometimes的同义词(sometimes同义词两个词)
2024年6月19日 02:34
![rubber(美语当中经常用「rubber」来表示避孕套吗)](/static/images/nopic/2.jpg)
rubber(美语当中经常用「rubber」来表示避孕套吗)
2024年5月7日 18:08
![average函数的使用方法和技巧(求平均数公式excel函数)](/static/images/nopic/12.jpg)
average函数的使用方法和技巧(求平均数公式excel函数)
2024年5月16日 21:42
![sqlyog有必要用密钥吗(sql server2012密钥 用哪个)](/static/images/nopic/12.jpg)
sqlyog有必要用密钥吗(sql server2012密钥 用哪个)
2024年4月21日 00:40
![前端开发需要学多久(新手学web前端开发需要多久)](/static/images/nopic/30.jpg)
前端开发需要学多久(新手学web前端开发需要多久)
2024年6月16日 18:29
![mysql怎么导出数据库给别人(mysql数据库怎么导出到另一个数据库中)](/static/images/nopic/18.jpg)
mysql怎么导出数据库给别人(mysql数据库怎么导出到另一个数据库中)
2024年6月12日 04:57