二叉树的性质概念脑图思维导图

树是由n（n>=0)个元素组成的有限集合

当n=0时，树为空树

每个元素称为结点

有且仅有一个首结点，即根结点

除根结点之外，每个结点都有唯一的前驱结点

每个结点都有0个或多个后继结点

当n>1时，除根结点之外的其他结点可以被划分为m（m>0）个互不相交的有限集合，这些树称为根结点的子树

子树：根结点的分叉树

高度：由底向上

深度：自顶向下

空二叉树：n=0

二叉树中每个结点的度必须小于等于2

每层结点个数必须满足2^n-1个

叶子只能出现在最下一层

非叶子结点的度一定是2

在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多

叶子结点只能出现在最后一层或倒数第二层

最下层叶子结点一定集中在左部连续位置

倒数第二层如果有叶子结点，一定出现在右部连续位置

同样结点数的二叉树，完全二叉树的深度最小

在非空二叉树的i层上，至多有2^（i-1）个结点

在深度为K的二叉树上最多有2^k -1个结点

对于任何一颗非空的二叉树，如果叶结点个数为n0，度数为2的结点个数为n2，则有n0=n2+1

在一颗只有度为0和度为2的二叉树中高度（深度）与结点个数的关系：2h（k）-1=n

具有n个结点的完全二叉树的深度为log2n+1

在深度为k的满二叉树中的结点数量是2^k -1=n,完全二叉树结点数量肯定最多2^k -1,同时完全二叉树倒数第二层肯定是满的，所以完全二叉树的结点数至少大于少一层的满二叉树，为2^k -1

n个结点的完全二叉树，对任意一层的结点i有

顺序存储结构

链式存储结构

根据先序遍历的顺序，先访问根结点，再访问左子树，后访问右子树

边访问边输出

二叉树是一种特殊的树形结构，每个节点最多只有两个子节点，通常称为左子节点和右子节点。

定义节点

构造方法步骤

前序遍历

中序遍历

后序遍历

struct Node

{

Datatype data；

 int parent；

}

void union （interesting root，int root2）

{

 s[root2].parent = root1;

}

查找某个元素所在的集合，返回该集合的代表元素，即根结点

int find(int x)

{

 if (s[x].parent < 0)

 return x;

 else

 return find(s[x].parent);

}