当前位置:  编程技术>c/c++/嵌入式

深入遍历二叉树的各种操作详解(非递归遍历)

    来源: 互联网  发布时间:2014-10-15

    本文导语:  先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序、中序、后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分...

先使用先序的方法建立一棵二叉树,然后分别使用递归与非递归的方法实现前序、中序、后序遍历二叉树,并使用了两种方法来进行层次遍历二叉树,一种方法就是使用STL中的queue,另外一种方法就是定义了一个数组队列,分别使用了front和rear两个数组的下标来表示入队与出队,还有两个操作就是求二叉树的深度、结点数。。。
代码如下:

#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("n%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 s;
    s.push(T);
    while(!s.empty())
    {
        BiTree temp = s.top();
        coutlchild)
            s.push(temp->lchild);
    }
}
void PreOrder_Nonrecursive(BiTree T)     //先序遍历的非递归
{
    if(!T)
        return ;
    stack s;
    while(T)          // 左子树上的节点全部压入到栈中
    {
        s.push(T);
        coutrchild == previsited)  
        {  
            coutlchild);
        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)//如果队尾指针不等于对头指针时
    {
        coutrchild!=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("                     本程序实现二叉树的基本操作。n");
    printf("可以进行建立二叉树,递归先序、中序、后序遍历,非递归先序、中序遍历及非递归层序遍历等操作。n");
    while(flag)
    {
        printf("n");
        printf("|--------------------------------------------------------------|n");
        printf("|                    二叉树的基本操作如下:                     |n");
        printf("|                        0.创建二叉树                          |n");
        printf("|                        1.递归先序遍历                        |n");
        printf("|                        2.递归中序遍历                        |n");
        printf("|                        3.递归后序遍历                        |n");
        printf("|                        4.非递归先序遍历                      |n");
        printf("|                        5.非递归中序遍历                      |n");
        printf("|                        6.非递归后序遍历                      |n");
        printf("|                        7.非递归层序遍历                      |n");
        printf("|                        8.二叉树的深度                        |n");
        printf("|                        9.二叉树的结点个数                    |n");
        printf("|                        10.退出程序                            |n");
        printf("|--------------------------------------------------------------|n");
        printf("                        请选择功能:");
        scanf("%d",&k);
        switch(k)
        {
        case 0:
            printf("请建立二叉树并输入二叉树的根节点:");
            CreateBiTree(&root);
            break;
        case 1:
            if(root)
            {
                printf("递归先序遍历二叉树的结果为:");
                PreOrder(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 2:
            if(root)
            {
                printf("递归中序遍历二叉树的结果为:");
                InOrder(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 3:
            if(root)
            {
                printf("递归后序遍历二叉树的结果为:");
                PostOrder(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 4:
            if(root)
            {
                printf("非递归先序遍历二叉树:");
                PreOrder_Nonrecursive(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 5:
            if(root)
            {
                printf("非递归中序遍历二叉树:");
                InOrderTraverse(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 6:
            if(root)
            {
                printf("非递归后序遍历二叉树:");
                PostOrder_Nonrecursive(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 7:
            if(root)
            {
                printf("非递归层序遍历二叉树:");
                //LeverTraverse(root);
                LevelOrder(root);
                printf("n");
            }
            else
                printf("          二叉树为空!n");
            break;
        case 8:
            if(root)
                printf("这棵二叉树的深度为:%dn",depth(root));
            else
                printf("          二叉树为空!n");
            break;
        case 9:
            if(root)
                printf("这棵二叉树的结点个数为:%dn",CountNode(root));
            else
                printf("          二叉树为空!n");
            break;
        default:
            flag=0;
            printf("程序运行结束,按任意键退出!n");
        }
    }
    system("pause");
    return 0;
}

运行效果图如下:



分别输入:
1
2
4
#
#
5
#
#
3
6
#
#
7
#
#
就可以构造如下图所示的二叉树了。。

后序遍历非递归的另外一种写法:

代码如下:

    /*
    后序遍历由于遍历父节点是在遍历子节点之后,而且左节点和右节点遍历后的行为不一样,
    所以需要用变量来记录前一次访问的节点,根据前一次节点和现在的节点的关系来确定具体执行什么操作
    */ 
    void Postorder(BiTree T) 
    { 
        if(T == NULL) 
            return ; 
        stack s; 
        BiTree prev = NULL , curr = NULL; 
        s.push(T); 
        while(!s.empty()) 
        { 
            curr = s.top(); 
            if(prev == NULL  || prev->lchild == curr || prev->rchild == curr) 
            { 
                if(curr->lchild != NULL) 
                    s.push(curr->lchild); 
                else if(curr->rchild != NULL) 
                    s.push(curr->rchild); 
            } 
            else if(curr->lchild == prev) 
            { 
                if(curr->rchild != NULL) 
                    s.push(curr->rchild); 
            } 
            else 
            { 
                coutlchild , pNode , path) ) 
        { 
            path.push_back(pRoot->lchild); 
            return true; 
        } 
        else if(GetNodePath(pRoot->rchild , pNode , path) ) 
        { 
            path.push_back(pRoot->rchild); 
            return true; 
        } 
        return false; 
    } 
    TreeNode *GetLastCommonNode(const vector &path1 , const vector &path2) 
    { 
        vector::const_iterator iter1 = path1.begin(); 
        vector::const_iterator iter2 = path2.begin(); 
        TreeNode *pLast; 
        while(iter1 != path1.end() && iter2 != path2.end() ) 
        { 
            if(*iter1 == *iter2) 
                pLast = *iter1; 
            else 
                break; 
            iter1++; 
            iter2++; 
        } 
        return pLast; 
    } 
    TreeNode *GetLastCommonParent(TreeNode *pRoot , TreeNode *pNode1 , TreeNode *pNode2) 
    { 
        if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL) 
            return  NULL; 
        vector path1; 
        GetNodePath(pRoot , pNode1 , path1); 

        vector path2; 
        GetNodePath(pRoot , pNode2 , path2); 
        return GetLastCommonNode(path1 , path2); 
    } 

    
 
 
 
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术,将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外,均为转载、整理或搜集自网络。欢迎任何形式的转载,转载请注明出处。












  • 相关文章推荐
  • 深入JDBC sqlserver连接写法的详解
  • 深入mysql YEAR() MONTH() DAYOFMONTH()日期函数的详解
  • 深入SQLServer中ISNULL与NULLIF的使用详解
  • 深入C++可见性与生命期的区别详解
  • 深入mysql并发插入优化详解
  • 深入android Unable to resolve target 'android-XX'详解
  • 深入MYSQL字符数字转换的详解
  • 深入SQL Server中定长char(n)与变长varchar(n)的区别详解
  • 深入C#任务管理器中应用程序选项隐藏程序本身的方法详解
  • 深入Windows下的回车是回车换行(rn)还是换行回车(nr)的详解
  • 深入分析NTFS中文件被锁定导致Process.Start失败的详解
  • 深入C# 内存管理以及优化的方法详解
  • 深入c# Func委托的详解
  • 深入分析Java内存区域的使用详解
  • Informatica bulk与normal模式的深入详解
  • 深入JAVA对象深度克隆的详解
  • 深入mysql存储过程中表名使用参数传入的详解
  • 深入SQL截取字符串(substring与patindex)的详解
  • 深入Java不可变类型的详解
  • 深入Android开发FAQ的详解
  • Docker支持更深入的容器日志分析
  • 关于《深入浅出MFC》
  • Linux有没有什么好的高级的书,我要深入,
  • 深入理解linux内核
  • [100分]有没有关于binutils的深入的资料?或者深入底层的资料?
  • 深入理解PHP内核 TIPI
  • 想深入学习Java应该学习哪些东西
  • 哪位有《JSP深入编程》电子版?
  • 想要深入学习LINUX该学什么?
  • 100分求:哪儿有《深入理解linux内核》可供下哉!
  • 如何深入Linux的内核学习?


  • 站内导航:


    特别声明:169IT网站部分信息来自互联网,如果侵犯您的权利,请及时告知,本站将立即删除!

    ©2012-2021,,E-mail:www_#163.com(请将#改为@)

    浙ICP备11055608号-3