阿坝州网站建设公司

树的基本概念-创新互联

树 树的定义

树（Tree）：n（n$\geq$0）个结点构成的有限集合

创新互联服务项目包括高县网站建设、高县网站制作、高县网页制作以及高县网络营销策划等。多年来，我们专注于互联网行业，利用自身积累的技术优势、行业经验、深度合作伙伴关系等，向广大中小型企业、政府机构等提供互联网行业的解决方案，高县网站推广取得了明显的社会效益与经济效益。目前，我们服务的客户以成都为中心已经辐射到高县省份的部分城市，未来相信会继续扩大服务区域并继续获得客户的支持与信任！

当n=0时，称为空树

特征

对于任一棵非空树（n>0），它具备一下特征：

  • 树中有个称为“根（Root）”的特殊结点，用r表示
  • 其余结点可分为m（m>0）个互不相交的有限集T1，T2…，Tm，其中每个集合本身又是一棵树，称为原来树的“子树（SubTree）”
  • 子树是不相交的
  • 除根节点外，每个结点都有且仅有一个父节点
  • 一棵N个结点的树有N-1条边
基本术语

  • 结点的度（Degree）：结点的子树个数

  • 树的度：树的所有结点中大的度数

  • 叶节点（Leaf）：度为0的结点

  • 父结点（Parent）：有子树的结点是其子树的根结点的父结点

  • 子节点（Child）：若A结点是B结点的父结点，则称B结点是A结点的子节点，也成孩子结点

  • 兄弟结点（Sibling）：具有统一父节点的各个结点彼此是兄弟结点

  • 路径：从结点n1到nk的路径为一个结点序列n1，n2…. nk，ni是n+1的父结点

  • 路径长度：路径所包含边的个数

  • 祖先结点（Ancestor）：沿树根到某一结点路径上的所有结点都是这个结点的祖宗结点

  • 子孙结点（Descendant）：某一结点的子树中的所有结点是这个结点的子孙

  • 结点的层次（Level）：规定根结点在1层，其他任一结点的层数是其父结点的层数+1

  • 树的深度（Depth）：树中所有结点中大层次是这棵树的深度

树的表示 儿子 - 兄弟表示法

image-20221130222844807

  • Element 存值
  • FirstChild 指向第一个儿子
  • NextSibing 指向下一个兄弟

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-O9SqFjfd-1669946093040)(C:\Users\lx659\AppData\Roaming\Typora\typora-user-images\image-20221130223011506.png)]

二叉树

即度为2的树

image-20221130223046184

  • Element 存值
  • Left 指向左子树
  • Right 指向右子树

二叉树其实就是儿子 - 兄弟表示法的链表右移45°得到的结果

image-20221130223154792

二叉树定义

二叉树 T ：一个有穷的结点集合

这个集合可以为空

若不为空，则它是由根结点和称为其**左子树TL和右子树TR**的两个不想交的二叉树组成二叉树的子树有左右顺序之分

五种形态

image-20221201152616240

a：空树；b：只有一个结点；c：有一个结点，只有一个左子树；d：有一个结点，只有一个右子树，e：有一个结点，有左右子树

二叉树的子树有左右顺序之分

特殊形态
  • 斜二叉树

只有左儿子或右儿子

image-20221201152733537
  • 完美二叉树（满二叉树）

除最后一层叶节点外，每个结点都有两个子节点

image-20221201152903267

  • 完全二叉树

有n个结点的二叉树，对树中结点按从上至下，从左到右顺序进行编号，编号为 i （1 ≤ \leq ≤i ≤ \leq ≤n）结点与满二叉树中编号为 i 结点在二叉树中位置相同

image-20221201153321215

重要性质

  • 一个二叉树第 i 层的大结点树为：2i-1,i ≥ \geq ≥ 1

  • 深度为 k 的二叉树有大结点总数为：2k-1，k ≥ \geq ≥ 1

  • 操作集：BT ∈ \in ∈BinTree，item ∈ \in ∈int

主要操作有

  • 判断BT是否为空
  • 遍历，按某顺序访问每个结点
  • 创建一个二叉树

常见的遍历方法有

  • 先序——根，左子树，右子树
  • 中序——左子树，根，右子树
  • 后序——左子树，右子树，根
  • 层次遍历——，从上到下，从左到右
1.顺序存储结构

按从上到下，从左到右顺序存储n个结点的完全二叉树的结点父子关系：

  • 非根结点（序号 i >1）的父结点的序号是[i/2]（向下取整）
  • 结点（序号为 i ）的左孩子结点的序号是2i（若2 i ≤ \leq ≤ n，否则没有左孩子）
  • 结点（序号为 i ）的右孩子结点的序号是2i+1（若2 i +1 ≤ \leq ≤ n ，否则没有右孩子）

image-20221202095002937

image-20221202095015136

一般二叉树会造成空间浪费

2.链式存储

image-20221202095049786

typedef struct TreeNode{
	int Data;  // 存值
    BinTree Left;   //左儿子结点
    BinTree Right;  //右儿子结点
}*BinTree;

今天18岁生日，此博客由杜老板赞助发布

你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧


本文名称：树的基本概念-创新互联
本文路径：http://azwzsj.com/article/cesghg.html

其他资讯