备案控制台
探索云世界
开发者社区 人工智能 文章 正文

二叉树递归遍历的多语言实现

2013-06-21 1068
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 一、理论知识 1、什么是二叉树遍历     二叉树的遍历：是指按一定的规律（顺着某一条搜索路径）访问二叉树中的所有结点，使得每个结点均被访问一次，而且仅被访问一次。

一、理论知识

1、什么是二叉树遍历

    二叉树的遍历：是指按一定的规律（顺着某一条搜索路径）访问二叉树中的所有结点，使得每个结点均被访问一次，而且仅被访问一次。

    访问的含义：可以是对结点的各种处理，如修改结点数据、输出结点数据等。

    实际上，二叉树的遍历也就是要把一个非线性结构的二叉树转化为一个线性结构。

    遍历是各种数据最基本的操作，许多其他的操作可以在遍历基础上实现。

 

2、二叉树的遍历方式

    二叉树的递归定义：二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的二叉树组成。

    可见二叉树有三部分组成：根结点D ，左子树L和右子树R。

由此，遍历二叉树的方案有6种：

    先左后右： DLR , LDR , LRD
    先右后左： DRL , RDL , RLD

约定先左后右，有三种遍历方法： DLR、LDR、LRD ，分别称为先序遍历、中序遍历、后序遍历。

 

2.1 二叉树的先序遍历算法

二叉树的先序遍历算法

若二叉树为空树，则空操作；否则，

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

例：先序遍历下图所示的二叉树。

image
图1

（1）访问根结点“-”

（2）先序遍历左子树：即按DLR的顺序遍历左子树

（3）先序遍历右子树：即按DLR的顺序遍历右子树

    先序遍历序列：-+a*b-cd/ef

先序遍历递归算法描述如下：

  1. void Preorder ( BinTree bt )
  2. {
  3.   if ( bt )
  4.   {
  5.     visit ( bt->data );
  6.     Preorder ( bt->lchild );
  7.     Preorder ( bt->rchild );
  8.   }
  9. }


2.2 二叉树的中序遍历算法

    若二叉树为空树，则空操作；否则，

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

例：中序遍历上图所示的二叉树。

（1）中序遍历左子树：即按LDR的顺序遍历左子树

（2）访问根结点“-”

（3）中序遍历右子树：即按LDR的顺序遍历右子树

中序遍历序列：a+b*c-d-e/f

中序遍历递归算法描述如下：

  1. void Inorder ( BinTree bt )
  2. {
  3.   if ( bt )
  4.   {
  5.     Inorder ( bt->lchild );
  6.     visit ( bt->data );
  7.     Inorder ( bt->rchild );
  8.   }
  9. }


2.3 二叉树的后序遍历算法

    若二叉树为空树，则空操作；否则，

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

例：后序遍历上图所示的二叉树。

（1）后序遍历左子树：即按LRD的顺序遍历左子树

（2）后序遍历右子树：即按LRD的顺序遍历右子树

（3）访问根结点“-”

    后序遍历序列：abcd-*+ef/-

后序遍历递归算法描述如下：

   

  1. void Postorder ( BinTree bt )
  2. {
  3.   if ( bt )
  4.   {
  5.     Postorder ( bt->lchild );
  6.     Postorder ( bt->rchild );
  7.     visit ( bt->data );
  8.   }
  9. }

 
二叉树的三种遍历算法小结


    三种遍历算法不同之处仅在于访问根结点、遍历左子树、遍历右子树的先后关系。若不考虑visit()语句，则三种遍历方法完全相同（访问路径是相同的，只是访问结点的时机不同）。

    三种遍历算法均是递归算法：

    （1）树的定义本身就是递归的；

    （2）递归和栈密切联系：递归过程实际就是对栈的操作过程；

    （3）可以直接通过对栈的操作，来把递归算法写为非递归算法。

 

二、程序设计

C语言实现二叉树的遍历
  1. // BitTreeForCPP.cpp : 定义控制台应用程序的入口点。
  2. //

  4. #include "stdafx.h"

  6. typedef struct SBitTreeNode
  7. {
  8.     int Data;
  9.     SBitTreeNode *LNode;
  10.     SBitTreeNode *RNode;
  11.     SBitTreeNode *PNode;
  12. }SBitTreeNode,*SBTNode;

  14. static void SetTree(SBTNode treeNode,int data,SBTNode lNode,SBTNode rNode,SBTNode pNode)
  15. {
  16.     treeNode->Data = data;
  17.     treeNode->LNode = lNode;
  18.     treeNode->RNode = rNode;
  19.     treeNode->PNode = pNode;
  20. }

  22. static void PreorderTraversal(SBTNode treeNode)
  23. {
  24.     if(treeNode != NULL)
  25.     {
  26.         printf("%d",treeNode->Data);
  27.         PreorderTraversal(treeNode->LNode);
  28.         PreorderTraversal(treeNode->RNode);
  29.     }
  30.     else
  31.         return;
  32. }

  34. static void InorderTraversal(SBTNode treeNode)
  35. {
  36.     if(treeNode != NULL)
  37.     {
  38.         InorderTraversal(treeNode->LNode);
  39.         printf("%d",treeNode->Data);
  40.         InorderTraversal(treeNode->RNode);
  41.     }
  42.     else
  43.         return;
  44. }

  46. static void PostorderTraversal(SBTNode treeNode)
  47. {
  48.     if(treeNode != NULL)
  49.     {
  50.         PostorderTraversal(treeNode->LNode);
  51.         PostorderTraversal(treeNode->RNode);
  52.         printf("%d",treeNode->Data);
  53.     }
  54.     else
  55.         return;
  56. }

  58. int _tmain(int argc, _TCHAR* argv[])
  59. {
  60.     SBitTreeNode node1;
  61.     SBitTreeNode node2;
  62.     SBitTreeNode node3;
  63.     SBitTreeNode node4;

  65.     SBitTreeNode node5;
  66.     SBitTreeNode node6;
  67.     SBitTreeNode node7;

  69.     SetTree(&node1,1,&node2,&node3,NULL);
  70.     SetTree(&node2,2,&node4,&node5,&node1);
  71.     SetTree(&node3,3,NULL,&node6,&node1);
  72.     SetTree(&node4,4,NULL,NULL,&node2);

  74.     SetTree(&node5,5,NULL,NULL,&node2);
  75.     SetTree(&node6,6,NULL,&node7,&node3);
  76.     SetTree(&node7,7,NULL,NULL,&node6);

  78.     printf("--------------------- PreorderTraversal ---------------------\n");
  79.     PreorderTraversal(&node1);
  80.     printf("\n--------------------- InorderTraversal ---------------------\n");
  81.     InorderTraversal(&node1);
  82.     printf("\n--------------------- PostorderTraversal ---------------------\n");
  83.     PostorderTraversal(&node1);

  85.     getchar();
  86.     return 0;
  87. }

image
图2

 

C#实现二叉树的遍历


  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;


  7. namespace CBitTreeProject
  8. {
  9.     class Program
  10.     {
  11.         public class CTreeNodeT>
  12.         {
  13.             public CTreeNodeT> LNode
  14.             {
  15.                 set;
  16.                 get;
  17.             }

  19.             public CTreeNodeT> RNode
  20.             {
  21.                 set;
  22.                 get;
  23.             }

  25.             public CTreeNodeT> PNode
  26.             {
  27.                 set;
  28.                 get;
  29.             }

  31.             public T Data
  32.             {
  33.                 set;
  34.                 get;
  35.             }

  37.             public CTreeNode(T data)
  38.             {
  39.                 this.Data = data;
  40.             }
  41.         };


  44.         static void Main(string[] args)
  45.         {
  46.             CTreeNodeint> node1 = new CTreeNodeint>(1);
  47.             CTreeNodeint> node2 = new CTreeNodeint>(2);
  48.             CTreeNodeint> node3 = new CTreeNodeint>(3);
  49.             
  50.             CTreeNodeint> node4 = new CTreeNodeint>(4);
  51.             CTreeNodeint> node5 = new CTreeNodeint>(5);
  52.             CTreeNodeint> node6 = new CTreeNodeint>(6);
  53.             CTreeNodeint> node7 = new CTreeNodeint>(7);

  55.             SetTree(ref node1, node2, node3, null);
  56.             SetTree(ref node2, node4, node5, node1);
  57.             SetTree(ref node3, null, node6, node1);
  58.             SetTree(ref node6, null, node7, node6);

  60.             Console.WriteLine("--------------------------------- Preorder traversal ----------------------------------------\n");
  61.             PreorderTraversal(node1);
  62.             Console.WriteLine("--------------------------------- Inorder traversal ----------------------------------------\n");
  63.             InorderTraversal(node1);
  64.             Console.WriteLine("--------------------------------- Postorder traversal ----------------------------------------\n");
  65.             PostorderTraversal(node1);

  67.             Console.ReadLine();
  68.         }

  70.         /** *************************************************************************************************
  71.          * DESC :
  72.          * ARGC :
  73.          * RET : success, true; fail, false.
  74.          *---------------------------------------------------------------------------------------------------
  75.         ****************************************************************************************************/
  76.         public static void SetTree(ref CTreeNodeint> treeNode,CTreeNodeint> lNode,CTreeNodeint> rNode,CTreeNodeint> pNode)
  77.         {
  78.             treeNode.LNode = lNode;
  79.             treeNode.RNode = rNode;
  80.             treeNode.PNode = pNode;
  81.         }

  83.         public static void PreorderTraversal(CTreeNodeint> treeNode)
  84.         {
  85.             if (treeNode != null)
  86.             {
  87.                 Console.WriteLine(treeNode.Data);
  88.                 PreorderTraversal(treeNode.LNode);
  89.                 PreorderTraversal(treeNode.RNode);
  90.             }
  91.             else
  92.                 return;
  93.         }

  95.         public static void InorderTraversal(CTreeNodeint> treeNode)
  96.         {
  97.             if (treeNode != null)
  98.             {
  99.                 InorderTraversal(treeNode.LNode);
  100.                 Console.WriteLine(treeNode.Data);
  101.                 InorderTraversal(treeNode.RNode);
  102.             }
  103.             else
  104.                 return;
  105.         }

  107.         public static void PostorderTraversal(CTreeNodeint> treeNode)
  108.         {
  109.             if (treeNode != null)
  110.             {
  111.                 PostorderTraversal(treeNode.LNode);
  112.                 PostorderTraversal(treeNode.RNode);
  113.                 Console.WriteLine(treeNode.Data);
  114.             }
  115.             else
  116.                 return;
  117.         }
  118.     }
  119. }



image 
图3


参考博客1：
http://www.lmwlove.com/ac/ID958

参考博客2：

http://www.91computer.com/datastruct/index.asp

 


文章标签：
算法
自然语言处理
C语言
C#
长空翱翔
目录
相关文章
狗哥不是甜妹
|
6月前
|
人工智能 Java 测试技术
二叉树通过前序中序来构建二叉树(炒鸡详细到每一步）
二叉树通过前序中序来构建二叉树(炒鸡详细到每一步）
狗哥不是甜妹
23 0
鸽芷咕
|
3月前
|
算法
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
递归算法：二叉树前序、中序、后序遍历解析与递归思想深度剖析
鸽芷咕
41 0
天玑y
|
3月前
|
算法
平衡二叉树的构建（递归
平衡二叉树的构建（递归
天玑y
42 0
BookSea
|
8月前
|
Java
java实现树的前序遍历，递归和非递归实现（简单明了）
java实现树的前序遍历，递归和非递归实现（简单明了）
BookSea
70 0
ZhangBlossom
|
9月前
中序线索二叉树的实现(源代码以及讲解)
中序线索二叉树的实现(源代码以及讲解)
ZhangBlossom
88 0
_BugMan
|
10月前
|
存储 机器学习/深度学习 Java
数据结构(4)树形结构——二叉树（概述、前序、中序、后序、层序遍历JAVA实现）
4.1.树 树，由n(n≥0)个有限节点和边组成一个具有层次关系的数据结构。树需要满足以下条件： 任何结点的子节点不相交。 任何子结点只有一个父节点。 N个结点，N-1条边。 对于一个非空树（结点数≥0），具有以下性质： 起始结点称为“根” 除根结点外可分为m个互不相交的有限集合，其中每个集合本身也是一棵树，称为原来这棵树的“子树”。
_BugMan
108 0
Parallel
|
11月前
【数据结构入门】二叉树的遍历（前序、中序、后序、层序）
【数据结构入门】二叉树的遍历（前序、中序、后序、层序）
Parallel
682 0
Lucky小黄人^_^
二叉树的三种非递归遍历方式
二叉树的三种非递归遍历方式
Lucky小黄人^_^
177 0
前端歌谣
|
前端开发
前端知识案例-二叉树的遍历(前序 中序 后序)
前端知识案例-二叉树的遍历(前序 中序 后序)
前端歌谣
53 0
前端知识案例-二叉树的遍历(前序 中序 后序)
壹佰、
|
C++
由前序遍历和中序遍历构建二叉树（C++语言）
由前序遍历和中序遍历构建二叉树（C++语言）
壹佰、
100 0

热门文章

最新文章

  • 1
    理解事务的4种隔离级别
  • 2
    疑犯追踪第一季/全集Person Of Interest迅雷下载
  • 3
    简单实用的数据建模工具PDManer
  • 4
    详细讲解！Canal+Kafka实现MySQL与Redis数据同步！
  • 5
    71.7. Script for automatic startup on boot
  • 6
    关于Oracle客户端显示乱码问题
  • 7
    PHPWAMP站点管理的“域名模式”和“端口模式”详解、均支持自定义
  • 8
    jsHelper
  • 9
    学校里学不到的东西(一)
  • 10
    Python 3 教程一:入门
  • 1
    Python的装饰器
    33
  • 2
    R语言用潜类别混合效应模型(Latent Class Mixed Model ,LCMM)分析老年痴呆年龄数据
    20
  • 3
    数据分享|R语言用logistic逻辑回归和AFRIMA、ARIMA时间序列模型预测世界人口
    16
  • 4
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（下）
    20
  • 5
    【视频】马尔可夫链蒙特卡罗方法MCMC原理与R语言实现|数据分享（上）
    27
  • 6
    数据分享|数据探索电商平台用户行为流失可视化分析
    29
  • 7
    电商平台数据可视化分析网红零食销量
    18
  • 8
    R语言线性回归模型拟合诊断异常值分析家庭燃气消耗量和卡路里实例带自测题
    16
  • 9
    数据分享|R语言GLM广义线性模型：逻辑回归、泊松回归拟合小鼠临床试验数据（剂量和反应）示例和自测题
    12
  • 10
    数据分享|R语言逻辑回归、线性判别分析LDA、GAM、MARS、KNN、QDA、决策树、随机森林、SVM分类葡萄酒交叉验证ROC（下）
    17

    • 相关电子书

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