C语言|数据结构——树的定义、存储与遍历

简介: 基本概念定义:1.有且只有一个称为根的节点; 2.有若干个互不相交的子树,这些子树本身也是一棵树; 3.由节点和边组组成的; 4.每个节点只有一个父节点,可以有无数个子节点(除了根节点)。分类:|一般树。任意一个子节点个数不受限制,可以是有序树也可以是无序树。|二叉树。任意一个节点最大度为2,二叉树是有序树,左右节点不能随意互换。 | 一般二叉树 |满二叉树。每一层节点都是满的。 |完全二叉树。除最后一层外,每一层节点都是满的,最后一层节点一定从左向右连续排列。|森林。n个互不相交的树的集合,可以是互不相连的几个树一些专业术语:父节

基本概念

定义:

1.有且只有一个称为根的节点;  

2.有若干个互不相交的子树,这些子树本身也是一棵树;  

3.由节点和边组组成的;  

4.每个节点只有一个父节点,可以有无数个子节点(除了根节点)。

分类:

|一般树。任意一个子节点个数不受限制,可以是有序树也可以是无序树。

|二叉树。任意一个节点最大度为2,二叉树是有序树,左右节点不能随意互换。

    | 一般二叉树

    |满二叉树。每一层节点都是满的。

    |完全二叉树。除最后一层外,每一层节点都是满的,最后一层节点一定从左向右连续排列。

|森林。n个互不相交的树的集合,可以是互不相连的几个树

一些专业术语:

父节点:该节点上面紧挨着的一个节点,一个节点只有一个父节点。

祖先节点:一个节点的父节点的父节点,一个节点只有一个。

兄弟节点:两个节点具有共同的父节点。

堂兄弟节点:两个节点的父节点不同,但各自的父节点彼此是兄弟节点。

子孙节点:一个节点的所有子节点和子孙节点。

树的深度:从根节点到最底层节点的层数,根节点是第一层。

叶子节点:没有子节点的节点。

非终端节点:非叶子节点。

度:子结点的个数称为度。

最大的度:一个树中含有最大度的那个度是这个树最大的度。

树的存储

本质是把非线性结构转化成线性结构进行存储。任何树的存储都是先转化成二叉树之后再按照二叉树的方式进行存储。

二叉树的存储

    |连续存储(只能以完全二叉树形式存储)

    |链式存储

一般树的存储

双亲表示法

*利用结构体数组存储

*数组下表即为该节点编号,结构体内部有两部分,一部分是数据域,一部分存储其父节点编号,如果没有父节点则为-1。

*缺点是只能记录无序树。

孩子表示法

*数组结构体

*每个节点由两部分组成,一部分是数据域,一部分存储其子节点的地址,所有孩子像链表一样连起来。后面的子节点是无序的。

*缺点是难以寻找父节点。

双亲孩子表示法

*数组结构体

*每个节点对应的数组下标就是各自的编号。每个节点由三部分组成:数据域,父节点下标,孩子节点地址。

*优势:即方便找父节点也方便找孩子节点。

二叉树表示法(最常用)

*结构体数组

*思路是先转化为二叉树,再按照二叉树的方法进行存储。每个节点有3个部分组成:一个数据域,一个指向其最左侧第一个孩子,另一个指针域指向其第一个兄弟。这一步可以把一个普通树转化为一个二叉树,这个过程也可以通过画图形象的表示出来。

*普通树转化成二叉树一定没有右子树。

森林的存储

*把森林转化成二叉树。 把根节点互相看做兄弟,接下来转化方法就跟普通树一样。

树的遍历

先序遍历,中序遍历,后序遍历这三种方法有一些共同之处:每遍历到一个节点,这个节点本身就可以看做是又一棵树的根节点。

先序遍历

根节点->先序访问左子树->先序访问右子树

下图遍历顺序:① -> ② -> ④ -> ⑤ -> ③ -> ⑥ -> ⑦

描述:先遍历根节点①;接着来到左孩子②,②这棵树仍然存在左孩子④,所以来到④;④是叶子结点,是一棵空树,左右节点都不存在,所以④这棵树遍历完成,也代表着②的左子树遍历完成;②的左子树遍历完成后,接下来来到其右孩子⑤,⑤的遍历方法和④一样;②的左右节点都遍历完成,②这棵树就遍历完成了,也就是①的左子树遍历完成;接下来以相同的方法遍历①的右子树③,大家自行推断。

        ①


       /    \


    ②     ③


    / \      / \


 ④ ⑤ ⑥ ⑦


中序遍历

左子树->根节点->先序访问右子树

上图遍历顺序:④ -> ② -> ⑤ -> ① -> ⑥ -> ③ -> ⑦

描述:根节点①的左孩子是②,②仍然有左孩子④,直到④才没有左孩子,所以④的左子树可以认为已经遍历完成,然后遍历空树④的根节点④,其右子树也不存在所以也可以认为遍历完成;④遍历完成,即②的左子树遍历完成,接着遍历②的根节点②,接着以同样的操作遍历⑤;②遍历完成,即①的左子树遍历完成,接着以同样的方法遍历其右子树③,请大家自行脑补。

后序遍历

后序遍历左子树->后序遍历右子树->根节点

上图遍历顺序:④ -> ⑤ -> ② -> ⑥ -> ⑦ -> ③ -> ①

描述:下面我只描述一下如何遍历①的右子树。记得我们上面说的吗,“每遍历到一个节点,这个节点本身就可以看做是又一棵树的根节点”,现在我们就把③看作是一棵树的根节点,所以要先遍历其左子树⑥,再遍历其右子树⑦,最后遍历根节点③。

层序遍历

从上往下,从左往右挨个遍历。

上图遍历顺序:① -> ② -> ③ -> ④ -> ⑤ -> ⑥ -> ⑦

#include <stdio.h>#include <stdlib.h> typedefstructT{
intdata;
structT*left;
structT*right;
}T,*PT;
//使用递归的方法创建一个树 PTmake()
{
intdata;
scanf("%d",&data);
getchar();//吸收scanf的回车键 //判断数据,如果是-1,那么不创建该节点并且向上返回//如果不是-1,那么就创建该节点并且把该数字存储到数据域 if(data==-1)
returnNULL;
else    {
PTtree=(PT)malloc(sizeof(T));
tree->data=data;
printf("请输入节点%d的左子树",data);
tree->left=make();
printf("请输入节点%d的右子树",data);
tree->right=make();
returntree;
    }
}
//先序遍历 :根-左-右 voidxianxu(PTtree)
{
//判断树是否为空 if(tree==NULL)
return;
else    {
printf("%d",tree->data); 
xianxu(tree->left);
xianxu(tree->right); 
    }
} 
//中序遍历:左-根-右 voidzhongxu(PTtree)
{
if(tree==NULL)
return;
else    {
xianxu(tree->left);
printf("%d",tree->data); 
xianxu(tree->right); 
    }
}
//后序遍历:左-右-根 voidhouxu(PTtree)
{
if(tree==NULL)
return;
else    {
xianxu(tree->left);
xianxu(tree->right); 
printf("%d",tree->data); 
    }
}
intmain()
{
printf("创建一棵树,请输入根节点");
PTtree=make();
intchoose;
printf("先序遍历请按1;中序遍历请按2;后序遍历请按3:\n");
scanf("%d",&choose);
getchar();
switch(choose)
    {
case1:xianxu(tree);
break;
case2:zhongxu(tree);
break;
case3:houxu(tree);
break;
default:
break;
    }
 } 


相关文章
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
984 1
|
定位技术 C语言
c语言及数据结构实现简单贪吃蛇小游戏
c语言及数据结构实现简单贪吃蛇小游戏
|
搜索推荐 C语言
数据结构(C语言)之对归并排序的介绍与理解
归并排序是一种基于分治策略的排序算法,通过递归将数组不断分割为子数组,直到每个子数组仅剩一个元素,再逐步合并这些有序的子数组以得到最终的有序数组。递归版本中,每次分割区间为[left, mid]和[mid+1, right],确保每两个区间内数据有序后进行合并。非递归版本则通过逐步增加gap值(初始为1),先对单个元素排序,再逐步扩大到更大的区间进行合并,直至整个数组有序。归并排序的时间复杂度为O(n*logn),空间复杂度为O(n),且具有稳定性,适用于普通排序及大文件排序场景。
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
891 3
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
874 1
|
数据采集 存储 算法
【C++数据结构——图】图的遍历(头歌教学实验平台习题) 【合集】
本文介绍了图的遍历算法,包括深度优先遍历(DFS)和广度优先遍历(BFS)。深度优先遍历通过递归方式从起始节点深入探索图,适用于寻找路径、拓扑排序等场景;广度优先遍历则按层次逐层访问节点,适合无权图最短路径和网络爬虫等应用。文中提供了C++代码示例,演示了如何实现这两种遍历方法,并附有测试用例及结果,帮助读者理解和实践图的遍历算法。
1026 0
|
存储 算法 C语言
【C语言程序设计——函数】素数判定(头歌实践教学平台习题)【合集】
本内容介绍了编写一个判断素数的子函数的任务,涵盖循环控制与跳转语句、算术运算符(%)、以及素数的概念。任务要求在主函数中输入整数并输出是否为素数的信息。相关知识包括 `for` 和 `while` 循环、`break` 和 `continue` 语句、取余运算符 `%` 的使用及素数定义、分布规律和应用场景。编程要求根据提示补充代码,测试说明提供了输入输出示例,最后给出通关代码和测试结果。 任务核心:编写判断素数的子函数并在主函数中调用,涉及循环结构和条件判断。
1113 23
|
安全 C语言
C语言中的字符、字符串及内存操作函数详细讲解
通过这些函数的正确使用,可以有效管理字符串和内存操作,它们是C语言编程中不可或缺的工具。
692 15
|
存储 C语言
`scanf`是C语言中用于按格式读取标准输入的函数
`scanf`是C语言中用于按格式读取标准输入的函数,通过格式字符串解析输入并存入指定变量。需注意输入格式严格匹配,并建议检查返回值以确保读取成功,提升程序健壮性。
1756 0

热门文章

最新文章