备案控制台
开发者社区 云计算 文章 正文

二叉树非递归遍历

2013-08-30 697
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 来源：http://www.cnblogs.com/JCSU/articles/2005944.html 【bitree.cpp】   /*************************************************************************...

来源：http://www.cnblogs.com/JCSU/articles/2005944.html

【bitree.cpp】

 

复制代码
/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : bitree.cpp
/* 功能描述    : 二叉树的非递归遍历
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : 输入示例与输出结果
/* 
/* e.g. input  : ABD###CE#F###
/* bi-tree     :
/*                 A
/*                / \
/*               B   C
/*              /   /
/*             D   E
/*                  \
/*                   F
/* 
/* pre-order traverse: A B D C E F
/* in-order traverse: D B A E F C
/* post-order traverse: D B F E C A
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >
#include  " common.h "

/* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */
Status Visit(TElemType e);
Status PreOrderTraverse(BiTree T, Status ( * Visit)(TElemType));
Status InOrderTraverse(BiTree T, Status ( * Visit)(TElemType));
Status PostOrderTraverse(BiTree T, Status ( * Visit)(TElemType));


 /* ******************************************************************************
/* <FUNC>
/* 函数名   : Visit
/* 功能     : 打印节点数据
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Visit(TElemType e)
{
    printf( " %c " , e);
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : PreOrderTraverse
/* 功能     : 前序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 非递归法
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status PreOrderTraverse(BiTree T, Status ( * Visit)(TElemType))
{
    LinkStack S;  BiTNode  * p  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) {  // 访问根结点, 遍历左子树
             if  ( ! Visit(p -> data))  return  ERROR;
            Push(S, p); p  =  p -> lchild; 
        }
         else  {  // 根指针出栈, 遍历右子树
            Pop(S, p); 
            p  =  p -> rchild;
        } // else
    }
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : InOrderTraverse
/* 功能     : 中序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 采用二叉链表存储结构, Visit是对数据元素操作的应用函数, 
/*            中序遍历二叉树T的非递归算法, 对每个数据元素调用函数Visit
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InOrderTraverse(BiTree T, Status ( * Visit)(TElemType e))
{
    LinkStack S;  BiTNode  * p  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) { Push(S, p); p  =  p -> lchild; }  // 根指针进栈, 遍历左子树
         else  {  // 根指针退栈, 访问根结点, 遍历右子树
            Pop(S, p);  if  ( ! Visit(p -> data))  return  ERROR;
            p  =  p -> rchild;
        } // else
    }
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : PostOrderTraverse
/* 功能     : 后序遍历二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 非递归法
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status PostOrderTraverse(BiTree T, Status ( * Visit)(TElemType))
{
    LinkStack S;  BiTNode  * p  =  NULL; 
    BiTNode  * top  =  NULL;   BiTNode  * pre  =  NULL;
    InitStack(S); p  =  T;
     while  (p  ||   ! StackEmpty(S)) {
         if  (p) {  // 遍历左子树
            Push(S, p); p  =  p -> lchild; 
        }
         else  {  // 根据栈顶元素的右孩子属性及与前驱节点的关系访问根结点或遍历右子树
                // 遍历结束条件: 栈为空且p为NULL
            GetTop(S, top);
             while  ( ! StackEmpty(S)  &&  ( ! top -> rchild  ||  top -> rchild  ==  pre)) {
                Pop(S, top);  pre  =  top; 
                 if  ( ! Visit(top -> data))  return  ERROR;
                GetTop(S, top);
            }
            p  =  StackEmpty(S)  ?  NULL : top -> rchild;
        } // else
    }
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : CreateBiTree
/* 功能     : 创建二叉树
/* 参数     : -
/* 返回值   : -
/* 备注     : 前序方式创建
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status CreateBiTree(BiTree  & T)
{
     char  ch  =  getchar();
     if ( ' # '   ==  ch) T  =  NULL;
     else  {
         if ( ! (T  =  (BiTNode  * )malloc( sizeof (BiTNode)))) exit(OVERFLOW);
        T -> data  =  ch;              // 生成根结点
        CreateBiTree(T -> lchild);   // 构造左子树
        CreateBiTree(T -> rchild);   // 构造右子树
    }
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : main
/* 功能     : 测试函数
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
void  main()
{
    BiTree T;
    CreateBiTree(T);

    printf( " Pre Order Traverse:  " );
    PreOrderTraverse(T, Visit);         // 前序方式遍历二叉树

    printf( " \nIn Order Traverse:  " );
    InOrderTraverse(T, Visit);          // 中序方式遍历二叉树

    printf( " \nPost Order Traverse:  " );
    PostOrderTraverse(T, Visit);        // 后序方式遍历二叉树
    printf( " \n " );
}
复制代码

 

 

【common.h】

 

复制代码
/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : common.h
/* 功能描述    : 栈和树的结构与函数原型 
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : -
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#ifndef __COMMON_H__
 #define  __COMMON_H__

#include  " stdio.h "  

 /* *****************************************************************************
/* 数据类型和常量定义
/***************************************************************************** */
typedef  int           Status;
typedef  int           TElemType;

 #define  TRUE         1
#define  FALSE        0
#define  OK           1
#define  ERROR        0
#define  OVERFLOW    -2

/* *****************************************************************************
/* 数据结构声明
/***************************************************************************** */

/*  二叉树的链式存储结构  */
typedef  struct  BiTNode {
    TElemType data;
     struct  BiTNode  * lchild,  * rchild;
} BiTNode,  * BiTree,  * SElemType;


 /*  存储树的节点指针的栈结构  */
typedef  struct  SNode {
    SElemType data;
     struct  SNode  * next;
}SNode;

typedef  struct  LinkStack {
    SNode  * base ;
    SNode  * top;
}LinkStack;


 /* *****************************************************************************
/* 函数原型声明
/***************************************************************************** */

/* 栈的基本操作 */
Status InitStack(LinkStack  & S);
Status StackEmpty(LinkStack S);
Status GetTop(LinkStack  & S, SElemType  & e);
Status Push(LinkStack  & S, SElemType e);
Status Pop(LinkStack  & S, SElemType  & e);

 #endif
复制代码

 

 

 

【stack.cpp】

 

复制代码
/* ******************************************************************************
/* <PRE>
/* 版权所有    : -
/* 模块名      : 树
/* 文件名      : stack.cpp
/* 功能描述    : 栈实现 
/* 作者        : <xxx>
/* 版本        : 1.0
/* -----------------------------------------------------------------------------
/* 备注        : -
/* -----------------------------------------------------------------------------
/* 修改记录    :
/* 日 期        版本     修改人        修改内容
/* 2011/01/01   1.0      <xxx>         创建
/* </PRE>
****************************************************************************** */
#include  < stdio.h >
#include  < stdlib.h >
#include  " common.h "

/* ******************************************************************************
/* <FUNC>
/* 函数名   : InitStack
/* 功能     : 构造空栈
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status InitStack(LinkStack  & S) {
    S.top  =  S. base   =  NULL;
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : GetTop
/* 功能     : 获取栈顶元素
/* 参数     : -
/* 返回值   : -
/* 备注     : -
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status GetTop(LinkStack  & S, SElemType  & e)
{
     if  (S.top  ==  NULL)  return  ERROR;
     else  e  =  S.top -> data;
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : Push
/* 功能     : 入栈
/* 参数     : -
/* 返回值   : -
/* 备注     : 插入元素e为新的栈顶元素
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Push(LinkStack  & S, SElemType e) {
    SNode  * p  =  (SNode  * )malloc( sizeof (SNode));
     if  ( ! p) exit(OVERFLOW);
    p -> data  =  e;
    p -> next  =  S.top;
    S.top  =  p;
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : Push
/* 功能     : 出栈
/* 参数     : -
/* 返回值   : -
/* 备注     : 若栈不空, 则删除S的栈顶元素, 用e返回其值, 并返回OK; 否则返回ERROR
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status Pop(LinkStack  & S, SElemType  & e) {
     if  (S.top  ==  S. base )
         return  ERROR;
    SNode  * p  =  S.top;
    S.top  =  S.top -> next;
    e  =  p -> data;
    free(p);
     return  OK;
}

 /* ******************************************************************************
/* <FUNC>
/* 函数名   : StackEmpty
/* 功能     : 判断栈是否为空
/* 参数     : -
/* 返回值   : -
/* 备注     : 若栈空则返回TRUE; 否则返回FALSE
/* 作者     : <xxx>
/* </FUNC>
****************************************************************************** */
Status StackEmpty(LinkStack S)
{
     if  (S. base   ==  S.top)  return  TRUE;
     else   return  FALSE;
}
复制代码

img_e00999465d1c2c1b02df587a3ec9c13d.jpg
微信公众号： 猿人谷
如果您认为阅读这篇博客让您有些收获，不妨点击一下右下角的【推荐】
如果您希望与我交流互动，欢迎关注微信公众号
本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接。

文章标签：
存储
yuanrengu
目录
相关文章
吹吹晚风
|
2月前
|
Python
二叉树前中后序遍历
这段内容是关于二叉树的前序、中序和后序遍历的Python实现。`Solution`类包含三个方法：`preorderTraversal`、`inorderTraversal`和`postorderTraversal`，分别返回二叉树节点值的前序、中序和后序遍历列表。每个方法都是递归的，遍历顺序为：前序（根-左-右）、中序（左-根-右）、后序（左-右-根）。
吹吹晚风
20 4
Man9Oo
|
9月前
|
存储 C++
非递归遍历二叉树
非递归遍历二叉树
Man9Oo
39 0
程序员行者孙
|
2月前
|
存储
详解二叉树的各种非递归遍历
详解二叉树的各种非递归遍历
程序员行者孙
18 0
dulu~dulu
|
2月前
|
算法
二叉树的递归遍历和非递归遍历
二叉树的递归遍历和非递归遍历
dulu~dulu
17 0
爱敲代码的小黄
|
2月前
求二叉树的层次遍历
求二叉树的层次遍历
爱敲代码的小黄
27 0
爱敲代码的小黄
|
2月前
|
Linux
求二叉树的先序遍历
求二叉树的先序遍历
爱敲代码的小黄
23 0
Rayce.
|
11月前
|
存储
线索化二叉树
线索化二叉树
Rayce.
42 0
爱躺平的威威
|
算法
二叉树的层次遍历
层次遍历就是即逐层地，从左到右访问所有节点
爱躺平的威威
151 0
二叉树的层次遍历
傲娇的萌
|
JavaScript 前端开发 Java
二叉树的先序、中序、后序遍历
二叉树的先序、中序、后序遍历
傲娇的萌
113 0
二叉树的先序、中序、后序遍历
Lucky小黄人^_^
|
存储
层序遍历、遍历二叉树的应用
层序遍历、遍历二叉树的应用
Lucky小黄人^_^
73 0

热门文章

最新文章

  • 1
    Spring Boot 集成 MyBatis和 SQL Server实践
  • 2
    V8中更快的异步函数和promises
  • 3
    semaphore
  • 4
    RHEL 4 update 4 DVD版制作
  • 5
    Linux命令——bash
  • 6
    MySQL DDL操作--------触发器最佳实战
  • 7
    PHP常用验证正则表达式
  • 8
    AKM项目总结之Foreign Trade相关的配置
  • 9
    [LeetCode] Wildcard Matching
  • 10
    用文件有效生成数组
  • 1
    流量控制系统，用正则表达式提取汉字
    25
  • 2
    Redis09-----List类型，有序，元素可以重复，插入和删除快，查询速度一般，一般保存一些有顺序的数据，如朋友圈点赞列表，评论列表等，LPUSH user 1 2 3可以一个一个推
    26
  • 3
    Redis08命令-Hash类型，也叫散列，其中value是一个无序字典，类似于java的HashMap结构，Hash结构可以将对象中的每个字段独立存储，可以针对每字段做CRUD
    25
  • 4
    Redis07命令-String类型字符串，不管是哪种格式，底层都是字节数组形式存储的，最大空间不超过512m，SET添加,MSET批量添加,INCRBY age 2可以，MSET,INCRSETEX
    27
  • 5
    S外部函数可以访问函数内部的变量的闭包-闭包最简单的用不了，闭包是内层函数+外层函数的变量，简称为函数套函数，外部函数可以访问函数内部的变量，存在函数套函数
    23
  • 6
    Redis06-Redis常用的命令,模糊的搜索查询往往会对服务器产生很大的压力，MSET k1 v1 k2 v2 k3 v3 添加，DEL是删除的意思，EXISTS age 可以用来查询是否有存在1
    30
  • 7
    Redis05数据结构介绍，数据结构介绍，官方网站中看到
    21
  • 8
    JS字符串数据类型转换，字符串如何转成变量，+号只要有一个是字符串，就会把另外一个转成字符串，- * / 都会把数据转成数字类型，数字型控制台是蓝色，字符型控制台是黑色，
    19
  • 9
    JS数组操作---删除，arr.pop()方法从数组中删除最后一个元素，并返回该元素的值，arr.shift() 删除第一个值，arr.splice()方法，删除指定元素，arr.splice，从第一
    19
  • 10
    定义好变量，${age}模版字符串，对象可以放null，检验数据类型console.log(typeof str)
    19

    • 相关电子书

    更多
  • 低代码开发师（初级）实战教程
  • 冬季实战营第三期：MySQL数据库进阶实战
  • 阿里巴巴DevOps 最佳实践手册
    • 下一篇
    部署LAMP环境（Alibaba Cloud Linux 3）