<% dim ModuleName,InfoID,ChannelShortName,CorrelativeArticle,InstallDir,ChannelDir,Keyword,PageTitle,ArticleIntro,Articlecontent Keyword=stripHTML("数据结构,二叉树,遍历,C语言,类") PageTitle=stripHTML("数据结构-二叉树的遍历(类C语言描述)") ArticleIntro=stripHTML("") Articlecontent=stripHTML("遍历概念   所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。  遍历是二…") ModuleName = stripHTML("programme") InfoID = stripHTML("194995") ChannelShortName=stripHTML("编程") InstallDir=stripHTML("http://www.77169.com/") ChannelDir=stripHTML("programme") %> 数据结构-二叉树的遍历(类C语言描述) - 华盟网 - http://www.77169.com
您现在的位置: 华盟网 >> 编程 >> C语言 >> 正文

数据结构-二叉树的遍历(类C语言描述)

2015/3/17 作者:admin 来源: 网络收集
导读 <% if len(ArticleIntro)<3 then Response.Write Articlecontent 'Response.Write "Articlecontent" else Response.Write ArticleIntro 'Response.Write "ArticleIntro" end if %>
遍历概念

  所谓遍历(Traversal)是指沿着某条搜索路线,依次对树中每个结点均做一次且仅做一次访问。访问结点所做的操作依赖于具体的应用问题。

  遍历是二叉树上最重要的运算之一,是二叉树上进行其它运算之基础。

  遍历方案

  1.遍历方案

  从二叉树的递归定义可知,一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此,在任一给定结点上,可以按某种次序执行三个操作:

  (1)访问结点本身(N),

  (2)遍历该结点的左子树(L),

  (3)遍历该结点的右子树(R)。

  以上三种操作有六种执行次序:

  NLR、LNR、LRN、NRL、RNL、RLN.

  注意:

  前三种次序与后三种次序对称,故只讨论先左后右的前三种次序。

  2.三种遍历的命名

  根据访问结点操作发生位置命名:

  ① NLR:前序遍历(PreorderTraversal亦称(先序遍历))

  --访问结点的操作发生在遍历其左右子树之前。

  ② LNR:中序遍历(InorderTraversal)

  --访问结点的操作发生在遍历其左右子树之中(间)。

  ③ LRN:后序遍历(PostorderTraversal)

  --访问结点的操作发生在遍历其左右子树之后。

  注意:

  由于被访问的结点必是某子树的根,所以N(Node)、L(Left subtlee)和R(Right subtree)又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。

  遍历算法

  1.中序遍历的递归算法定义:

  若二叉树非空,则依次执行如下操作:

  (1)遍历左子树;

  (2)访问根结点;

  (3)遍历右子树。

  2.先序遍历的递归算法定义:

  若二叉树非空,则依次执行如下操作:

  (1) 访问根结点;

  (2) 遍历左子树;

  (3) 遍历右子树。

  3.后序遍历得递归算法定义:

  若二叉树非空,则依次执行如下操作:

  (1)遍历左子树;

  (2)遍历右子树;

  (3)访问根结点。

  4.中序遍历的算法实现

  用二叉链表做为存储结构,中序遍历算法可描述为:

  void InOrder(BinTree T)

  { //算法里①~⑥是为了说明执行过程加入的标号

  ① if(T) { // 如果二叉树非空

  ② InOrder(T->lchild);

  ③ printf("%c",T->data); // 访问结点

  ④ InOrder(T->rchild);

  ⑤ }

  ⑥ } // InOrder



  • 上一篇编程:

  • 下一篇编程: