树的基本概念-创新互联

树 树的定义

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

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

当n=0时，称为空树

特征

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

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

基本术语

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

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

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

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

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

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

• 路径：从结点n₁到n_k的路径为一个结点序列n₁，n₂…. n_k，n_i是n₊₁的父结点

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

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

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

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

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

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

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

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

二叉树

即度为2的树

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

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

二叉树定义

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

这个集合可以为空

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

五种形态

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

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

特殊形态

• 斜二叉树

只有左儿子或右儿子

• 完美二叉树（满二叉树）

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

• 完全二叉树

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

重要性质

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

• 深度为 k 的二叉树有大结点总数为：2^k-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 ，否则没有右孩子）

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

2.链式存储

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

---

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

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

文章标题：树的基本概念-创新互联
文章URL：http://cdkjz.cn/article/cesghg.html