【Java】从树形结构到二叉树：一篇搞懂数据结构里的“家族树”
🎁个人主页：User_芊芊君子
🎉欢迎大家点赞👍评论📝收藏⭐文章
🔍系列专栏：Java.数据结构
【前言】
你有没有想过，电脑里的文件分类、通讯录的层级关系，其实都藏着“树”的影子？树形结构是数据结构里最像“现实家族关系”的存在，而二叉树更是其中的“明星选手”——它规则清晰、操作灵活，是很多复杂数据处理的基础。这篇文章会从树形结构的概念入手，一步步拆解二叉树的类型、性质、存储和操作，帮你把这些抽象的结构变成能上手用的知识~
文章目录：
一、树形结构
1.树形结构的概念
树是一种非线性的数据结构，它模拟了自然界中树的结构。树形结构由若干个节点(node)组成，这些节点之间存在明确的层次关系。
树是递归定义的结点的度：⼀个结点含有⼦树的个数称为该结点的度；树的度：⼀棵树中，所有结点度的最⼤值称为树的度；叶⼦结点或终端结点：度为0的结点称为叶结点；双亲结点或⽗结点：指向其他节点的节点孩⼦结点或⼦结点：被其他节点指向的节点根结点：每个树形结构有一个根节点(root)，它是树的起点 ；⾮终端结点或分⽀结点：度不为0的结点；兄弟结点：具有相同⽗结点的结点互称为兄弟结点；堂兄弟结点：双亲在同⼀层的结点互为堂兄弟；
2.树的表示形式
双亲表⽰法，孩⼦表⽰法、孩⼦双亲表⽰法、孩⼦兄弟表⽰法…
classNode{int value;//数据域 Node firstChild;//第一个孩子 Node nextBrother;//下一个兄弟 }
二、二叉树
1.概念
二叉树是一种非线性数据结构，其中每个节点最多有两棵树，分别称为左子树和右子树。
2.二叉树类型
二叉树分为两种：满二叉树和完全二叉树
2.1 满二叉树
定义：==每个节点都有0个或2个子节点 ==
特点：没有只有1个子节点的节点
2.2 完全二叉树
定义：==除最后一层外，所有层都完全填满，且最后一层节点尽可能靠左 ==
应用：常用于堆的实现
3.二叉树的性质
- 若规定根结点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)个结点(i>0)
- 若规定只有根结点的⼆叉树的深度为1，则深度为K的⼆叉树的最⼤结点数是（2^k)-1(k>=0)
- 对任何⼀棵⼆叉树,如果其叶结点个数为n0,度为2的⾮叶结点个数为n2,则有n0＝n2＋1
- 具有n个结点的完全⼆叉树的==深度k为log(n+1)==上取整
- 对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的顺序对所有节点从0开始编号，则对于序号为i的结点有：
若i>0，双亲序号：(i-1)/2；i=0，i为根结点编号，⽆双亲结点
若2i+1<n，左孩⼦序号：2i+1，否则⽆左孩⼦
若2i+2<n，右孩⼦序号：2i+2，否则⽆右孩⼦
4.二叉树的存储
⼆叉树的存储结构分为：顺序存储和类似于链表的链式存储。
⼆叉树的链式存储是通过⼀个⼀个的节点引⽤起来的，常⻅的表⽰⽅式有⼆叉和三叉表⽰⽅式
//孩子表示法classNode{int val;//数据域Node left;//左孩子的引用Node right;//右孩子的引用}//孩子双亲表示法classNode1{int val;//数据域Node left;//左孩子的引用Node right;//右孩子的引用Node parent;//当前节点的根节点}5.二叉树的基本操作
5.1手动创建二叉树
publicstaticclassNode{publicchar val;publicNode left;publicNode right;publicNode(char val){this.val = val;}}//根节点publicNodecreatTree(){NodeA=newNode('A');NodeB=newNode('B');NodeC=newNode('C');NodeD=newNode('D');NodeE=newNode('E');NodeF=newNode('F');NodeG=newNode('G');NodeH=newNode('H');A.left =B;A.right =C;B.left =D;B.right =E;E.right =H;C.left =F;C.right =G;returnA;}5.2 二叉树的遍历
1.前序遍历
访问顺序：根节点 → 左子树 → 右子树
//前序遍历publicvoidpreOrder(Node root){if(root ==null){return;}System.out.println(root.val);preOrder(root.left);preOrder(root.right);}2.中序遍历
访问顺序：左子树 → 根节点 → 右子树
//中序遍历publicvoidinOrder(Node root){if(root ==null){return;}preOrder(root.left);System.out.println(root.val);preOrder(root.right);}3.后序遍历
访问顺序：左子树 → 右子树 → 根节点
//后序遍历publicvoidpostOrder(Node root){if(root ==null){return;}preOrder(root.left);preOrder(root.right);System.out.println(root.val);}5.3 二叉树操作方法实现
//节点个数publicstaticint count =0;//获取节点个数publicvoidsize(Node root){if(root ==null){return;} count++;size(root.left);size(root.right);}//获取节点个数publicintsize2(Node root){if(root ==null){return0;}returnsize2(root.right)+size2(root.left)+1;}//获取叶子节点个数publicintgetleafNodeCount(Node root){if(root ==null){return0;}if(root.left ==null&&root.right ==null){return1;}returngetleafNodeCount(root.left)+getleafNodeCount(root.right);}//获取第k层节点个数publicintgetLevelNodeCount(Node root,int k){if(root ==null){return0;}if(k ==1){return1;}returngetLevelNodeCount(root.left,k-1)+getLevelNodeCount(root.right,k-1);}//获取二叉树高度publicintgetHight(Node root){if(root ==null){return0;}int leftH =getHight(root.left);int rightH =getHight(root.right);returnMath.max(leftH,rightH)+1;}//找val元素是否存在publicNodefind(Node root,char val){if(root ==null){returnnull;}if(root.val != val ){return root;}Node ret =find(root.left,val);if(ret !=null){return ret;}Node ret1 =find(root.right,val);if(ret !=null){return ret1;}returnnull;}}三、总结
树形结构是一种“一对多”的层级数据组织方式，而二叉树作为它的特殊形式（每个节点最多俩孩子），凭借满二叉树、完全二叉树等细分类型，以及明确的性质（比如节点数和层数的关系），成了实际开发中常用的结构。我们可以用不同方式存储二叉树，也能通过前/中/后序遍历“逛遍”树里的每个节点——掌握这些内容，不仅能理解数据的组织逻辑，也能为后续学更复杂的树结构（比如红黑树）打牢基础。
