二叉树中序遍历递归算法
在前面一文,说过二叉树的递归遍历算法(二叉树先根(先序)遍历的改进),此文主要讲二叉树的非递归算法,采用栈结构
总结先根遍历得到的非递归算法思想如下:
1)入栈,主要是先头结点入栈,然后visit此结点
2)while,循环遍历当前结点,直至左孩子没有结点
3)if结点的右孩子为真,转入1)继续遍历,否则退出当前结点转入父母结点遍历转入1)
先看符合此思想的算法:
[cpp] view plain copy print?
int PreOrderTraverseNonRecursiveEx(const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空,就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
真正实用编程中,也没有必要太计较。
if(T){if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
以上就是中序遍历二叉树
这段程序我全有,具体如下:
#include <alloc.h>
#define ERROR 0;
#define FALSE 0;
#define TRUE 1;
#define OK 1;
typedef int ElemType;
typedef int Status;
typedef int KeyType;
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
typedef struct BinaryTree //定义二叉树
{
ElemType data;
struct BinaryTree *l;
struct BinaryTree *r;
}*BiTree,BiNode;//
BiNode * new()//为新结点开辟空间
{
return( (BiNode *)malloc(sizeof(BiNode)) );
}
CreateSubTree(BiTree *T,ElemType *all,int i)//创建新有子树
{
if ((all[i]==0)||i>16)
{
*T=NULL;
return OK;
}
*T=new();
if(*T==NULL) return ERROR;
(*T)->data=all[i];
CreateSubTree(&((*T)->l),all,2*i);
CreateSubTree(&((*T)->r),all,2*i+1);
}
CreateBiTree(BiTree *T)//创建新结点
{
ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,};
CreateSubTree(T,all,1);
}
printelem(ElemType d)//输出
{
printf("%d\n",d);
}
PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍历
{
if(T){
if(Visit(T->data))
if(PreOrderTraverse(T->l,Visit))
if(PreOrderTraverse(T->r,Visit)) return OK;
return ERROR;
} else return OK;
}
InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍历
{
if(T){
if(InOrderTraverse(T->l,Visit))
if(Visit(T->data))
if(InOrderTraverse(T->r,Visit)) return OK;
return ERROR;
}else return OK;
}
Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){
if(!T) {*p=f;return FALSE;}
else if EQ(key,T->data){ *p=T;return TRUE;}
else if LT(key,T->data) SearchBST(T->l,key,T,p);
else SearchBST(T->r,key,T,p);
}
Status InsertBST(BiTree *T,ElemType e){
BiTree p;
BiTree s;
if(!SearchBST(*T,e,NULL,&p)){
s=(BiTree)malloc(sizeof(BiNode));
s->data=e;s->l=s->r=NULL;
if(!p) *T=s;
else if (LT(e,p->data)) p->l=s;
else p->r=s;
return TRUE;
}
else return FALSE;
}
void Delete(BiTree *p){
BiTree q,s;
if(!(*p)->r){
q=(*p);
(*p)=(*p)->l;
free(q);
}
else if(!(*p)->l){
q=(*p);
(*p)=(*p)->r;
free(q);
}
else {
/* q=(*p);
s=(*p)->l;
while(s->r) {q=s; s=s->r;}
(*p)->data=s->data;
if(q!=(*p) ) q->r=s->l;
else q->l=s->l;
free(s);
*/
q=s=(*p)->l;
while(s->r) s=s->r;
s->r=(*p)->r;
free(*p);
(*p)=q;
}
}
Status DeleteBST(BiTree *T,KeyType key){
if (!(*T) )
{return FALSE;}
else{
if ( EQ(key,(*T)->data)) Delete(T);
else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key);
else DeleteBST( &((*T)->r),key);
return TRUE;
}
}
main()
{
BiTree root;
BiTree sroot=NULL;
int i;
int a[10]={45,23,12,3,33, 27,56,90,120,62};
system("cls");
CreateBiTree(&root);
printf("PreOrderTraverse:\n");
PreOrderTraverse(root,printelem);
printf("InOrderTraverse:\n");
InOrderTraverse(root,printelem);
for(i=0;i<10;i++)
InsertBST(&sroot,a[i]);
printf("InOrderTraverse:\n");
InOrderTraverse(sroot,printelem);
for(i=0;i<3;i++)
DeleteBST(&sroot,a[i]);
printf("Now sroot has nodes:\n");
InOrderTraverse(sroot,printelem);
}
把Visit往下移一行就行了。也就是先遍历lchild,再Visit,最后遍历rchild。
某二叉树中序序列为ABCDEFG,后序序列为BDCAFGE,则前序序列是?
应该是EACBDGF.遍历算法 1.中序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:(1)遍历左子树;(2)访问根结点;(3)遍历右子树。2.先序遍历的递归算法定义:若二叉树非空,则依次执行如下操作:(1) 访问根结点;(2) 遍历左子树;(3) 遍历右子树。3.后序遍历得递归算法定义:若二...
如何判断二叉树的先序遍历、中序遍历和后序遍历?
(3)中序遍历右子树 如右图所示二叉树,中根遍历结果:DBEAFC 3、后根遍历一般指后序遍历,指在访问根结点、遍历左子树与遍历右子树三者中,首先遍历左子树,然后遍历右子树,最后遍历访问根结点,在遍历左、右子树时,仍然先遍历左子树,然后遍历右子树,最后遍历根结点。后序遍历有递归算法和非递归...
紧急求助:请写出递归算法,从小到大输出二叉排序树中所有数据值>=x的...
由于是二叉排序树,因此只要使用中序遍历,输出比x大的数即可。void printMoreThanX(TreeNode *root, int x){ if (root == NULL)return;printMoreThanX(root->left, x, bPrint);if (root->data >= x){ printf("%d ", root->data);} printMoreThanX(root->right, x, bPrint);} ...
1用递归实现二叉树的先序、中序、后序三种遍历。2哈夫曼树问题
1通过调试为下面的二叉树建立二叉链表,并用递归实现二叉树的先序、中序、后序三种遍历。2[基本要求]:A:从终端读入字符集大小为n,及n个字符和n个权值,建立哈夫曼树,进行编码并且... 1通过调试为下面的二叉树建立二叉链表,并用递归实现二叉树的先序、中序、后序三种遍历。2[基本要求]: A:从终端读入字符...
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。这句话对吗...
因为二叉排序树的根节点大于左子树,小于右子树,然后使用中序遍历算法,中序遍历算法先遍历左子树,然后是根节点,然后是右子树。根据遍历的特性,所有的先遍历的结点,一定是小于后边遍历的结点,所以说中序遍历一棵二叉排序树的结点就可以得到一个排好序的序列。
建立二叉树,层序、先序、中序、后序遍历( 用递归或非递归的方法都需要...
Postorder(T->lchild); \/\/后序遍历左子树 Postorder(T->rchild); \/\/后序遍历右子树 printf("%c",T->data); \/\/访问结点 } } \/\/===采用后序遍历求二叉树的深度、结点数及叶子数的递归算法=== int TreeDepth(BinTree T){ int hl,hr,max;if(T){ hl=TreeDepth(T->lchild);...
已知某二叉树先序遍历序列为ABCDEFH,中序遍历序列是BDCEAHF
我们来举个简单的例子,先序序列为:ABDECF,中序序列为:DBEAFC。算法思想:先序遍历树的规则为中左右,可以看到先序遍历序列的第一个元素必为树的根节点,比如上例中的A就为根节点。再看中序遍历为:左中右,再根据根节点A,可知左子树包含元素为:DBE,右子树包含元素:FC。然后递归的 进行左...
前序.中序.后序遍历如何转换
指的是在对二叉树的递归遍历中,对根结点的遍历次序。假设递归访问函数如下:遍历(节点){访问(节点);遍历(节点.左孩子);遍历(节点.右孩子);} 则该遍历被称为先序遍历。相应的:遍历(节点){遍历(节点.左孩子);访问(节点);遍历(节点.右孩子);}以上遍历被称为中序遍历。后序遍历同理。
设二叉树的存储结构为二叉链表,编写有关二叉树的递归算法:
\/\/中序遍历求结点的深度和度为0,1,2的结点数,结果保存在pAns指的。。。void InOrderDO(BiTree *t , Answear * pAns){ \/\/遍历用的数据 BiTree **stack, **top, *p; \/\/求深度的数据 int curDeep, MostDeep;\/\/创建堆栈 if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))) { prin...
...并用递归算法对其进行前序、中序、后序遍历。要求
void postorder(bitree root)\/\/后根遍历 { if(!root)return;else { postorder(root->lchild);postorder(root->rchild);putchar(root->data);} } int leafcount(bitree root)\/\/计算叶子节点 { if(!root)return 0;else { if(!root->lchild&&!root->rchild)return 1;else return leafcount(...
谭星长春: #include<stdio.h> #include <malloc.h> #define maxsize 100 typedef char elemtype; typedef struct Node {elemtype data;struct Node *lchild;struct Node *rchild; }BitNode; void CreatBiTree(BitNode *&b,char *str) {BitNode *st[maxsize],*p=NULL; int ...
章贡区18256667670: 二叉树中序遍历递归算法 - ?
谭星长春: if(T){ if(InOrderTraverse(T->l,Visit)) if(Visit(T->data)) if(InOrderTraverse(T->r,Visit)) return OK; return ERROR; }else return OK; 以上就是中序遍历二叉树 这段程序我全有,具体如下:#include #define ERROR 0;#define FALSE 0;#define TRUE 1;...
章贡区18256667670: 二叉树的遍历? - ?
谭星长春: 遍历方案从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成.因此,在任一给定结点上,可以按某种次序执行三个操作:(1)访问结点本身(N),(2)遍历该结点的左子树(L),(3)遍历该结点的右子树(R)...
章贡区18256667670: 二叉树的中序遍历 - ?
谭星长春: 中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1)遍历左子树; (2)访问根结点; (3)遍历右子树.中序遍历的算法实现 用二叉链表做为存储结构,中序遍历算法可描述为: void InOrder(BinTree T) { //算法里①~⑥是为了说明执行过程加入的标号 ① if(T) { // 如果二叉树非空 ② InOrder(T->lchild); ③ printf("%c",T->data); // 访问结点 ④ InOrder(T->rchild); ⑤ } ⑥ } // InOrder
章贡区18256667670: 二叉树层次和中序遍历算法 - ?
谭星长春: 先序非递归算法 【思路】 假设:T是要遍历树的根指针,若T != NULL 对于非递归算法,引入栈模拟递归工作栈,初始时栈为空. 问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针? 方法1:访...
章贡区18256667670: 用递归的方式中序遍历二叉树算法描述 - ?
谭星长春: void travser(Node *node) { if(node==NULL) return; travser(node->left); cout<<node->data; travser(node->right); }
章贡区18256667670: 求二叉树的遍历算法 - ?
谭星长春: 这里有一份以前从网上找到的C语言代码,自己测试过,没有问题,写的很好,分享给你,供参考: #include<stdio.h> #include<stdlib.h> #define STACKINITSIZE 100 #define STACKINCREASESIZE 20 typedef char ElemType; //树结构 typedef ...
章贡区18256667670: 二叉树遍历该怎样写?(计算机二级考试) - ?
谭星长春: 前序遍历 是 根左右 中序 是 左根右 后序 是 左右根 都是递归遍历:1.中序遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1)中序遍历左子树; (2)访问根结点; (3)中序遍历右子树. 2.先序(前序)遍历的递归算法定义: 若二叉树非空,则依次执行如下操作: (1) 访问根结点; (2) 先序遍历左子树; (3) 先序遍历右子树. 3.后序遍历得递归算法定义: 若二叉树非空,则依次执行如下操作: (1)后序遍历左子树; (2)后序遍历右子树; (3)访问根结点
章贡区18256667670: 二叉树的遍历算法 - ?
谭星长春: 怎么又来问了,不是回答过你了吗?很简单,就是一个递归过程.在函数中以先序遍历的第一个结点在中序遍历中为界把中序遍历分为两半,再分别把左一半和右一半作为这个结点的左子树和右子树进行递归.完成递归之后再打印该结点即可....
章贡区18256667670: 按照二叉树的递归定义,对二叉树遍历的常用算法有哪三种? - ?
谭星长春: /*1 、前序遍历二叉树的递归算法 */ void preorder(bintree t) {if (t) {printf("%c",t->data);preorder(t->lchild);preorder(t->rchild);} } /*2 、中序遍历二叉树的递归算法 */ void inorder(bintree t) {if (t) {inorder(t->lchild);printf("%c",t->data);...