文档章节

三种遍历树的算法

刺猬一号
 刺猬一号
发布于 2017/05/14 19:05
字数 813
阅读 35
收藏 1
递归与非递归转换的基础知识是能够正确理解三种树的遍历方法:前序,中序和后序,第一篇就是关于这三种遍历方法的递归和
非递归算法。


如何用栈实现递归与非递归的转换(一)三种遍历树的算法

一.为什么要学习递归与非递归的转换的实现方法? 
1)并不是每一门语言都支持递归的. 
2)有助于理解递归的本质. 
3)有助于理解栈,树等数据结构.

二.三种遍历树的递归和非递归算法 
    递归与非递归的转换基于以下的原理:所有的递归程序都可以用树结构表示出来.需要说明的是,这个"原理"并没有经过严格的
数学证明,只是我的一个猜想,不过在至少在我遇到的例子中是适用的.学习过树结构的人都知道,有三种方法可以遍历树:前序,中序
,后序.理解这三种遍历方式的递归和非递归的表达方式是能够正确实现转换的关键之处,所以我们先来谈谈这个.需要说明的是,这里
以特殊的二叉树来说明,不过大多数情况下二叉树已经够用,而且理解了二叉树的遍历,其它的树遍历方式就不难。 
            了. 
            1)前序遍历

            a)递归方式: 
                  void preorder_recursive(Bitree T)      /* 先序遍历二叉树的递归算法 */ 
                        { 
                           if (T) { 
                              visit(T);          /* 访问当前结点 */ 
                              preorder_recursive(T->lchild);   /* 访问左子树 */ 
                              preorder_recursive(T->rchild);   /* 访问右子树 */ 
                           } 
                        }


            b)非递归方式 
                  void preorder_nonrecursive(Bitree T)      /* 先序遍历二叉树的非递归算法 */ 
                        { 
                           initstack(S); 
                           push(S,T);             /* 根指针进栈 */ 
                           while(!stackempty(S)) { 
                              while(gettop(S,p)&&p) {      /* 向左走到尽头 */ 
                                 visit(p);      /* 每向前走一步都访问当前结点 */ 
                                 push(S,p->lchild); 
                              } 
                              pop(S,p); 
                              if(!stackempty(S)) {      /* 向右走一步 */ 
                                 pop(S,p); 
                                 push(S,p->rchild); 
                              } 
                           } 
                        }



            2)中序遍历

            a)递归方式 
                  void inorder_recursive(Bitree T)      /* 中序遍历二叉树的递归算法 */ 
                        { 
                           if (T) { 
                              inorder_recursive(T->lchild);   /* 访问左子树 */ 
                              visit(T);          /* 访问当前结点 */ 
                              inorder_recursive(T->rchild);   /* 访问右子树 */ 
                           } 
                        }


            b)非递归方式 
                  void inorder_nonrecursive(Bitree T) 
                        { 
                           initstack(S);            /* 初始化栈 */ 
                           push(S, T);            /* 根指针入栈 */

                           while (!stackempty(S)) {          
                              while (gettop(S, p) && p)    /* 向左走到尽头 */ 
                                 push(S, p->lchild); 
                              pop(S, p);         /* 空指针退栈 */ 
                              if (!stackempty(S)) { 
                                 pop(S, p); 
                                 visit(p);      /* 访问当前结点 */ 
                                 push(S, p->rchild);   /* 向右走一步 */ 
                              } 
                           } 
                        }


            3)后序遍历

            a)递归方式 
                  void postorder_recursive(Bitree T)      /* 中序遍历二叉树的递归算法 */ 
                        { 
                           if (T) { 
                              postorder_recursive(T->lchild);   /* 访问左子树 */ 
                              postorder_recursive(T->rchild);   /* 访问右子树 */ 
                              visit(T);             /* 访问当前结点 */ 
                           } 
                        }


            b)非递归方式 
                  typedef struct { 
                           BTNode* ptr; 
                           enum {0,1,2} mark; 
                        } PMType;                /* 有mark域的结点指针类型 */

                        void postorder_nonrecursive(BiTree T)      /* 
                  后续遍历二叉树的非递归算法 */ 
                        { 
                           PMType a; 
                           initstack(S);             /* S的元素为PMType类型 */ 
                           push (S,{T,0});          /* 根结点入栈 */ 
                           while(!stackempty(S)) { 
                              pop(S,a); 
                              switch(a.mark) 
                              { 
                              case 0: 
                                 push(S,{a.ptr,1});    /* 修改mark域 */ 
                                 if(a.ptr->lchild) 
                                    push(S,{a.ptr->lchild,0}); /* 访问左子树 */ 
                                 break; 
                              case 1: 
                                 push(S,{a.ptr,2});    /* 修改mark域 */ 
                                 if(a.ptr->rchild) 
                                    push(S,{a.ptr->rchild,0}); /* 访问右子树 */ 
                                 break; 
                              case 2: 
                                 visit(a.ptr);       /* 访问结点 */ 
                              } 
                           } 
                        }

 

© 著作权归作者所有

刺猬一号
粉丝 12
博文 373
码字总数 616361
作品 0
深圳
私信 提问
Java学习资料-Java常用算法-二叉树算法

二叉树算法的数据结构: 二叉树结点Node实现与c中的区别是,c中采用的是结构体,而java中是用类来实现,而在c++的教材中,类是一种自定义数据结构。 二叉树的leftchild和rightchild在c中是利...

晓阳
2015/01/28
707
0
LeetCode算法题-Minimum Distance Between BST Nodes(Java实现-四种解法)

这是悦乐书的第314次更新,第335篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第183题(顺位题号是783)。给定具有根节点值的二叉搜索树(BST),返回树中任何两个不同节点的...

小川94
04/23
0
0
LeetCode.897-递增搜索树(Increasing Order Search Tree)

这是悦乐书的第346次更新,第370篇原创 01 看题和准备 今天介绍的是LeetCode算法题中Easy级别的第211题(顺位题号是897)。给定一棵树,按中序遍历顺序重新排列树,以便树中最左边的节点现在...

小川94
06/07
0
0
【LeetCode】Symmetric Tree(对称二叉树)

这道题是LeetCode里的第101道题。是我在学数据结构——二叉树的时候碰见的题。 题目如下: 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 是对称的。 1/ 2 2/ / 3 4 4 3 但是下面这...

1000sakura
2018/11/24
0
0
算法知识梳理(11) - 二叉树相关算法第一部分

面试算法代码知识梳理系列 算法知识梳理(1) - 排序算法 算法知识梳理(2) - 字符串算法第一部分 算法知识梳理(3) - 字符串算法第二部分 算法知识梳理(4) - 数组第一部分 算法知识梳理(5) - 数...

泽毛
2017/12/19
0
2

没有更多内容

加载失败,请刷新页面

加载更多

rime设置为默认简体

转载 https://github.com/ModerRAS/ModerRAS.github.io/blob/master/_posts/2018-11-07-rime%E8%AE%BE%E7%BD%AE%E4%B8%BA%E9%BB%98%E8%AE%A4%E7%AE%80%E4%BD%93.md 写在开始 我的Arch Linux上......

zhenruyan
今天
4
0
简述TCP的流量控制与拥塞控制

1. TCP流量控制 流量控制就是让发送方的发送速率不要太快,要让接收方来的及接收。 原理是通过确认报文中窗口字段来控制发送方的发送速率,发送方的发送窗口大小不能超过接收方给出窗口大小。...

鏡花水月
今天
8
0
OSChina 周日乱弹 —— 别问,问就是没空

Osc乱弹歌单(2019)请戳(这里) 【今日歌曲】 @tom_tdhzz :#今日歌曲推荐# 分享容祖儿/彭羚的单曲《心淡》: 《心淡》- 容祖儿/彭羚 手机党少年们想听歌,请使劲儿戳(这里) @wqp0010 :周...

小小编辑
今天
891
11
golang微服务框架go-micro 入门笔记2.1 micro工具之micro api

micro api micro 功能非常强大,本文将详细阐述micro api 命令行的功能 重要的事情说3次 本文全部代码https://idea.techidea8.com/open/idea.shtml?id=6 本文全部代码https://idea.techidea8....

非正式解决方案
今天
5
0
Spring Context 你真的懂了吗

今天介绍一下大家常见的一个单词 context 应该怎么去理解,正确的理解它有助于我们学习 spring 以及计算机系统中的其他知识。 1. context 是什么 我们经常在编程中见到 context 这个单词,当...

Java知其所以然
昨天
6
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部