开发者社区> 长空翱翔> 正文
阿里云
为了无法计算的价值
打开APP
阿里云APP内打开

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

简介: 一、理论知识 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. //

  3. #include "stdafx.h"

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

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

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

  29. static void InorderTraversal(SBTNode treeNode)
  30. {
  31.     if(treeNode != NULL)
  32.     {
  33.         InorderTraversal(treeNode->LNode);
  34.         printf("%d",treeNode->Data);
  35.         InorderTraversal(treeNode->RNode);
  36.     }
  37.     else
  38.         return;
  39. }

  40. static void PostorderTraversal(SBTNode treeNode)
  41. {
  42.     if(treeNode != NULL)
  43.     {
  44.         PostorderTraversal(treeNode->LNode);
  45.         PostorderTraversal(treeNode->RNode);
  46.         printf("%d",treeNode->Data);
  47.     }
  48.     else
  49.         return;
  50. }

  51. int _tmain(int argc, _TCHAR* argv[])
  52. {
  53.     SBitTreeNode node1;
  54.     SBitTreeNode node2;
  55.     SBitTreeNode node3;
  56.     SBitTreeNode node4;

  57.     SBitTreeNode node5;
  58.     SBitTreeNode node6;
  59.     SBitTreeNode node7;

  60.     SetTree(&node1,1,&node2,&node3,NULL);
  61.     SetTree(&node2,2,&node4,&node5,&node1);
  62.     SetTree(&node3,3,NULL,&node6,&node1);
  63.     SetTree(&node4,4,NULL,NULL,&node2);

  64.     SetTree(&node5,5,NULL,NULL,&node2);
  65.     SetTree(&node6,6,NULL,&node7,&node3);
  66.     SetTree(&node7,7,NULL,NULL,&node6);

  67.     printf("--------------------- PreorderTraversal ---------------------\n");
  68.     PreorderTraversal(&node1);
  69.     printf("\n--------------------- InorderTraversal ---------------------\n");
  70.     InorderTraversal(&node1);
  71.     printf("\n--------------------- PostorderTraversal ---------------------\n");
  72.     PostorderTraversal(&node1);

  73.     getchar();
  74.     return 0;
  75. }

image
图2

 

C#实现二叉树的遍历


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


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

  16.             public CTreeNodeT> RNode
  17.             {
  18.                 set;
  19.                 get;
  20.             }

  21.             public CTreeNodeT> PNode
  22.             {
  23.                 set;
  24.                 get;
  25.             }

  26.             public T Data
  27.             {
  28.                 set;
  29.                 get;
  30.             }

  31.             public CTreeNode(T data)
  32.             {
  33.                 this.Data = data;
  34.             }
  35.         };


  36.         static void Main(string[] args)
  37.         {
  38.             CTreeNodeint> node1 = new CTreeNodeint>(1);
  39.             CTreeNodeint> node2 = new CTreeNodeint>(2);
  40.             CTreeNodeint> node3 = new CTreeNodeint>(3);
  41.             
  42.             CTreeNodeint> node4 = new CTreeNodeint>(4);
  43.             CTreeNodeint> node5 = new CTreeNodeint>(5);
  44.             CTreeNodeint> node6 = new CTreeNodeint>(6);
  45.             CTreeNodeint> node7 = new CTreeNodeint>(7);

  46.             SetTree(ref node1, node2, node3, null);
  47.             SetTree(ref node2, node4, node5, node1);
  48.             SetTree(ref node3, null, node6, node1);
  49.             SetTree(ref node6, null, node7, node6);

  50.             Console.WriteLine("--------------------------------- Preorder traversal ----------------------------------------\n");
  51.             PreorderTraversal(node1);
  52.             Console.WriteLine("--------------------------------- Inorder traversal ----------------------------------------\n");
  53.             InorderTraversal(node1);
  54.             Console.WriteLine("--------------------------------- Postorder traversal ----------------------------------------\n");
  55.             PostorderTraversal(node1);

  56.             Console.ReadLine();
  57.         }

  58.         /** *************************************************************************************************
  59.          * DESC :
  60.          * ARGC :
  61.          * RET : success, true; fail, false.
  62.          *---------------------------------------------------------------------------------------------------
  63.         ****************************************************************************************************/
  64.         public static void SetTree(ref CTreeNodeint> treeNode,CTreeNodeint> lNode,CTreeNodeint> rNode,CTreeNodeint> pNode)
  65.         {
  66.             treeNode.LNode = lNode;
  67.             treeNode.RNode = rNode;
  68.             treeNode.PNode = pNode;
  69.         }

  70.         public static void PreorderTraversal(CTreeNodeint> treeNode)
  71.         {
  72.             if (treeNode != null)
  73.             {
  74.                 Console.WriteLine(treeNode.Data);
  75.                 PreorderTraversal(treeNode.LNode);
  76.                 PreorderTraversal(treeNode.RNode);
  77.             }
  78.             else
  79.                 return;
  80.         }

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

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



image 
图3


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

参考博客2:

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

 


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
树和二叉树的特点与异同
树和二叉树的特点与异同
0 0
03、leetcode【二叉树—简单】 二叉树的统一迭代法
03、leetcode【二叉树—简单】 二叉树的统一迭代法
0 0
【笔记14】树的基本概念,二叉树,真二叉树,满二叉树,完全二叉树
节点、根节点、父节点、子节点、兄弟节点 空树:没有任何节点的树 一棵树可以只有 1 个节点(即只有根节点) 子树、左子树、右子树
0 0
C++实现树 - 04 二叉树的构建(数组)
通过前面两讲的学习,大家可能对二叉树有了比较深的感悟,但可能会发现一个小问题,我们在构建二叉树的时候都是一个个插入的,非常的不方便。那么这节课我们就来看看,如何通过输入一个数组来快速构建起一个二叉树。这里会介绍通过顺序数组、前序数组和后序数组如何构建二叉树。
0 0
二叉树,前序,中序,后序遍历——非递归形式 模板总结
二叉树,前序,中序,后序遍历——非递归形式 模板总结
0 0
二叉树的递归套路——最大二叉搜索子树头结点
二叉树的递归套路——最大二叉搜索子树头结点
0 0
数据结构实践项目——树和二叉树(1)
本文针对[数据结构基础系列(6):树和二叉树]第1-6, 8-10课时 1 树结构导学 2 树的基本概念 3 树的基本术语 4 树的性质 5 树的存储结构 6 二叉树概念和性质 8 二叉树的存储结构 9 二叉树的基本运算及其实现 10 二叉树的遍历 【项目1 - 二叉树算法库】   定义二叉树的链式存储结构,实现其基本运算,并完成测试。 要求:
1457 0
树、二叉树基础
刚看到堆排序,顺便记录一下关于树的一些基本概念: 前言 前面介绍的栈、队列都是线性结构(linear structure)。而树是非线性结构(non-linear structure)。因此,树中的元素之间一般不存在类似于线性结构的一对一的关系,更多地表现为多对多的关系。
582 0
+关注
长空翱翔
长期从事Windows和linux应用程序开发,系统开发,驱动程序开发以及基于.net平台的软件开发;擅长面向对象程序设计、数据库设计、应用与开发;
文章
问答
文章排行榜
最热
最新
相关电子书
更多
低代码开发师(初级)实战教程
立即下载
阿里巴巴DevOps 最佳实践手册
立即下载
冬季实战营第三期:MySQL数据库进阶实战
立即下载