目录
🌴树是什么
🌴二叉树
🌲两种特殊的二叉树
🌲二叉树的性质
🌲二叉树的存储
🌲二叉树的遍历
🌴小结
🌴树是什么 树 是一种非线性 的数据结构，它是由 n （ n>=0 ）个有限结点组成一个具有层次关系的集合。 把它叫做树是因为它看 起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的 。它具有以下的特点： 1、有一个特殊的节点，称为根节点(如下图的A节点），根节点没有前驱节点。 2、除根节点外，其余节点被分成 M(M > 0) 个互不相交的集合 T1 、 T2 、 ...... 、 Tm ，其中每一个集合 Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有 0 个或多个后继 。 3、树是递归定义的。
主要概念：
🌴二叉树🌵双亲结点或者父节点：若一个节点含有子节点，则称该节点为子节点的父节点。（如上图A为B的父节点）
🌵孩子节点或者子节点：一个节点含有的子树的根节点称为该节点的子节点。（如B节点为A节点的子节点）
🌵根节点：没有父节点的节点（A）。
🌵叶节点：没有子节点也就是度为0的节点（上图的B、C等）
🌵节点的度：一个节点含有子节点的个数称为该节点的度。（例如A的度为6，D的度为1）
🌵树的度：一棵树中最大节点的度称为树的度。（上图树的度为6）
🌵根结点 ：一棵树中，没有双亲结点的结点。（如上图： A） 🌵节点的层次 ：从根开始定义起，根为第 1 层，根的子节点为第 2 层，以此类推。 🌵树的深度和高度：高度为最大深度。
🌵概念
一棵二叉树是结点的一个有限集合，该集合或者为空，或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成。 （度小于等于2的树称为二叉树） 二叉树的特点： 1. 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。 2. 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。🌵基本形态：
从左往右依次是：空树、只有根节点的二叉树、节点只有左子树、节点只有右子树、节点的左右子树均存在，一般二叉树都是由上述基本形态结合而形成的。 🌲两种特殊的二叉树1、满二叉树：一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。
(如果一个二叉树的层数为 K ，且结点总数是 2^k-1，则它就是满二叉树)2、完全二叉树
对于深度为 K 的，有 n个结点的二叉树，当且仅当其每一个结点都与深度为 K 的满二叉树中编号从 1 至 n 的结点一一对应时称之为完全 二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。举个反例：
🌲二叉树的性质🌵若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 2^（i-1）(i>0)个结点。
🌵 若规定只有 根节点的二叉树的深度为 1 ，则深度为2^（K-1）的二叉树的最大结点数是(k>=0) 🌵 对任何一棵二叉树 , 如果其 叶结点个数为 n0, 度为 2 的非叶结点个数为 n2, 则有 n0 ＝ n2 ＋ 1 。例题1：
1、某二叉树共有399个结点，其中有199个度为2的结点，则该二叉树中的叶子结点数为( B)
A、不存在这样的二=叉树
B、200
C 、198
D、 199
由2可知度为2（n2）的结点个数为199，则根据公式n0=n2+1；所以该二叉树中叶子结点数为200。
例题2：
2、在具有2n个结点的完全二叉树中，叶子结点个数为(A )
A、n
B、 n+1
C 、n-1
D 、n/2
解题思路：
例题3：
3、一个具有767个节点的完全二叉树，其叶子节点个数为(B)
A、383
B、384
C、385
D、386
解题思路：
🌵 具有n个结点的完全二叉树的深度k为 log2（n+1）向上取整 。
🌵对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若子节点的编号为i，则父节点编号为（i-1）/2；
若父节点的编号为i，则左孩子节点编号为2i+1，右节点编号为2i+2；
🌲二叉树的存储 二叉树的存储结构 分为： 顺序存储 和 类似于链表的链式存储。这里主要介绍类似于链表的链式存储。二叉树的链式存储是通过一个一个的节点引用起来的，常见的表示方式有二叉和三叉表示方式，具体如下：
// 孩子表示法
class TreeNode {
int val; // 数据域
TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
}
// 孩子双亲表示法
class TreeNode {
int val; // 数据域
TreeNode left; // 左孩子的引用，常常代表左孩子为根的整棵左子树
TreeNode right; // 右孩子的引用，常常代表右孩子为根的整棵右子树
TreeNode parent; // 当前节点的根节点
}接下来的 *** 作一般都是用孩子表示法。
🌲二叉树的遍历1、前序遍历（根节点-->左节点-->右节点)
递归实现（遍历结果放list里面）
public List preorderTraversal(TreeNode root) {//给根节点来遍历数组
List list=new ArrayList<>();
if(root==null){
return list;
}
list.add(root.val);
List left=new ArrayList<>();
left=preorderTraversal(root.left);
list.addAll(left);
List right=new ArrayList<>();
right=preorderTraversal(root.right);
list.addAll(right);
return list;
} 2、中序遍历（左节点-->根节点-->右节点)
递归实现（遍历结果放list里面）
public List inorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List left=inorderTraversal(root.left);
list.addAll(left);
list.add(root.val);
List right=inorderTraversal(root.right);
list.addAll(right);
return list;
} 3、后序遍历（左节点-->右节点-->根节点)
递归实现（遍历结果放list里面）
public List postorderTraversal(TreeNode root) {
List list=new ArrayList<>();
if(root==null){
return list;
}
List left=postorderTraversal(root.left);
list.addAll(left);
List right=postorderTraversal(root.right);
list.addAll(right);
list.add(root.val);
return list;
} 4、层序遍历
public List> levelOrder(TreeNode root) {
List> ret= new ArrayList>();
if(root==null){
return ret;
}
Queue queue=new LinkedList();
queue.offer(root);
while(!queue.isEmpty()){
List list=new ArrayList<>();
int size=queue.size();
for(int i=0;i 以上就是今天的内容了，有什么问题大家都可以在评论区留言哦✌✌✌
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）