树
树可以简单理解为是由节点和边(存放指针域,指向下一个结点的地址)组成,每个节点只有一个父节点(根节点除外),但可以有多个子节点。树只有一个称为根的节点,树有若干个子树,且这些子树本身也是一棵树。树里面有很多专业术语,常用的有:深度(从根节点到最底层结点的层数,根节点是第一层),叶子节点(没有子节点的节点),非叶子节点(也叫非终端节点,含有子节点),度(某个节点含有子节点的个数,树的都按节点的最大度算),节点的层次(根作为第1层,根的子节点作为第2层,以此类推到该节点的层数)。树的分类分为一般树(任何一个节点的子节点的个数都不受限制);二叉树(有序):任何一个节点的子节点的个数最多两个,且子节点的位置不可更改;森林(n个互不相交的树的集合)。我们用的最多的是二叉树,而二叉树又分为:一般二叉树,满二叉树(每一层节点数都是最大节点数),完全二叉树(只是删除了或未删除满二叉树最底层最右边的连续若干个节点);可以看出满二叉树只是完全二叉树的一个特例。一般树的存储可以通过将其转化成二叉树来存储(森林也是这样做的)再来存储二叉树,具体做法是:设法保证任意一个节点的左指针域指向它的第一个孩子,右指针域指向它的下一个兄弟。不难发现一般树转成二叉树一定没有右子树(因为根节点没有兄弟节点)。树的应用非常广泛,如操作系统中子父进程的关系本身就是一棵树、树是数据库中组织的一种重要形式,还有面向对象中类的继承关系都可以看做是树。
二叉树的三种遍历
二叉树的三种遍历在考试中经常会遇到,三种遍历分为:先序遍历,中序遍历,后序遍历。先序遍历的操作是先访问根节点,然后先序遍历左子树,再先序遍历右子树;中序遍历的操作是中序遍历左子树,然后访问根节点,再中序遍历右子树;后序遍历的操作是后序遍历左子树,然后后序遍历右子树,再访问根节点。可以看到这里的先中后是针对根节点而言的。遍历的思想是把非线性结构通过线性方式来遍历。如何通过先序和中序遍历或中序和后序遍历来求另外一种遍历(但已知先序和后序不能)也经常考。
链式二叉树
实例说明
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
typedef struct BTNode
{
char data;//数据域
struct BTNode *pLchild;//左指针域
struct BTNode *pRchild;//右指针域
}BTNODE;
BTNODE *CreateBTree(void);//创建二叉树,并返回根节点的地址
void PreTraverseBTree(BTNODE *);//先序遍历
void InTraverseBTree(BTNODE *);//中序遍历
void PostTraverseBTree(BTNODE *);//后序遍历
int main()
{
BTNODE *pT=CreateBTree();//让pT指向CreateBTree()函数返回的根节点
printf("先序遍历:");
PreTraverseBTree(pT);
printf("\n");
printf("中序遍历:");
InTraverseBTree(pT);
printf("\n");
printf("后序遍历:");
PostTraverseBTree(pT);
printf("\n");
return 0;
}
BTNODE *CreateBTree(void)//这里只造5个节点
{
BTNODE *pA=(BTNODE *)malloc(sizeof(BTNODE));//造根节点
BTNODE *pB=(BTNODE *)malloc(sizeof(BTNODE));
BTNODE *pC=(BTNODE *)malloc(sizeof(BTNODE));
BTNODE *pD=(BTNODE *)malloc(sizeof(BTNODE));
BTNODE *pE=(BTNODE *)malloc(sizeof(BTNODE));
if(NULL==pA||NULL==pB||NULL==pC||NULL==pD||NULL==pE)
{
printf("动态内存分配失败!\n");
exit(-1);//终止程序
}
pA->data='A';
pB->data='B';
pC->data='C';
pD->data='D';
pE->data='E';
pA->pLchild=pB;
pA->pRchild=pC;
pB->pLchild=pB->pRchild=NULL;
pC->pLchild=pD;
pC->pRchild=NULL;
pD->pLchild=NULL;
pD->pRchild=pE;
pE->pLchild=pE->pRchild=NULL;
return pA;//返回根节点地址
}
/*先序遍历*/
void PreTraverseBTree(BTNODE *bT)
{
printf("%c ",bT->data);
if(NULL!=bT->pLchild)
{
PreTraverseBTree(bT->pLchild);
}
if(NULL!=bT->pRchild)
{
PreTraverseBTree(bT->pRchild);
}
}
/*中序遍历*/
void InTraverseBTree(BTNODE *bT)
{
if(NULL!=bT->pLchild)
{
InTraverseBTree(bT->pLchild);
}
printf("%c ",bT->data);
if(NULL!=bT->pRchild)
{
InTraverseBTree(bT->pRchild);
}
}
/*后序遍历*/
void PostTraverseBTree(BTNODE *bT)
{
if(NULL!=bT->pLchild)
{
PostTraverseBTree(bT->pLchild);
}
if(NULL!=bT->pRchild)
{
PostTraverseBTree(bT->pRchild);
}
printf("%c ",bT->data);
}
运行结果:
结束语
从某种角度而言,数据结构中的数据存储最核心的就是个体关系的存储,而通过泛型我们知道同一种逻辑结构(如必须都是线性结构、树、图等),无论该逻辑结构的物理存储(线性存储或非线性存储)是什么样子的,我们都可以对它进行相同的操作。今天就写到这,明天开始学习排序。
分享到:
相关推荐
链式二叉树是一种数据结构,它以节点的形式存储元素,每个节点有两个子节点:一个称为左子节点,另一个称为右子节点。这种数据结构在计算机科学中有着广泛的应用,如搜索、排序、树遍历等操作。在这个压缩包中,包含...
链式二叉树模板,方便学习C语言数据结构。自行下载,只求积分!
链式二叉树是一种数据结构,它以节点的形式存储数据,每个节点可能包含两个子节点:左子节点和右子节点。在二叉树中,遍历是访问每个节点的过程,有三种主要的遍历方式:前序遍历、中序遍历和后序遍历。本主题聚焦于...
链式二叉树递归创建及遍历的完整代码
【先序遍历】:先访问根节点,然后先序遍历左子树,再先序遍历右子树! 【中序遍历】:中序遍历左子树,然后访问根节点,再中序遍历右子树! 【后序遍历】:后序遍历左子树,然后后序遍历右子树,再访问根节点!
链式二叉树是数据结构中的一个重要概念,它在计算机科学中被广泛应用于解决各种问题。本资源聚焦于链式二叉树的实现算法,包括完整的程序代码和实验报告,适用于重庆大学数据结构课程的实验四。下面我们将深入探讨...
链式二叉树是一种数据结构,它以节点的形式存储数据,每个节点有两个子节点:左子节点和右子节点。二叉树的操作通常包括插入、删除、查找以及各种遍历方式。在本话题中,我们将重点讨论链式二叉树的中序遍历,包括...
链式二叉树是一种数据结构,它以节点的形式存储数据,并通过指针连接这些节点,形成树状结构。在二叉树中,每个节点最多有两个子节点,分别称为左子节点和右子节点。二叉树的操作主要包括创建、遍历、销毁以及计算树...
//C++实现链式二叉树,采用非递归的方式先序,中序,后序遍历二叉树#include “stdafx.h”#include<iostream>#include<string>#include <stack>using namespace std;template<class>struct BiNode{ T data; struct...
本例程详细讲解了链式二叉树的实现方法和实现的函数,对于学习数据结构中的链式二叉树具有很好的学习作用,可以充分理解二叉树的结构和特性
内容概要:用c代码完成链式二叉树、有序二叉树、线索二叉树的的常见操作。其中包括构建、销毁、前序/后序/中序遍历、高度、密度、添加、删除、查询等操作 适合人群:具备一定编程基础,尤其是c语言基础,并很好地...
在这个资源中,我们专注于二叉树的链式表示以及其遍历方法,这些都是理解和实现二叉树算法的关键。 首先,我们来看"二叉树"这一概念。二叉树可以被看作是一种非线性的数据结构,其中每个节点包含一个值、一个指向左...
链式二叉树是二叉树最常见的表示方法,每个节点包含三个部分:数据域、指向左子节点的指针和指向右子节点的指针。这种结构允许节点在内存中的任意位置,使得插入和删除操作相对灵活。链式二叉树的主要操作包括: 1....
在链式存储的二叉树中,每个节点通常包含三个字段:数据、左子节点的指针和右子节点的指针。 链表是另一种重要的数据结构,它由一系列节点组成,每个节点包含数据和指向下一个节点的指针。链表与数组相比,优点在于...
链式二叉树是一种在计算机科学中用于存储和操作二叉树数据结构的数据结构实现方式。在这种实现中,每个节点包含指向其左子节点和右子节点的指针,而不是像数组或矩阵那样通过索引访问。这种设计使得二叉树可以更灵活...
还有一些链式二叉树的相关内容,在这里为了简单链式二叉树相关内容均是用递归的思路来进行实现的,因而算是初阶数据结构二叉树的一个小集合。 适合人群:学生,学习初阶数据结构的人群 能学到什么:通过简单的代码,...
链式存储二叉树是一种在计算机科学中用于表示和操作二叉树的数据结构。与数组存储方式不同,链式存储不依赖于连续的内存空间,而是通过指针连接各个节点,使得二叉树可以在内存中灵活分布。这种存储方式特别适用于...
本文实例讲述了C++使用递归和非递归算法实现的二叉树叶子节点个数计算方法。分享给大家供大家参考,具体如下: /*求二叉树叶子节点个数 -- 采用递归和非递归方法 经调试可运行源码及分析如下: ***/ #include #...