二叉树的遍历
1、递归实现二叉树的建立和递归实现遍历
//算法5.1 中序遍历的递归算法 #include<iostream> using namespace std; typedef struct BiNode{ //二叉链表定义 char data; struct BiNode *lchild,*rchild; }BiTNode,*BiTree; //用算法5.3 先序遍历的顺序建立二叉链表 void CreateBiTree(BiTree &T){ //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束,建空树 else{ T=new BiTNode; T->data=ch; //生成根结点 CreateBiTree(T->lchild); //递归创建左子树 CreateBiTree(T->rchild); //递归创建右子树 } //else } //CreateBiTree void InOrderTraverse(BiTree T){ //中序遍历二叉树T的递归算法 if(T){ InOrderTraverse(T->lchild); cout << T->data; InOrderTraverse(T->rchild); } } int main(){ BiTree tree; cout<<"请输入建立二叉链表的序列:\n"; CreateBiTree(tree); cout<<"中序遍历的结果为:\n"; InOrderTraverse(tree); cout<<endl; return 0; }
先序建立二叉树:ABD#G##EH###CF###
//算法5.2 中序遍历的非递归算法 求栈的长度就可以得出树的高度 #include<iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode { char data; //结点数据域 struct BiNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; //链栈的定义 typedef struct StackNode { BiTNode data; struct StackNode *next; }StackNode,*LinkStack; //用算法5.3 先序遍历的顺序建立二叉链表 void CreateBiTree(BiTree &T) { //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束,建空树 else{ T=new BiTNode; T->data=ch; //生成根结点 CreateBiTree(T->lchild); //递归创建左子树 CreateBiTree(T->rchild); //递归创建右子树 } //else } //CreateBiTree void InitStack(LinkStack &S) { //构造一个空栈S,栈顶指针置空 S=NULL; } bool StackEmpty(LinkStack S) { if(!S) return true; return false; } void Push(LinkStack &S,BiTree e) { //在栈顶插入元素*e StackNode *p=new StackNode; p->data=*e; p->next=S; S=p; } void Pop(LinkStack &S,BiTree e) { if(S!=NULL)//原书上写的是if(S==NULL)return ERROR; { *e=S->data; StackNode *p=S; S=S->next; delete p; } } void InOrderTraverse1(BiTree T) { // 中序遍历二叉树T的非递归算法 LinkStack S; BiTree p; BiTree q=new BiTNode; InitStack(S); p=T; while(p||!StackEmpty(S)) { if(p) { Push(S,p); //p非空根指针进栈,遍历左子树 p=p->lchild; } else { Pop(S,q); //p为空根指针退栈,访问根结点,遍历右子树 cout<<q->data; p=q->rchild; } } // while } // InOrderTraverse int main() { BiTree tree; cout<<"请输入建立二叉链表的序列:\n"; CreateBiTree(tree); cout<<"中序遍历的结果为:\n"; InOrderTraverse1(tree); cout<<endl; }
//算法5.3 先序遍历的的顺序建立二叉链表 #include<iostream> using namespace std; //二叉树的二叉链表存储表示 typedef struct BiNode { char data; //结点数据域 struct BiNode *lchild,*rchild; //左右孩子指针 }BiTNode,*BiTree; void CreateBiTree(BiTree &T) { //按先序次序输入二叉树中结点的值(一个字符),创建二叉链表表示的二叉树T char ch; cin >> ch; if(ch=='#') T=NULL; //递归结束,建空树 else{ T=new BiTNode; T->data=ch; //生成根结点 CreateBiTree(T->lchild); //递归创建左子树 CreateBiTree(T->rchild); //递归创建右子树 } //else } //CreateBiTree //用算法5.1 中序遍历的递归算法 void InOrderTraverse(BiTree T) { //中序遍历二叉树T的递归算法 if(T){ InOrderTraverse(T->lchild); cout << T->data; InOrderTraverse(T->rchild); } } int main() { BiTree tree; cout<<"请输入建立二叉链表的序列:\n"; CreateBiTree(tree); cout<<"所建立的二叉链表中序序列:\n"; InOrderTraverse(tree); cout<<endl; }
二、递归实现先序、中序、后续遍历
#include<iostream.h> #include<stdio.h> #include<stdlib.h> typedef struct BTree{ char date; struct BTree *lchild,*rchild; }BTree,* BiTree; BiTree intit(); //函数先序遍历 void out(BiTree); //先序输出 void outZ(BiTree); //中序输出 void outL(BiTree); //后序输出 int main(){ BiTree root; root=intit(); //out(root); //outZ(root); outL(root); cout<<endl; return 0; } void outL(BiTree root){ //后序输出 if(root){ out(root->lchild); out(root->rchild); printf("%c",root->date); } } void outZ(BiTree root){ //中序输出 if(root){ out(root->lchild); printf("%c",root->date); out(root->rchild); } } void out(BiTree root){ //先序输出 if(root){ printf("%c",root->date); out(root->lchild); out(root->rchild); } } BiTree intit(){ //建立二叉树 BiTree root; char da; scanf("%c",&da); if(da ==' '){ root=NULL; }else{ root=(BiTree)malloc(sizeof(BTree)); root->date=da; root->lchild=intit(); root->rchild=intit(); } return root; }
相关推荐
(2)先序、中序、后序遍历二叉树:递归算法。 (3)中序遍历二叉树:非递归算法(最好也能实现先序,后序非递归算法)。 (4)求二叉树的高度 。 (5)求二叉树的叶子个数。 (6)对于树中每一个元素值为x的结点...
建立一棵二叉树,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目...
1、 定义链接存储的二叉树类。 2、 实验验证如下算法的正确性、各种功能及指标: 1) 创建一棵二叉树,并对其初始化; 2)先根、中根、后根遍历二叉树; 3) 在二叉树中搜索给定结点的父结点; 4) 搜索二叉树中符合...
编写程序实现二叉树的如下操作: 1) 建立二叉链表 2) 二叉树的先序、中序、后序遍历 3) 求解二叉树的叶子结点个数 4) 将二叉树中所有结点的左、右子树相互交换 输入: 扩展二叉树先序序列:ab#d##ce###。其中#...
数据结构试验3二叉树建立,遍历等操作代码及运行结果。 实验内容: 采用二叉链表存储,实现二叉树的创建、遍历(递归)、赫夫曼编码和译码等典型操作。 1. 编程实现如下功能: (1)假设二叉树的结点值是字符型,...
3 程序所能达到的功能:生成一个新的二叉树,实现对二叉树的先序,中序,后序和层次遍历,计算二叉树的深度,结点数,叶结点数,。 4 测式数据: A生成一个新的二叉树后,直接在键盘上按要求输入字符,可以依次输入...
如果给出了遍历二叉树的前序序列和中序序列,则可以构造出唯一的一棵二叉树。试编写实现上述功能的程序。 [基本要求] 已知一棵二叉树的前序和中序序列,试设计完成下列任务的一个算法: (1)构造一棵二叉树...
详细的树和二叉树的教程,还附有源代码 部分代码如下: 二叉树头文件.h //二叉树的二叉链表存储表示 typedef struct BiTNode {TElemType data; //二叉树结点数据域 struct BiTNode *lchild,*rchild; //左右孩子指针...
按先序序列构造一棵二叉链表表示的二叉树T,并输出该T的中序遍历序列。实现提示: 1) 按先序序列建立一棵二叉树时,先构造根结点,再构造根的左子树,然后构造右子树;每棵子树又都是二叉树,所以构造一棵子树的过程...
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...
根据先序与中序遍历结果建立二叉树 输入为: 第一行:二叉树的先序遍历结果 第二行:二叉树的中序遍历结果 例如: ①输入aa则返回的指针指向的二叉树应该就是仅有一个节点,值为a. ②输入123213则返回的指针指向...
运用二叉链表实现二叉树的基本操作,包括:创建二叉树的存储结构、复制已有的二叉树、计算已有的二叉树的深度、先根序序列、中根序序列、后根序序列等。 输入格式:AB#C##D## 二、实验目的 掌握二叉链表及二叉树的...
1.采用二叉链表作为存储结构,创建一棵二叉树; 2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问...
一)建立二叉树+判空+遍历 (1)以二叉链表作为存储结构,从键盘以先序次序输入各个结点(空格字符表示空树)建立一棵二叉树; (2)对(1)中生成的二叉树进行判空; (3)对(1)中生成的二叉树进行遍历(分别实现...
二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树二叉树
一、实验名称:二叉树的遍历方法 二、实验目的: (1)熟悉C语言的上机环境,进一步掌握C语言的结构特点; (2)掌握二叉树的储存结构的定义及C语言实现; (3)掌握二叉树的三种遍历方法,即先序遍历,中序遍历,...
4.掌握计算二叉树的结点个数、二叉树的深度、二叉树的叶子结点和二叉树复制算法。 二、实验内容 1、构造基于先序遍历的二叉链表。 要求:按先序遍历规则,从键盘连续输入二叉树的先序序列,若无孩子结点,则用#代替...
在计算机科学中,二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 一棵深度为k,且有2^k-1个结点的...
根据二叉树的抽象数据类型的定义,使用二叉链表实现一个二叉树。 二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定...