树，二叉树

在讨论二叉树之前，先讨论一下低级树和图的概念

树: 无环的连通无向图（树是简单的非线性结构）

该树具有不包含循环的特征，因此该树具有许

1. 一棵树中的任何两个节点仅通过一条路径连接

2. 如果一棵树有n个节点，那么它必须恰好具有n-1个边缘

3. 在树上添加边缘会形成循环

4. 树中只有一个节点，没有称为根节点的前体

在讨论树时，树中的每个点都称为节点，

**根节点: **没有父节点的节点

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

**内部节点: **一个节点既不是根节点也不是叶节点

每个节点都有一个深度. 例如，左侧树中第4个节点的深度为3（深度是指从根节点到该节点的层数，并且根节点是第一层）<

有两种遍历树的方法:

一种方法是先遍历树二叉排序树时间复杂度，即首先访问树的根节点，然后依次遍历根的每个子树.

另一种是后根遍历树，即首先使用该后根遍历每个子树，然后访问根节点.

上图中的第一个根遍历序列是ABEFCDG，最后一个根遍历序列是EBFCGDA.

二叉树是计算机科学中每个节点最多具有两个子树的树结构. 通常，子树称为“左子树”（左子树）和“右子树”（右子树）. 二进制树通常用于实现二进制搜索树和二进制堆.

**完整的二叉树: **二叉树中的每个内部节点都有一个左子树和一个右子树（或整个二叉树的所有叶节点具有相同的深度）.

完整的二叉树必须是完整的二叉树，但是完整的二叉树不一定是完整的二叉树.

（完整二叉树的严格定义是: 深度为h且节点数为2h-1的二叉树）.

**完整的二叉树: **完整的二叉树-如果二叉树的高度为h，则除h层外，其他所有层（1〜h-1）的节点数均达到最大值， h层中有叶节点，叶节点从左到右排列，是完整的二叉树.

**平衡的二叉树: **平衡的二叉树，也称为AVL树（与AVL算法不同），是具有以下属性的二进制排序树: 它是空树或其左，右子节点，绝对树的高度差值不超过1二叉排序树时间复杂度，左右子树均为平衡二叉树.

与二叉树有关的词的解释:

**节点的度数: **节点拥有的子树的数量

**叶节点: **度为0的节点（提示: 在任何二叉树中，度为0的叶节点总是比度为2的节点大一个）

**分支节点: 度数不为0的节点

**树的程度: **树中节点的最大程度

**级别: **根节点的级别为1，其余节点的级别等于该节点的父节点的级别加1

**树的高度: **树中节点的最大级别

属性1如果二叉树的级别从0开始，则在二叉树的第i层中最多有2i个节点. （I≥0）

属性2高度为h的二叉树最多具有2h + 1-1个节点. （H≥-1）

属性3对于任何二叉树，如果存在n0个叶子节点和n2个2级的非叶子节点，则有: n0 = n2 + 1

属性4具有n（n≥0）个节点的完整二叉树的高度为[log2（n + 1）]-1.

属性5如果将具有n个节点的完整二叉树从上到下放置，并且这些节点从左到右在同一级别上连续编号为0,1,2，...，n-1，则存在以下关系:

如果i = 0，则我没有父母；如果i> 0，则我的父母为[（i-1）/ 2].

如果2i + 1

如果我是偶数，我！ = 0，则其左兄弟为i-1，如果i为奇数，则i！ = n-1，右边的兄弟是i + 1.

所谓的遍历（Traversal）是指遵循一定的搜索路径，依次对树中的每个节点进行一次访问，而仅一次访问. 接入节点执行的操作取决于特定的应用程序问题. 遍历是二叉树上最重要的操作之一，也是二叉树上其他操作的基础.

二叉树遍历算法有三种:

**遍历遍历: **首先访问根节点，然后遍历左侧子树，最后遍历右侧子树（root-> left-> right）

**序列遍历: **首先遍历左侧子树，然后访问根节点，最后遍历右侧子树（left-> root-> right）

**事后遍历: **首先遍历左侧子树，然后遍历右侧子树，最后访问根节点（left-> right-> root）

例如:

预遍历顺序为: ABDGHCEIF（规则是先根节点，然后对左子树进行预排序，然后对右子树进行预排序）

它的中序遍历顺序是: GDHBAEICF（规则是先遍历左子树，然后遍历根节点，然后遍历右子树）

其后遍历顺序为: GHDBIEFCA（规则是先遍历左子树，然后遍历右子树，再遍历根节点）

二叉树的递归遍历遍历算法:

int PreTraverse（BiTree T）

{

如果（T = -NULL）返回0;

Visit（T）;

PreTraverse（T-> lchild）;

PreTraverse（T> rchild）;

返回1；

}

用于二叉树递归的中阶遍历算法:

int InTraverse（BiTree T）

{

如果（T == NULL）返回0;

InTraverse（T-> lchild）;

Visit（T）;

InTraverse（T-> rchild）;

返回1；

}

二叉树的递归后序遍历算法

int SucTraverse（BiTree T）

{

如果（T = -NULL）返回0;

SucTraverse（T> lchild）;

SucTraverse（T-> rchild）;

Visit（T）;

返回1；

}

本文来自电脑杂谈，转载请注明本文网址：
https://www.pc-fly.com/a/jisuanjixue/article-251346-1.html