假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序
文件 main.cpp 代码如下:
#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#include<stdlib.h> // atoi(),exit()
#include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等
#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样
typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果:构造空二叉树T
T=NULL;
}
void CreateBiTree(BiTree &T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}
void DestroyBiTree(BiTree &T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}
void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}
void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}
void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0
");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:
");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("
中序递归遍历二叉树:
");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("
后序递归遍历二叉树:
");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么?
if(p!=NULL)
{
Push(S,p->data);
p=p->lchild;
}
else//此时的p==NULL
{
Pop(S,e);//这句与p毫无关系
printf("%c",p->data);//那么这里怎么能访问p->data?
p=p->rchild;;//以及这里的p->rchild?
}
#include "iostream.h"
#include "string.h"
#include "malloc.h"
#include "stdio.h"
typedef struct btree
{
int data;//树结点的值域
int ltag,rtag;//树结点的左右线索
struct btree *left,*right;//树结点的左右指针,ltag,rtag=1时指向前驱和后继,否则指向左右孩子
}node;
node *SearchNode(node *q,node *r)
{//在根结点地址为q的中序线索二叉树中查找结点r将要插入的结点
node *p;
p=q;
while(1)
{
while(r->data<p->data&&p->ltag!=1){p=p->left;}//一直向左寻找
while(r->data>p->data&&p->rtag!=1){p=p->right;}//一直向右寻找
if(r->data<p->data&&p->ltag==1||r->data>p->data&&p->rtag==1||r->data==p->data)break;
//当r->data<p->data并且p没有左孩子或r->data>p->data并且p没有由孩子
//或r->data==p->data时,结点p找到,跳出循环
}
return(p);//返回p结点
}
node *InsertNode(node *rot,node *s)
{//在根结点地址为rot的中序线索二叉树中插入结点s
node *p;
if(rot==NULL)
{//如果根结点为空,s结点作为根结点插入。
rot=s;
rot->data=s->data;
rot->ltag=1;
rot->left=NULL;
rot->rtag=1;
rot->right=NULL;
return(rot);
}
p=SearchNode(rot,s);//调用SearchNode函数查找s将要插入的结点p的位置
if(s->data==p->data)
{//如果结点在树中已经存在,释放该结点并返回
free(s);
return(rot);
}
if(s->data<p->data)
{//如果s->data<p->data,则做为p的左孩子插入,此时s的前驱是插入前p的前驱,s的后继是p
s->ltag=1;
s->left=p->left;
s->rtag=1;
s->right=p;
p->ltag=0;
p->left=s;
}
if(s->data>p->data)
{//如果s->data>p->data,则做为p的右孩子插入,此时s的后继是插入前p的后继,s的前驱是p
s->rtag=1;
s->right=p->right;
s->ltag=1;
s->left=p;
p->rtag=0;
p->right=s;
}
return(rot);
}
node *CreatTree(node *rt)
{//以根结点为空开始构造中序线索二叉排序树,并返回根结点的地址
int m;//用于输入根结点的值域
node *q;
while(1)
{
printf("Please input number:\nm=");
//scanf("%d",&m);
cin>>m;//输入结点的值
if(m==-1) return(rt);
node *s;//建一个有待插入的新结点
s=(node *)malloc(sizeof(node));//给s开辟一个结点空间
s->data=m;
q=InsertNode(rt,s);//调用InsertNode函数一个个结点插入已生成的中序线索二叉树中,形成新的树
rt=q;
}
return(rt);
}
node *Search(node *root,int x)
{//在根结点地址为root的中序线索二叉树中查找结点值为x的结点p并返回p,若结点不存在则返回NULL。
node *p;//返回值为x的结点的位置
p=root;
while(1)
{
while(x<p->data&&p->ltag!=1){p=p->left;}
while(x>p->data&&p->rtag!=1){p=p->right;}
if(x<p->data&&p->ltag==1||x>p->data&&p->rtag==1||x==p->data)break;
}
if(x!=p->data) p=NULL;
return(p);
}
node *P_Next(node *root,int x)
{//查找根结点地址为root的中序线索二叉树中结点值为x的结点p按后序遍历的后继结点q
node *p,*q;//p是结点值为x的结点,q用来返回p按后序遍历的后继结点
p=Search(root,x);//调用Search函数查找结点p的位置
if(p==NULL)//值为x结点不存在,出错
{
return NULL;
}
if(p->ltag==0) return(p->left);//如果此结点有左孩子,返回左孩子结点
else
{
if(p->rtag==0) return(p->right);//如果此结点无左孩子有右孩子,返回右孩子结点
else//如果此结点为叶子结点
{
q=p->right;//寻找此结点的后继结点
if(q==NULL)//后继为空,此结点是按前序遍历的最后一个结点,返回空
{
printf("this node is last node\n");
return NULL;
}
else
{
while(q->rtag==1&&q->right!=NULL) {q=q->right;}//如果结点的后继没有右孩子,一直向后继方向寻找结点
if(q->right==NULL)
{
return NULL;
}
else return(q->right);//返回结点的右孩子结点
}
}
}
}
void display(node *t)
{//非递归中序遍历中序线索二叉排序树
printf("中序序列为:");
while(t->ltag!=1){t=t->left;}//寻找最左结点,即中序遍历的第一个结点
while(t!=NULL)
{
printf("%d ",t->data);//打印结点值
while(t->rtag==1)//结点右指针指向后继结点
{
t=t->right;
if(t==NULL)return;//t空,遍历结束
else printf("%d ",t->data);//打印结点值
}
if(t->rtag==0)//如果结点有右孩子
{
t=t->right;//从右孩子结点开始
while(t->ltag!=1){t=t->left;}//继续向左寻找此子树的最左结点
}
}
}
void main()
{
int w;
printf("输入一串正整数建立一棵中序线索二叉排序树最后以-1作为结束标志\n");
node *root;
root=NULL;
node *p;
node *q;
p=CreatTree(root);
display(p);
while(1)
{
cout<<"\n查找按前序遍历x的后继结点\nx=";
cin>>w;
q=P_Next(p,w);
if(q==NULL) cout<<"此结点不在树中或是按前序遍历的最后一个结点\n";
else
{
cout<<"\n此结点的后继结点为:";
cout<<q->data;
}
}
}
前序遍历?Pascal?
建立个过程叫print接受传送来的指针参数 这个你要自己定义的
然后在过程里加上这些就O
WriteLn(Tree.data);
Print(Tree.L);
Print(Tree.R);
Over 递归的
<算法与数据结构>书上有,现成的例子啊
假设二叉树采用链接方法存储,编写一个计算一棵二又树t的高度的函数...
【答案】:(1)数据结构 采用二叉树的链接表示。(2)思路 对一棵二叉树t,考察它左右子树的高度,取其中大的一个,再加1即为t的高度。(3)算法 int depth(BinTree t){ PBinTreeNode pbtree;int dl,dr;pbtree=t;if(pbtree==NULL)return-1;dl=depth(pbtree->llink);dr=depth(pbtree->r...
假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非...
int data;\/\/树结点的值域 int ltag,rtag;\/\/树结点的左右线索 struct btree *left,*right;\/\/树结点的左右指针,ltag,rtag=1时指向前驱和后继,否则指向左右孩子 }node;node *SearchNode(node *q,node *r){\/\/在根结点地址为q的中序线索二叉树中查找结点r将要插入的结点 node *p;p=q;while(...
已知二叉树采用二叉链表方式存放 要求返回二叉树T的后序序列的第一个...
InitBiTree(T); \/\/ 初始化二叉树T printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\\n");CreateBiTree(T); \/\/ 建立二叉树T printf("先序递归遍历二叉树:\\n");PreOrderTraverse(T,visit); \/\/ 先序递归遍历二叉树T printf("\\n中序递归遍历二叉...
已知二叉树按二叉链表方式存储 设计算法计算二叉树深度
二叉树结构体 struct bintree{ int data;struct bintree left;struct bintree right;};有一棵已建好的二叉树 根指针为*root 函数max定义为 int max(int a,int b){ if (a>b)return a;else return b;} 则设计递归算法 函数 depth int depth(struct bintree r){ if (r==NULL)return 0;i...
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
【答案】:C 本题用后序遍历肯定没问题,不过用层次遍历也可以实现,所以选D也不能算错,相比之下,后序遍历实现的程序更容易理解,作为单项选择题,首选的应该是C。
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
答案:C。用二叉链表存储结构也就是左孩子右兄弟的存储结构。后序遍历比较合理。正常的逻辑应该就是:做好当前结点子树内部的交换,然后交换当前结点的左右子树。刚好符合后序遍历的算法逻辑。1、交换好左子树 2、交换好右子树 3、交换左子树与右子树 其他算法如先序和按层次其逻辑都差不多,即访问当前...
已知二叉树按照二叉链表方式存储,编写算法,要求实现二叉树的竖向显示...
\/\/用左右孩子的方式输出一颗树 pBTNode St[MaxSize],p;int Level[MaxSize][2],top=-1,n,i,width=4;char type;if(bt!=NULL){ top++;St[top]=bt;Level[top][0]=width;Level[top][1]=2;while(top>-1){ p=St[top];n=Level[top][0];switch(Level[top][1]){ case 0:type='...
已知二叉树按照二叉链表的方式存储.编写算法.计算二叉树度为0.度为...
二叉树的先序中序后序 完全二叉树 平衡二叉树 利用二叉链表存储树 若二叉树采用二叉链表 二叉树遍历 什么是二叉树 其他类似问题2012-10-25 已知二叉树按二叉链表方式存储 设计算法计算二叉树深度 1 2013-11-08 已知二叉树采用链表存储结构,根结点指针为T,请写出计算二叉树... 2014-04-23 编写递归算...
设计一个算法将一棵以二叉链方式存储的二叉树t按顺序方式存储到数组A中...
\/\/建立二叉链表存储结构的二叉树,以p1为根节点,p2,p3分别为p1的左右子树,p4为p3的左子树 struct BTNode p1,p2,p3,p4; struct BTNode *t=&p1; p1.data='a'; p2.data='b'; p3.data='c'; p4.data='d'; p1.lchild=&p2; p1.rchild=&p3;...
若二叉树采用二叉链表存储结构,要交换其所有分支结点左、右子树的位置...
后续遍历和层次遍历均可实现左右子树的交换 不过层次遍历的实现消耗比后续大 还是后续好一些
愈贾阿法: 这是我做的. 中序遍历: var root,i,t,tl,tr,n:byte;depth,l,r:array[1..100]of byte; procedure b(p:byte); beginif p=0 then exit;b(l[p]);writeln(p,' ');b(r[p]); end; beginreadln(n);for i:=1 to n do beginreadln(t,l[t],r[t]);if l[t]>0 then inc(depth[l[t]]);if r[t]>0 ...
昌平区18581929305: 编程:假设二叉树采用链接方式存储,编写一个非递归程序对二叉树进行前序遍历 - ?
愈贾阿法: //---------------------------------------------------------------------------#include #include #include #include typedef struct node{ int data; struct node *left; struct node *right; } node,*tree; typedef struct stknode{ tree nd; struct stknode *next; }stknode; typedef struct { ...
昌平区18581929305: 假设二叉树采用连接方式存储,编写一个对二叉树进行前序遍历的递归和非递归程序?
愈贾阿法: 前序遍历?Pascal? 建立个过程叫print接受传送来的指针参数 这个你要自己定义的 然后在过程里加上这些就O WriteLn(Tree.data); Print(Tree.L); Print(Tree.R); Over 递归的
昌平区18581929305: 假设二叉树采用链接方式存储....拜托啊!!! - ?
愈贾阿法: 二叉树采用链接方式存储,在二叉树中删除所有以结点
昌平区18581929305: 假设二叉树采用链接存储结构存储,设计一个算法由二叉树B复制产生二叉树1 - ?
愈贾阿法: level起始赋值为1boolgetIndexLevel(TreeNode*root,TreeNode*found,int&level){if(root==NULL||found==NULL)returnfalse;if(root==found)returntrue;intnextlevel=level+1;if(getIndexLevel(root->left,found,
昌平区18581929305: 二叉树采用链接存储结构,设计一个算法计算一棵给定二叉树的"左孩子"的结点数.(重点是左孩子结点数) - ?
愈贾阿法: int count = 0; void countsinglechild(btree *t) { if(t) { if((t->left == null && t->right != null)||(t->left != null && t->right == null)) count++; countsinglechild(t->left); countsinglechild(t->right); } }
昌平区18581929305: 数据结构与算法 - ?
愈贾阿法: 二叉树求高度, 运行后, 输入:ABC__DE_G__F___ (_为空格) #include#include#define OK 1 #define NULL 0 typedef int Status; typedef char TElemType; typedef struct BiTNode //二叉树的二叉链表存储表示 { TElemType data; struct ...
昌平区18581929305: 假设二叉树采用链式方法存储,编写一个计算一棵二叉树t的高度的函数?
愈贾阿法: #include "stdio.h" #include "stdlib.h" int BiTreeDepth(BiTree T) { int h1,h2,h; if (T==NULL) return 0; else { h1=BiTreeDepth(T->lchild); h2=BiTreeDepth(T->rchild); if (h1>h2) h=h1+1; else h=h2+1; } return h; }
昌平区18581929305: 假设二叉树采用链式存储结构,编写一个算法释放该二叉树所占用的全部存储空间. - ?
愈贾阿法: 后序遍历二叉树的变种.一般的后序遍历是将节点信息输出,只需要将输出语句改为存储空间释放语句就行了
昌平区18581929305: 假设二叉树用二叉链表存储结构.编写一个算法统计二叉树的结点个数. - ?
愈贾阿法: int BiTreeCount(BiTree T) { int rNum,lNum; if(!T) return 0; else { lNum = BiTreeCount(T->lchild); rNum = BiTreeCount(T->rchild); return rNum + lNum + 1; }}