从一个初学者看树

飞熊 • 2023年4月2日下午5:28 • 技术随笔 • 阅读 208

树的基本定义

树(tree）可以用几种方式定义。定义树的一种自然的方式是递归的方法。一棵树是一些结点的集合。这个集合可以是空集;若不是空集，则树由称作根（root)的结点r以及零个或多个非空的(子）树T,T，…,T组成，这些子树中每一棵的根都被来自根r的一条有向的边（edge)所连接。

叶子节点：没有左孩子和右孩子

非叶节点：有child

深度:对任意结点n，ni的深度( depth)为从根到n0的唯一路径的长

高度：( height）是从ni到一片树叶的最长路径的长.

树的实现

struct TreeNode
{
 object element;
 TreeNode* firstchild;
 TreeNode* nextSlibing；

}；

前序中左右

中序左中右

后序左右中

代码前序

void traversal（TreeNode* root）
{
vector<int>vec;
if(root=nullptr)return;
vec.push_back(root->val);
traversal(root->left);
traversal(root->right);
}

满二叉树：如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。

如图所示：

什么是完全二叉树？

完全二叉树的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^(h-1) 个节点。

前面介绍的树，都没有数值的，而二叉搜索树是有数值的了，二叉搜索树是一个有序树。

如果向一棵预先排序的树输入数据，那么–连串insert操作将花费二次的时间，而链表实现的代价会非常巨大，因为此时的树将只由那些没有左儿子的结点组成。一种解决办法就是要有一个称为平衡(balance）的附加的结构条件:任何结点的深度均不得过深。

平衡条件是要求每个结点都必须有相同高度的左子树和右子树。如果空子树的高度定义为-1（通常就是这么定义)，那么只有具有2*-1个结点的理想平衡树满足这个条件。因此，虽然这种平衡条件保证了树的深度小，但是它太严格，难以使用，需要放宽条件

左边和右边深度之差绝对值不超过一

文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/129657.html