Chinaunix首页 | 论坛 | 博客
  • 博客访问: 9469325
  • 博文数量: 1293
  • 博客积分: 13501
  • 博客等级: 上将
  • 技术积分: 17974
  • 用 户 组: 普通用户
  • 注册时间: 2011-03-08 18:11
文章分类

全部博文(1293)

文章存档

2019年(1)

2018年(1)

2016年(118)

2015年(257)

2014年(128)

2013年(222)

2012年(229)

2011年(337)

分类: 架构设计与优化

2013-06-21 16:36:46

一、理论知识

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 CTreeNode<T>
  10.         {
  11.             public CTreeNode<T> LNode
  12.             {
  13.                 set;
  14.                 get;
  15.             }

  16.             public CTreeNode<T> RNode
  17.             {
  18.                 set;
  19.                 get;
  20.             }

  21.             public CTreeNode<T> 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.             CTreeNode<int> node1 = new CTreeNode<int>(1);
  39.             CTreeNode<int> node2 = new CTreeNode<int>(2);
  40.             CTreeNode<int> node3 = new CTreeNode<int>(3);
  41.             
  42.             CTreeNode<int> node4 = new CTreeNode<int>(4);
  43.             CTreeNode<int> node5 = new CTreeNode<int>(5);
  44.             CTreeNode<int> node6 = new CTreeNode<int>(6);
  45.             CTreeNode<int> node7 = new CTreeNode<int>(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 CTreeNode<int> treeNode,CTreeNode<int> lNode,CTreeNode<int> rNode,CTreeNode<int> pNode)
  65.         {
  66.             treeNode.LNode = lNode;
  67.             treeNode.RNode = rNode;
  68.             treeNode.PNode = pNode;
  69.         }

  70.         public static void PreorderTraversal(CTreeNode<int> 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(CTreeNode<int> 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(CTreeNode<int> 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

 


阅读(2375) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~