中序遍历二叉树-二叉树的非递归操作。。

问题描述

二叉树的非递归操作。。

如何用栈实现二叉树的非递归操作，越详细越好，谢谢各位啦。一定要详细哦

解决方案

 void inOrder2(BinTree *root)      //非递归中序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            cout<<p->data<<" ";
            s.pop();
            p=p->rchild;
        }
    }
}

解决方案二：

 void preOrder2(BinTree *root)     //非递归前序遍历
{
    stack<BinTree*> s;
    BinTree *p=root;
    while(p!=NULL||!s.empty())
    {
        while(p!=NULL)
        {
            cout<<p->data<<" ";
            s.push(p);
            p=p->lchild;
        }
        if(!s.empty())
        {
            p=s.top();
            s.pop();
            p=p->rchild;
        }
    }
}

void postOrder3(BinTree *root)     //非递归后序遍历
{
    stack<BinTree*> s;
    BinTree *cur;                      //当前结点
    BinTree *pre=NULL;                 //前一次访问的结点
    s.push(root);
    while(!s.empty())
    {
        cur=s.top();
        if((cur->lchild==NULL&&cur->rchild==NULL)||
           (pre!=NULL&&(pre==cur->lchild||pre==cur->rchild)))
        {
            cout<<cur->data<<" ";  //如果当前结点没有孩子结点或者孩子节点都已被访问过
              s.pop();
            pre=cur;
        }
        else
        {
            if(cur->rchild!=NULL)
                s.push(cur->rchild);
            if(cur->lchild!=NULL)
                s.push(cur->lchild);
        }
    }
}

解决方案三：

谢谢了，不过能不能再解释一下，代码我看不懂

解决方案四：

二叉树的遍历 非递归操作
二叉树各种操作的非递归实现

解决方案五：

#include
#include
#include
using namespace std;
//二叉树结点的描述
typedef struct BiTNode
{
char data;
struct BiTNode lchild, *rchild; //左右孩子
}BiTNode,*BiTree;
//按先序遍历创建二叉树
//BiTree *CreateBiTree() //返回结点指针类型
//void CreateBiTree(BiTree &root) //引用类型的参数
void CreateBiTree(BiTNode **root) //二级指针作为函数参数
{
char ch; //要插入的数据
scanf("
%c", &ch);
//cin>>ch;
if(ch=='#')
*root = NULL;
else
{
*root = (BiTNode *)malloc(sizeof(BiTNode));
(*root)->data = ch;
printf("请输入%c的左孩子：",ch);
CreateBiTree(&((*root)->lchild));
printf("请输入%c的右孩子：",ch);
CreateBiTree(&((*root)->rchild));
}
}
//前序遍历的算法程序
void PreOrder(BiTNode *root)
{
if(root==NULL)
return ;
printf("%c ", root->data); //输出数据
PreOrder(root->lchild); //递归调用，前序遍历左子树
PreOrder(root->rchild); //递归调用，前序遍历右子树
}
//中序遍历的算法程序
void InOrder(BiTNode *root)
{
if(root==NULL)
return ;
InOrder(root->lchild); //递归调用，前序遍历左子树
printf("%c ", root->data); //输出数据
InOrder(root->rchild); //递归调用，前序遍历右子树
}
//后序遍历的算法程序
void PostOrder(BiTNode *root)
{
if(root==NULL)
return ;
PostOrder(root->lchild); //递归调用，前序遍历左子树
PostOrder(root->rchild); //递归调用，前序遍历右子树
printf("%c ", root->data); //输出数据

}
/
二叉树的非递归前序遍历，前序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作，
每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。
*/
void PreOrder_Nonrecursive2(BiTree T) //先序遍历的非递归

{
if(!T)

return ;

stack<BiTree> s;
s.push(T);
while(!s.empty())
{
    BiTree temp = s.top();
    cout<<temp->data<<" ";
    s.pop();
    if(temp->rchild)
        s.push(temp->rchild);
    if(temp->lchild)
        s.push(temp->lchild);
}

}
void PreOrder_Nonrecursive(BiTree T) //先序遍历的非递归
{
if(!T)
return ;
stack s;
while(T) // 左子树上的节点全部压入到栈中
{
s.push(T);
cout<data<<" ";
T = T->lchild;
}

while(!s.empty())
{
    BiTree temp = s.top()->rchild;  // 栈顶元素的右子树
    s.pop();                        // 弹出栈顶元素
    while(temp)          // 栈顶元素存在右子树，则对右子树同样遍历到最下方
    {
        cout<<temp->data<<"  ";
        s.push(temp);
        temp = temp->lchild;
    }
}

}
void InOrderTraverse(BiTree T) // 中序遍历的非递归
{
if(!T)
return ;
stack S;
BiTree curr = T->lchild; // 指向当前要检查的节点
S.push(T);
while(curr != NULL || !S.empty())
{
while(curr != NULL) // 一直向左走
{
S.push(curr);
curr = curr->lchild;
}
curr = S.top();
S.pop();
cout<data<<" ";
curr = curr->rchild;
}
}
void PostOrder_Nonrecursive(BiTree T) // 后序遍历的非递归

{

stack S;

BiTree curr = T ; // 指向当前要检查的节点
BiTree previsited = NULL; // 指向前一个被访问的节点
while(curr != NULL || !S.empty()) // 栈空时结束

{

while(curr != NULL) // 一直向左走直到为空
{

S.push(curr);

curr = curr->lchild;

}

curr = S.top();
// 当前节点的右孩子如果为空或者已经被访问，则访问当前节点
if(curr->rchild == NULL || curr->rchild == previsited)

{

cout<data<<" ";

previsited = curr;

S.pop();

curr = NULL;

}

else
curr = curr->rchild; // 否则访问右孩子
}

}
void PostOrder_Nonrecursive(BiTree T) // 后序遍历的非递归 双栈法
{

stack s1 , s2;

BiTree curr ; // 指向当前要检查的节点
s1.push(T);
while(!s1.empty()) // 栈空时结束

{
curr = s1.top();
s1.pop();
s2.push(curr);
if(curr->lchild)
s1.push(curr->lchild);
if(curr->rchild)
s1.push(curr->rchild);
}
while(!s2.empty())
{
printf("%c ", s2.top()->data);
s2.pop();
}
}
int visit(BiTree T)
{
if(T)
{
printf("%c ",T->data);
return 1;
}
else
return 0;
}
void LeverTraverse(BiTree T) //方法一、非递归层次遍历二叉树
{
queue Q;
BiTree p;
p = T;
if(visit(p)==1)
Q.push(p);
while(!Q.empty())
{
p = Q.front();
Q.pop();
if(visit(p->lchild) == 1)
Q.push(p->lchild);
if(visit(p->rchild) == 1)
Q.push(p->rchild);
}
}
void LevelOrder(BiTree BT) //方法二、非递归层次遍历二叉树
{
BiTNode *queue[10];//定义队列有十个空间
if (BT==NULL)
return;
int front,rear;
front=rear=0;
queue[rear++]=BT;
while(front!=rear)//如果队尾指针不等于对头指针时
{
cout<data<<" "; //输出遍历结果
if(queue[front]->lchild!=NULL) //将队首结点的左孩子指针入队列
{
queue[rear]=queue[front]->lchild;
rear++; //队尾指针后移一位
}
if(queue[front]->rchild!=NULL)
{
queue[rear]=queue[front]->rchild; //将队首结点的右孩子指针入队列
rear++; //队尾指针后移一位
}
front++; //对头指针后移一位
}
}
int depth(BiTNode *T) //树的深度
{
if(!T)
return 0;
int d1,d2;
d1=depth(T->lchild);
d2=depth(T->rchild);
return (d1>d2?d1:d2)+1;
//return (depth(T->lchild)>depth(T->rchild)?depth(T->lchild):depth(T->rchild))+1;
}
int CountNode(BiTNode *T)
{
if(T == NULL)
return 0;
return 1+CountNode(T->lchild)+CountNode(T->rchild);
}
int main(void)
{
BiTNode *root=NULL; //定义一个根结点
int flag=1,k;
printf(" 本程序实现二叉树的基本操作。
");
printf("可以进行建立二叉树，递归先序、中序、后序遍历，非递归先序、中序遍历及非递归层序遍历等操作。
");
while(flag)
{
printf("
");
printf("|--------------------------------------------------------------|
");
printf("| 二叉树的基本操作如下: |
");
printf("| 0.创建二叉树 |
");
printf("| 1.递归先序遍历 |
");
printf("| 2.递归中序遍历 |
");
printf("| 3.递归后序遍历 |
");
printf("| 4.非递归先序遍历 |
");
printf("| 5.非递归中序遍历 |
");
printf("| 6.非递归后序遍历 |
");
printf("| 7.非递归层序遍历 |
");
printf("| 8.二叉树的深度 |
");
printf("| 9.二叉树的结点个数 |
");
printf("| 10.退出程序 |
");
printf("|--------------------------------------------------------------|
");
printf(" 请选择功能：");
scanf("%d",&k);
switch(k)
{
case 0:
printf("请建立二叉树并输入二叉树的根节点：");
CreateBiTree(&root);
break;
case 1:
if(root)
{
printf("递归先序遍历二叉树的结果为：");
PreOrder(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 2:
if(root)
{
printf("递归中序遍历二叉树的结果为：");
InOrder(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 3:
if(root)
{
printf("递归后序遍历二叉树的结果为：");
PostOrder(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 4:
if(root)
{
printf("非递归先序遍历二叉树：");
PreOrder_Nonrecursive(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 5:
if(root)
{
printf("非递归中序遍历二叉树：");
InOrderTraverse(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 6:
if(root)
{
printf("非递归后序遍历二叉树：");
PostOrder_Nonrecursive(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 7:
if(root)
{
printf("非递归层序遍历二叉树：");
//LeverTraverse(root);
LevelOrder(root);
printf("
");
}
else
printf(" 二叉树为空！
");
break;
case 8:
if(root)
printf("这棵二叉树的深度为：%d
",depth(root));
else
printf(" 二叉树为空！
");
break;
case 9:
if(root)
printf("这棵二叉树的结点个数为：%d
",CountNode(root));
else
printf(" 二叉树为空！
");
break;
default:
flag=0;
printf("程序运行结束，按任意键退出！
");
}
}
system("pause");
return 0;
}

时间： 2025-01-31 05:36:42

中序遍历二叉树-二叉树的非递归操作。。的相关文章

C++中前序遍历和中序遍历重建二叉树例子

已知某二叉树的前序遍历结果和中序遍历结果,假如前序遍历和中序遍历的结果中都不含重复的数字.例如某个二叉树的前序遍历的序列为{1,2,4,7,3,5,6,8}中序遍历序列{4,7,2,1,5,3,8,6}. 通过前序遍历和中序遍历重建二叉树  struct BinaryTreeNode{  int m_nValue;  BinaryTreeNode* m_pLeft;  BinaryTreeNode* m_pRight; } 先把三种遍历算法写上: // 前序遍历 void preOrder(Bi

中序遍历-为什么二叉树的中序非递归算法无法实现

问题描述 为什么二叉树的中序非递归算法无法实现 // 实验三.cpp : 定义控制台应用程序的入口点. // #include "stdafx.h" #include using namespace std; #define true 1 #define false 0 #define OK 1 #define ERROR 0 #define OVERFLOW -2 #define MAXSIZE 100 typedef char TElemType; typedef int Stat

二叉树的应用-先序遍历中序遍历还原二叉树

二叉树的一些应用 还是大实验要求的 还有已知先序遍历 中序遍历求后续遍历 #include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; #define MAX 100 //节点个数 #define Null 0 typedef int Elemtype; class node { public: Elemtype data; no

c语言-已知二叉树的中序遍历序列与层次遍历序列分别存于数组A[1-n] B[1-n]中，建立二叉树的二叉链表。

问题描述 已知二叉树的中序遍历序列与层次遍历序列分别存于数组A[1-n] B[1-n]中,建立二叉树的二叉链表. 已知二叉树的中序遍历序列与层次遍历序列分别将值存于数组A[1-n].B[1-n]中,请编程建立二叉树的二叉链表. 二叉树结点定义 typedef struct { Elemtype data; BiNode* lchild,rchild; }BiNode,*BiTree; 解决方案 http://www.zybang.com/question/23e04267bb862ea67197

根据先序中序遍历建树【模板】

主要就是通过先序找到当前子树根节点,再用中序遍历分子树,不断递归下去. #include <iostream> #include <stdio.h> #include <cstring> #include <vector> #include <cmath> #include <algorithm> #include <set> #include <cassert> #include <time.h>

二叉树遍历算法之二：中序遍历

中序遍历的递归实现 中序遍历遍历指的是先访问二叉树中节点的左孩子,再访问当前节点,最后再访问其右孩子.具体访问步骤如下: 首先访问根节点,判断根节点是否有左孩子,如果有,进行第二步:如果没有,跳到第三步: 访问左孩子,继续判断当前节点是否有左孩子,如果有则继续访问其左孩子,直到某节点的左孩子为空 判断是否有右孩子,如果有,则继续判断当前节点是否有左孩子,一直到某节点没有左孩子为止 把第二步访问的节点做为当前节点(该节点无左孩子,如图中的15节点),按照规则,下一步应该访问其右孩子 返回到第四部节

二叉树的创建、前序遍历、中序遍历、后序遍历

// BTree.cpp : Defines the entry point for the console application. /* 作者:成晓旭 时间:2001年7月2日(9:00:00-14:00:00) 内容:完成二叉树的创建.前序遍历.中序遍历.后序遍历 时间:2001年7月2日(14:00:00-16:00:00) 内容:完成二叉树的叶子节点访问,交换左.右孩子 */ #include "stdafx.h" #include "stdlib.h"

数据结构 排序二叉树(BST) 插入删除查询 中序遍历 销毁(后序遍历)

结构概念如下: 二叉排序树(binary sort tree): 1.也叫做二叉查找树 2.如果他的左子树不为空,则左子树上所有结点的 值均小于他的根结构的值 3.如果他的右子树不为空,则右子树上所有结点的 值均大于他的根结构的值 4.他的左右子树分别为二叉排序树 5.按照二叉树中序遍历其返回结果树有序的 下面就是一颗典型的二叉树,只是是字母,可以将字母换位字母的顺序进行审视,但是它不是平衡二叉树 排序二叉树(BST)的优点在于进行数据查找比较方便,因为他是按照数据来到的顺序进行如上的规则进行的

二叉树系列（二）：已知中序遍历序列和后序遍历序列，求先序遍历序列

前面已经介绍过三种遍历方法的规则,为了大家看着方便,这里我们在重新介绍一遍:   1.先序遍历   (1)访问根结点:   (2)先序遍历左子树:   (3)先序遍历右子树.   2.中序遍历   (1)中序遍历左子树:   (2)访问根结点:   (3)中序遍历右子树.   3.后序遍历   (1)后序遍历左子树:   (2)后序遍历右子树:   (3)访问根结点.   知道了二叉树的三种遍历规则,只要有中序遍历序列和前后任一种遍历序列,我们就可以求出第三种遍历序列,今天我们研究的是已知中序和