二叉树递归遍历的多语言实现-阿里云开发者社区

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

2013-06-21 1135

版权

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

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

一、理论知识

1、什么是二叉树遍历

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

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

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

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

2、二叉树的遍历方式

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

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

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

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

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

2.1 二叉树的先序遍历算法

二叉树的先序遍历算法

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

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

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

图1

（1）访问根结点“-”

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

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

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

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

void Preorder ( BinTree bt )
{
if ( bt )
{
visit ( bt->data );
Preorder ( bt->lchild );
Preorder ( bt->rchild );
}
}

2.2 二叉树的中序遍历算法

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

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

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

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

（2）访问根结点“-”

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

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

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

void Inorder ( BinTree bt )
{
if ( bt )
{
Inorder ( bt->lchild );
visit ( bt->data );
Inorder ( bt->rchild );
}
}

2.3 二叉树的后序遍历算法

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

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

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

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

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

（3）访问根结点“-”

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

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

void Postorder ( BinTree bt )
{
if ( bt )
{
Postorder ( bt->lchild );
Postorder ( bt->rchild );
visit ( bt->data );
}
}

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

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

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

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

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

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

二、程序设计

C语言实现二叉树的遍历

// BitTreeForCPP.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
typedef struct SBitTreeNode
{
int Data;
SBitTreeNode *LNode;
SBitTreeNode *RNode;
SBitTreeNode *PNode;
}SBitTreeNode,*SBTNode;
static void SetTree(SBTNode treeNode,int data,SBTNode lNode,SBTNode rNode,SBTNode pNode)
{
treeNode->Data = data;
treeNode->LNode = lNode;
treeNode->RNode = rNode;
treeNode->PNode = pNode;
}
static void PreorderTraversal(SBTNode treeNode)
{
if(treeNode != NULL)
{
printf("%d",treeNode->Data);
PreorderTraversal(treeNode->LNode);
PreorderTraversal(treeNode->RNode);
}
else
return;
}
static void InorderTraversal(SBTNode treeNode)
{
if(treeNode != NULL)
{
InorderTraversal(treeNode->LNode);
printf("%d",treeNode->Data);
InorderTraversal(treeNode->RNode);
}
else
return;
}
static void PostorderTraversal(SBTNode treeNode)
{
if(treeNode != NULL)
{
PostorderTraversal(treeNode->LNode);
PostorderTraversal(treeNode->RNode);
printf("%d",treeNode->Data);
}
else
return;
}
int _tmain(int argc, _TCHAR* argv[])
{
SBitTreeNode node1;
SBitTreeNode node2;
SBitTreeNode node3;
SBitTreeNode node4;
SBitTreeNode node5;
SBitTreeNode node6;
SBitTreeNode node7;
SetTree(&node1,1,&node2,&node3,NULL);
SetTree(&node2,2,&node4,&node5,&node1);
SetTree(&node3,3,NULL,&node6,&node1);
SetTree(&node4,4,NULL,NULL,&node2);
SetTree(&node5,5,NULL,NULL,&node2);
SetTree(&node6,6,NULL,&node7,&node3);
SetTree(&node7,7,NULL,NULL,&node6);
printf("--------------------- PreorderTraversal ---------------------\n");
PreorderTraversal(&node1);
printf("\n--------------------- InorderTraversal ---------------------\n");
InorderTraversal(&node1);
printf("\n--------------------- PostorderTraversal ---------------------\n");
PostorderTraversal(&node1);
getchar();
return 0;
}

图2

C#实现二叉树的遍历

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace CBitTreeProject
{
class Program
{
public class CTreeNodeT>
{
public CTreeNodeT> LNode
{
set;
get;
}
public CTreeNodeT> RNode
{
set;
get;
}
public CTreeNodeT> PNode
{
set;
get;
}
public T Data
{
set;
get;
}
public CTreeNode(T data)
{
this.Data = data;
}
};
static void Main(string[] args)
{
CTreeNodeint> node1 = new CTreeNodeint>(1);
CTreeNodeint> node2 = new CTreeNodeint>(2);
CTreeNodeint> node3 = new CTreeNodeint>(3);
CTreeNodeint> node4 = new CTreeNodeint>(4);
CTreeNodeint> node5 = new CTreeNodeint>(5);
CTreeNodeint> node6 = new CTreeNodeint>(6);
CTreeNodeint> node7 = new CTreeNodeint>(7);
SetTree(ref node1, node2, node3, null);
SetTree(ref node2, node4, node5, node1);
SetTree(ref node3, null, node6, node1);
SetTree(ref node6, null, node7, node6);
Console.WriteLine("--------------------------------- Preorder traversal ----------------------------------------\n");
PreorderTraversal(node1);
Console.WriteLine("--------------------------------- Inorder traversal ----------------------------------------\n");
InorderTraversal(node1);
Console.WriteLine("--------------------------------- Postorder traversal ----------------------------------------\n");
PostorderTraversal(node1);
Console.ReadLine();
}
/** *************************************************************************************************
* DESC :
* ARGC :
* RET : success, true; fail, false.
*---------------------------------------------------------------------------------------------------
****************************************************************************************************/
public static void SetTree(ref CTreeNodeint> treeNode,CTreeNodeint> lNode,CTreeNodeint> rNode,CTreeNodeint> pNode)
{
treeNode.LNode = lNode;
treeNode.RNode = rNode;
treeNode.PNode = pNode;
}
public static void PreorderTraversal(CTreeNodeint> treeNode)
{
if (treeNode != null)
{
Console.WriteLine(treeNode.Data);
PreorderTraversal(treeNode.LNode);
PreorderTraversal(treeNode.RNode);
}
else
return;
}
public static void InorderTraversal(CTreeNodeint> treeNode)
{
if (treeNode != null)
{
InorderTraversal(treeNode.LNode);
Console.WriteLine(treeNode.Data);
InorderTraversal(treeNode.RNode);
}
else
return;
}
public static void PostorderTraversal(CTreeNodeint> treeNode)
{
if (treeNode != null)
{
PostorderTraversal(treeNode.LNode);
PostorderTraversal(treeNode.RNode);
Console.WriteLine(treeNode.Data);
}
else
return;
}
}
}