初识数据结构——二叉树从基础概念到实践应用
数据结构专栏 ⬅(click)
初识二叉树：从基础概念到实践应用🌳
一、树型结构基础
1.1 树的基本概念
树是一种非线性的数据结构，由n(n>0)个有限节点组成一个具有层次关系的集合。它看起来像一棵倒挂的树，根朝上而叶朝下。
关键特点：有且仅有一个根节点，没有前驱节点除根节点外，其余节点被分成M(M>0)个互不相交的子树树是递归定义的
重要术语：结点的度：一个结点含有子树的个数树的度：树中所有结点度的最大值叶子结点：度为0的结点双亲结点/父结点：含有子结点的结点孩子结点/子结点：一个结点含有的子树的根结点根结点：没有双亲结点的结点结点的层次：从根开始定义，根为第1层树的高度/深度：树中结点的最大层次
1.2 树的表示方法
最常用的表示方法是孩子兄弟表示法：
classNode{int value;// 树中存储的数据Node firstChild;// 第一个孩子引用Node nextBrother;// 下一个兄弟引用}
二、二叉树详解
2.1 二叉树概念
二叉树是结点的一个有限集合，该集合：
- 或者为空
- 或者由一个根节点加上两棵分别称为左子树和右子树的二叉树组成
特点：
- 二叉树不存在度大于2的结点
二叉树的子树有左右之分，次序不能颠倒，是有序树
2.2 特殊二叉树
- 满二叉树：每层的结点数都达到最大值。层数为K，结点总数是2^K-1
完全二叉树：深度为K，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应
2.3 二叉树的性质
- 非空二叉树的第i层最多有2^(i-1)个结点
- 深度为K的二叉树最大结点数是2^K-1
- 对于任何二叉树，n0(叶子结点) = n2(度为2的结点) + 1
- 具有n个结点的完全二叉树深度为⌈log₂(n+1)⌉
- 完全二叉树的父子结点关系：
- 父结点序号：(i-1)/2
- 左孩子序号：2i+1
- 右孩子序号：2i+2
2.4 二叉树的存储
链式存储
// 孩子表示法classNode{int val;// 数据域Node left;// 左孩子引用，常常代表左孩⼦为根的整棵左⼦树 Node right;// 右孩子引用，常常代表右孩⼦为根的整棵右⼦树 }// 孩子双亲表示法classNode{int val;Node left;// 左孩子引用，常常代表左孩⼦为根的整棵左⼦树 Node right;// 右孩子引用，常常代表右孩⼦为根的整棵右⼦树 Node parent;// 当前节点的根节点}三、二叉树遍历
遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。访问结点所做的操作依赖于具体的应⽤问题(比如：打印节点内容、节点内容加1)。遍历是⼆叉树上最重要的操作之一，是二叉树上进行其它运算之基础。
3.1 递归遍历
- (NLR)前序遍历：根节点 -> 左子树 -> 右子树
- (LNR)中序遍历：左子树 -> 根节点 -> 右子树
(LRN)后序遍历：左子树 -> 右子树 -> 根节点
// 前序遍历voidpreOrder(Node root){if(root ==null)return;System.out.print(root.val +" ");preOrder(root.left);preOrder(root.right);}// 中序遍历voidinOrder(Node root){if(root ==null)return;inOrder(root.left);System.out.print(root.val +" ");inOrder(root.right);}// 后序遍历voidpostOrder(Node root){if(root ==null)return;postOrder(root.left);postOrder(root.right);System.out.print(root.val +" ");}3.2 层序遍历
从根节点出发，按层次从上到下、从左到右访问结点。
voidlevelOrder(Node root){if(root ==null)return;Queue<Node> queue =newLinkedList<>(); queue.offer(root);while(!queue.isEmpty()){Node cur = queue.poll();System.out.print(cur.val +" ");if(cur.left !=null) queue.offer(cur.left);if(cur.right !=null) queue.offer(cur.right);}}四、二叉树基本操作
代码示例：
// 获取节点个数intsize(Node root){if(root ==null)return0;return1+size(root.left)+size(root.right);}// 获取叶子节点个数intgetLeafNodeCount(Node root){if(root ==null)return0;if(root.left ==null&& root.right ==null)return1;returngetLeafNodeCount(root.left)+getLeafNodeCount(root.right);}// 获取第k层节点个数intgetKLevelNodeCount(Node root,int k){if(root ==null|| k <=0)return0;if(k ==1)return1;returngetKLevelNodeCount(root.left, k-1)+getKLevelNodeCount(root.right, k-1);}// 获取二叉树高度intgetHeight(Node root){if(root ==null)return0;return1+Math.max(getHeight(root.left),getHeight(root.right));}// 查找值为val的节点Nodefind(Node root,int val){if(root ==null)returnnull;if(root.val == val)return root;Node left =find(root.left, val);if(left !=null)return left;returnfind(root.right, val);}结语
二叉树是数据结构中的核心内容，掌握好二叉树对于理解更复杂的数据结构和算法至关重要。建议读者在学习理论的同时，多动手实现代码，解决实际问题，才能真正掌握二叉树的精髓。
