2025年【常用数据结构——二叉树（还有三叉四叉...？）】

科技前沿 • 2025-01-25 12:01 • 阅读 31

大家好，我是讯享网，很高兴认识大家。

---恢复内容开始---

简介

　　在计算机科学中，二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

也就五种，从左往右分别是空树，只有根节点的树，根节点和左儿子，根节点和右孩子，根节点和左右孩子。

1.二叉树第i层上的结点数目最多为2^i-1(i>=1)

2.深度为k的二叉树至多有2^k-1个结点（k>=1）

3.包含n个结点的二叉树的高度至少为(log₂n)+1

4.在任意二叉树中，若度为0的个数为n₀，度为2的结点数为n₂，则n₀=n₂+1

5.如果对一棵有n个节点的完全二叉树的节点按层序编号（从第一层开始到最下一层，每一层从左到右编号），对任一节点i有：

　　就像它的名字一样，它是满的（废话）

　　满二叉树是指一个高度为n的树有2^(n-1)个结点（其实就是每个点都有两个孩子，除了最后一层的单身狗）

　　完全二叉树是指一颗二叉树的叶子结点只在最后两层，并且最后一层的叶子结点都集中在左边。显然，满二叉树也是一颗完全二叉树。

　　对于二叉树的遍历，我们分为三种情况：

以下顺序就是

1 void work(int x) 2 { 3 if(!x)return;//如果这个点有效  4 printf("%d ",x);//根  5 work(l[x]);//左子树  6 work(r[x]);//右子树  7 }

讯享网