`
yuanzher
  • 浏览: 30930 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

【转】二叉树及二叉树的遍历

 
阅读更多

二叉树(binary tree)

二叉树的定义

  二叉树的定义:树的度为2的树。

  二叉树的递归定义:二叉树或者是一棵空树,或者是一棵由一个根结点和两棵互不相交的左子树和右子树所组成的非空树,而左右子树又都是一棵二叉树。

二叉树的性质

  1.第i层上至多有2的i-1次方个结点。

  2.深度为h的二叉树至多有2的h次方减1个结点。

  3.每一层都满的二叉树称为满二叉树,只在最后一层右边缺若干个结点的树称为完全二叉树

  (对结点的编号通常都是从满二叉树的树根开始,从上到下从左到右编号)。

  完全二叉树的重要性质:

  根结点序号为i=1的情况下:

  1.编号为i的结点,左孩子编号为2i,右孩子编号为2i+1.

  2.除根结点外,编号为i的结点,其父结点的标号为i/2向下取整。

二叉树的存储结构

  同线性表一样,二叉树有顺序和链接两种存储结构。

1.顺序存储结构

  顺序存储一棵二叉树,首先对该树中每个结点进行编号,然后以各个结点的编号为下标,把各结点的值对应存储到一个一维数组中。

  每个结点的编号与等深度的满二叉树中对应的结点编号相同,即树根编号为1,然后从上到下从左到右编号,i结点的左右孩子为2i和2i+1.

  缺点:对于单支结点较多的二叉树来说很多存储位置空闲。

2.链接存储结构

  链接存储中通常采用的方法是,在每个结点中设置三个域:值域(用来存储对应的数据元素),左指针域和右指针域。

  另一种方法是,在如上的结构中再增加一个parent指针域(便于查找父结点)。

  不带双亲指针的链接存储结构称作二叉链表,既可以由独立分配的结点链接而成,也可以由数组中的元素结点链接而成。

  独立结点的类型可以这样定义:

struct BTreeNode{
    ElemType data;
    BTreeNode* left;
    BTreeNode* right;
};

 

  数组元素结点可以定义为

struct ABTreeNode{
    ElemType data;
    int left,right;
};

  第二种形式中left和right域分别存储左右孩子结点所在单元的下标,所以被定义为整型。

  在数组中建立二叉树的好处是,建立好后可以把整个数组写入到文件中保存起来,需要时再从文件中读入到数组中。

二叉树遍历

  设二叉树由BTreeNode类型的、通过动态分配产生的独立结点链接而成,并设BT为指向根结点的指针。

  前序遍历

复制代码
void PreOrder(BTreeNode* BT)
{
    if(BT != NULL)
    {
        cout<<BT->data<<' ';  //访问根结点,操作视应用而定
          PreOrder(BT->left);
        PreOrder(BT->right);
    }
}
复制代码

 

  中序遍历

复制代码
void InOrder(BTreeNode* BT)
{
    if(BT != NULL)
    {
        InOrder (BT->left);
        cout<<BT->data<<' ';
        InOrder (BT->right);
    }
}
复制代码

 

  后序遍历

复制代码
void PostOrder(BTreeNode* BT)
{
    if(BT != NULL)
    {
        PostOrder (BT->left);
        PostOrder (BT->right);
        cout<<BT->data<<' ';
    }
}
复制代码

 

  按层遍历

  可以按照二叉树的层次结构进行遍历,即按照从上到下从左到右的次序访问各个结点。

  按层遍历算法需要使用一个队列,开始时把整个树的根结点入队,然后每从队列中删除一个结点并输出该结点的值时,都把它的非空的左右孩子结点入队,这样当队列空时算法结束。

复制代码
//按层遍历
void LevelOrder(BTreeNode* BT)
{
    const int MaxSize = 30; //定义用于存储队列的数组长度
    //在这个算法中,队列的最大长度不会超过二叉树中一层上的最大结点数
    BTreeNode* q[MaxSize];  //定义队列所使用的数组空间
    int front=0, rear=0;    //定义队首指针和队尾指针,初始为空队
    BTreeNode* p;

    if(BT != NULL) //将树根指针进队
    {
        rear = (rear +1) % MaxSize;
        q[rear] = BT;
    }

    while(front!=rear)  //当队列非空时执行循环
    {
        front=(front + 1) % MaxSize;  //使队首指针指向队首元素
        p = q[front];                  //操作并删除队首元素
        cout<<p->data<<' ';
        if(p->left !=NULL)        //若存在左孩子,则该结点指针进队
        {
            rear = (rear +1) % MaxSize;
            q[rear] = p->left;        
        }
        if(p->right !=NULL)        //若存在右孩子,则该结点指针进队
        {
            rear = (rear +1) % MaxSize;
            q[rear] = p->right;        
        }
    }//while end

}
复制代码

 

 

分享到:
评论

相关推荐

    【C语言二叉树遍历实例】C语言二叉树遍历实例

    二叉树的遍历C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历实例C语言二叉树遍历...

    二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历.txt

    二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历

    易语言二叉树遍历

    二叉树遍历是理解数据结构和算法的基础,它包括前序遍历、中序遍历和后序遍历三种主要方法。 1. **二叉树的基本概念**: - 二叉树是一种特殊的树结构,每个节点最多有两个子节点,通常称为左子节点和右子节点。 -...

    二叉树遍历 二叉树遍历

    二叉树遍历 二叉树遍历

    二叉树遍历及其应用

    ### 二叉树遍历及其应用 #### 一、引言 在计算机科学领域,《数据结构》是一门极为重要的基础课程。它不仅涵盖了各种数据结构的设计与实现,还涉及到了算法的设计与分析。其中,二叉树作为一种常用的数据结构,在...

    二叉树遍历问题-前序, 中序, 后序

    二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...

    二叉树的遍历实验报告.pdf

    1. 二叉树遍历的概念与目的: 遍历二叉树是为了访问树中的所有节点,按照特定的顺序执行操作,如查找、插入或删除节点。在二叉树的应用中,遍历常用于解决问题,如查找特定属性的节点,或者对所有节点进行统一处理。...

    层次遍历二叉树

    层次遍历二叉树

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

    ### 二叉树遍历的特点(数据结构) 在计算机科学领域,数据结构是研究的核心之一。其中,二叉树作为一种重要的非线性数据结构,在实际应用中极为广泛,包括搜索算法、排序算法等方面都有其身影。本文将详细介绍...

    树和二叉树-层序遍历二叉树 

    树和二叉树-层序遍历二叉树 在计算机科学中,树和二叉树是很重要的数据结构概念。我们可以使用链表来存储二叉树,并使用层序遍历算法来遍历它。层序遍历二叉树的算法可以分为三步:首先,建立二叉树的链表存储结构...

    按层次遍历二叉树的算法

    按层次遍历二叉树的算法是二叉树遍历的一种重要方法。该算法的时间复杂度为O(n),空间复杂度为O(m),非常适合实际应用。在树形结构中,按层次遍历二叉树的算法可以快速地遍历、搜索、插入、删除等操作。

    数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx

    "数据结构树和二叉树遍历二叉树和线索二叉树PPT学习教案.pptx" 本资源主要讲述了数据结构树和二叉树遍历的相关知识点,包括二叉树的基本概念、二叉树遍历的六种方案、先序、中序、后序遍历算法的实现、线索二叉树的...

    二叉树各种遍历算法的C++实现

    在这个主题中,我们将深入探讨二叉树的三种主要遍历方法:前序遍历、中序遍历和后序遍历,以及它们在C++中的实现方式。 1. **前序遍历**:前序遍历的顺序是根节点 -&gt; 左子树 -&gt; 右子树。在C++中,递归实现可以如下...

    数据结构实验-3二叉树遍历与路径查找(二叉树实验)

    实验三 二叉树遍历与路径查找(二叉树实验) 实现功能:建立二叉树存储结构、求二叉树的先序遍历、求二叉树的中序遍历、求二叉树的后序遍历、求二叉树的层次遍历、求根到给定结点的路径。 主控菜单: 1.建立二叉树...

    遍历二叉树程序

    遍历二叉树程序,亲自调试,注释详尽,有不懂的随时和大家交流,希望能帮到大家~

    二叉树遍历算法应用各种算法包括遍历创建求深度等

    二叉树遍历算法应用 二叉树是一种常见的数据结构,遍历二叉树是指从根节点开始访问树中的所有节点,并对其进行处理。二叉树遍历算法有多种,包括前序遍历、中序遍历、后序遍历、层次遍历等。每种遍历算法都有其特点...

    二叉树的遍历以及创建.zip

    二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的遍历以及创建.zip二叉树的...

    实现先序,中序和后序遍历的二叉树遍历程序

    二叉树遍历是针对这种数据结构的一种基本操作,用于按照特定顺序访问树中的所有节点。本程序实现了三种主要的二叉树遍历方法:先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释: 1. 先序遍历...

    二叉树遍历实验报告

    ### 二叉树遍历实验报告知识点概览 #### 一、实验背景及目标 **实验背景:** 本次实验属于《数据结构》课程的一部分,旨在通过实际编程加深学生对二叉树这一数据结构的理解和应用能力。二叉树作为一种基本且重要的...

    递归方式遍历二叉树

    java实现创建二叉树,并且遍历二叉树(此处使用递归方式遍历); 创建二叉树的方式有很多,此处使用线性的链表转化成二叉树,链表节点的顺序就是前序遍历的顺序,链表中的null值,代表二叉树左节点或者右节点为null...

Global site tag (gtag.js) - Google Analytics