首先什么是树结构?
树是一种描述非线性层次关系的数据结构,树是n个数据结点的集合,这些集结点包含一个根节点,根节点下有着互相不交叉的子集合,这些子集合便是根节点的子树。
树的特点
- 在一个树结构中,有且仅有一个结点没有直接前驱,它就是根节点。
- 除了根节点,其他结点有且只有一个直接前驱
- 每个结点可以有任意多个直接后继
树的名词解释
- 结点的度:一个结点包含子树的数量。
- 树的度:该树所有结点中最大的度。
- 兄弟结点:具有同一父结点的结点称为兄弟结点。
- 树的深度(高度):叶子结点的深度(高度)为1,根节点深度(高度)最高;
- 层数:从树根开始算,树根是第一层,以此类推。
- 森林:由多个树组成
只说干货,现在直接复习最重要的——二叉树
二叉树
二叉树是一种超级超级超级重要的数据结构!也是树表家族最为基础的结构
先看看定义:二叉树嘛,每个结点最多只能有二棵子树,二叉树的子树有左右之分,次序不能颠倒
再看看完全二叉树的性质:
- 第i层至多有 2的i次方减一 个结点
- 深度为k的二叉树至多有2k-1个结点
- 任意二叉树,度为0的节点数=度为2的节点数+1;
- 如果i为父亲的编号,则孩子的编号为2i和2i+1;
- 如果孩子编号为n,父亲结点编号为k/2,向下取整
关于树的度:
二叉树中连接节点和节点的线就是度
上面说过——度为0的节点数为度为2的节点数加1,即n0=n2+1
这个公式的推理方法如下:
设:
k:总度数
k+1:总节点数
n0:度为0的节点
n1:度为1的节点
n2:度为二的节点
根据二叉树中度和节点的守衡原理,可列出以下一组方程:
k=n2*2+n1;
k+1=n2+n1+n0;
根据方程可以求出n0=n2+1
基本概念不说,研究一下二叉树的遍历
二叉树的遍历
首先,我们看看前序、中序、后序遍历的特性:
前序遍历: (根——左——右)
1.访问根节点
2.前序遍历左子树
3.前序遍历右子树
中序遍历: (左——根——右)
1.中序遍历左子树
2.访问根节点
3.中序遍历右子树
后序遍历: (左——右——根)
1.后序遍历左子树
2.后序遍历右子树
3.访问根节点
要知道:
中序遍历是很重要的一个判断参照!如果只给我们前序遍历和后序遍历的结果,我们将无法推导出唯一的树。
给我们前序遍历和中序遍历,我们可以推出中序
给我们后序遍历和中序遍历,我们可以推出中序
好了,已经写了很多但是并没有拿出来什么真干货,接下来用代码写一下关于树的操作,这里先讲好——对于“树”这个运行结构,最重要的概念是“递归”,要想把树的概念理解好,必须先培养递归的思想。我向这篇文章:写递归函数的正确思想学习了一下,真的写的很棒,条理清晰而且有详有略。在这之后我就希望通过自己亲手敲代码的方式去学习,但是研究了两天,依然进展比较一般,最后通过研究各方博客的C代码,从而找到了思路。不再说废话了,这东西,必须通过自己动手敲才能有收获,好的接下来就要拿代码出来了。这里感谢这片文章二叉树题目实现
以下则是用java代码去写的,注解已经很详细,没有分开写,时不时有新体会也会去添加或修改:
二叉树类:
相关操作:
* 1.获取节点数 * 2.求深度 * 3. 前序遍历,中序遍历,后序遍历 * 4.分层遍历二叉树(按层次从上往下,从左往右) * 5.求二叉树第K层的节点个数 * 6.求二叉树中叶子节点的个数 * 7. 判断两棵二叉树是否结构相同
实现:
1 package com.myutil.tree1; 2 3 /* 4 * 1.获取节点数 5 * 2.求深度 6 * 3. 前序遍历,中序遍历,后序遍历 7 * 4.分层遍历二叉树(按层次从上往下,从左往右) 8 * 5.求二叉树第K层的节点个数 9 * 6.求二叉树中叶子节点的个数 10 * 7. 判断两棵二叉树是否结构相同 11 */ 12 import java.util.LinkedList; 13 import java.util.Queue; 14 15 class TreeNode{ 16 int key=0; 17 String data=null; 18 boolean isVisited=false; 19 20 TreeNode leftChild=null; 21 TreeNode rightChild=null; 22 23 public TreeNode(int key,String data) { 24 this.key=key; 25 this.data=data; 26 this.isVisited=false; 27 this.leftChild=null; 28 this.rightChild=null; 29 } 30 } 31 32 33 34 public class BinaryTree { 35 36 TreeNode root=null; 37 38 public BinaryTree() { 39 root=new TreeNode(1, "A"); 40 } 41 42 //创建二叉树bt,树由节点构成 43 public void createBinTree(TreeNode root) { 44 TreeNode newNodeB=new TreeNode(2, "B"); 45 TreeNode newNodeC=new TreeNode(3, "C"); 46 TreeNode newNodeD=new TreeNode(4, "D"); 47 TreeNode newNodeE=new TreeNode(5, "E"); 48 TreeNode newNodeF=new TreeNode(6, "F"); 49 50 root.leftChild=newNodeB; 51 root.rightChild=newNodeC; 52 root.leftChild.leftChild=newNodeD; 53 root.leftChild.rightChild=newNodeE; 54 root.rightChild.rightChild=newNodeF; 55 } 56 57 //创建二叉树bt2,树由结点构成 58 public void createBinTree2(TreeNode root){ 59 TreeNode newNodeB = new TreeNode(2,"B"); 60 TreeNode newNodeC = new TreeNode(3,"C"); 61 TreeNode newNodeD = new TreeNode(4,"D"); 62 TreeNode newNodeE = new TreeNode(5,"E"); 63 //填充它 64 root.leftChild = newNodeB; 65 root.rightChild = newNodeC; 66 root.leftChild.leftChild = newNodeD; 67 root.leftChild.rightChild = newNodeE; 68 } 69 70 71 //访问节点,输出节点,便于我们查看效果 72 public void visitNode(TreeNode node) { 73 System.out.println(node.data+" "); 74 } 75 76 77 //1.获取节点数 78 //递归解法: 79 //(1)如果二叉树为空,节点个数为0 80 //(2)如果二叉树不为空,二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1 81 public int size() { 82 return size(root); 83 } 84 85 //通过递归求size 86 public int size(TreeNode subtree) { 87 if (subtree==null) { 88 return 0; 89 }else { 90 return 1+size(subtree.leftChild)+size(subtree.rightChild); 91 } 92 } 93 94 //2.求深度 95 //递归解法: 96 //(1)如果二叉树为空,二叉树的深度为0 97 //(2)如果二叉树不为空,二叉树的深度 = max(左子树深度, 右子树深度) + 1 98 public int getDepth(TreeNode root) { 99 if (root==null) { 100 return 0; 101 }else { 102 int depthLeft=getDepth(root.leftChild); 103 int depthRight=getDepth(root.rightChild); 104 return depthLeft>depthRight?(depthLeft+1):(depthRight+1); 105 } 106 } 107 108 //3. 前序遍历,中序遍历,后序遍历 109 //a.前序遍历 110 //前序遍历递归解法: 111 //(1)如果二叉树为空,空操作 112 //(2)如果二叉树不为空,访问根节点,前序遍历左子树,前序遍历右子树 113 public void preOrderTraverse(TreeNode root) { 114 if (root!=null) { 115 visitNode(root); 116 preOrderTraverse(root.leftChild); 117 preOrderTraverse(root.rightChild); 118 } 119 } 120 121 //b.中序遍历 122 //中序遍历递归解法 123 //(1)如果二叉树为空,空操作。 124 //(2)如果二叉树不为空,中序遍历左子树,访问根节点,中序遍历右子树 125 126 public void inOrderTraverse(TreeNode root) { 127 if (root!=null) { 128 inOrderTraverse(root.leftChild); 129 visitNode(root); 130 inOrderTraverse(root.rightChild); 131 } 132 } 133 134 //c.后序遍历 135 //后序遍历递归解法 136 //(1)如果二叉树为空,空操作。 137 //(2)如果二叉树不p为空,后序遍历左子树,后序遍历右子树,访问根节点, 138 public void postOrderTraverse(TreeNode root) { 139 if (root!=null) { 140 postOrderTraverse(root.leftChild); 141 postOrderTraverse(root.rightChild); 142 visitNode(root); 143 } 144 } 145 146 //4.分层遍历二叉树(按层次从上往下,从左往右) 147 //相当于广度优先搜索,使用队列实现。队列初始化,将根节点压入队列。 148 //当队列不为空,进行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。 149 public void levelTraverse(TreeNode root) { 150 if (root==null) { 151 return; 152 } 153 Queue<TreeNode> queue=new LinkedList<>(); 154 //让根节点入队(队列:先进先出) 155 queue.offer(root); 156 while (!queue.isEmpty()) { 157 //让元素出队 158 TreeNode node=queue.poll(); 159 //访问它 这里就是用visit方法输出看效果~~ 160 visitNode(node); 161 if (node.leftChild!=null) { 162 queue.offer(node.leftChild); 163 } 164 if (node.rightChild!=null) { 165 queue.offer(node.rightChild); 166 } 167 } 168 return; 169 } 170 171 //5.求二叉树第K层的节点个数 172 //递归解法: 173 //(1)如果二叉树为空或者k<1返回0 174 //(2)如果二叉树不为空并且k==1,返回1 175 //(3)如果二叉树不为空且k>1,返回左子树中k-1层的节点个数与右子树k-1层节点个数之和 176 public int getNodeNumKthLevel(TreeNode root,int k) { 177 if (root==null||k<1) { 178 return 0; 179 }else if (k==1) { 180 return 1; 181 }else { 182 int leftNum=getNodeNumKthLevel(root.leftChild, k-1); 183 int rightNum=getNodeNumKthLevel(root.rightChild, k-1); 184 return leftNum+rightNum; 185 } 186 } 187 188 //6.求二叉树中叶子节点的个数 189 // 递归解法: 190 //(1)如果二叉树为空,返回0 191 //(2)如果二叉树不为空且左右子树为空,返回1 192 //(3)如果二叉树不为空,且左右子树不同时为空,返回左子树中叶子节点个数加上右子树中叶子节点个数 193 public int getLeafNodeNum(TreeNode root) { 194 if (root==null) { 195 return 0; 196 }else if (root.leftChild==null&&root.rightChild==null) { 197 return 1; 198 }else { 199 int leftNum=getLeafNodeNum(root.leftChild); 200 int rightNum=getLeafNodeNum(root.rightChild); 201 return leftNum+rightNum; 202 } 203 } 204 205 206 //7. 判断两棵二叉树是否结构相同 207 //不考虑数据内容。结构相同意味着对应的左子树和对应的右子树都结构相同。 208 //递归解法: 209 //(1)如果两棵二叉树都为空,返回真 210 //(2)如果两棵二叉树一棵为空,另一棵不为空,返回假 211 //(3)如果两棵二叉树都不为空,如果对应的左子树和右子树都同构返回真,其他返回假 212 public boolean StructureCmp(TreeNode root1,TreeNode root2) { 213 if (root1==null&&root2==null) { 214 return true; 215 }else if (root1==null||root2==null) { 216 return false; 217 }else { 218 boolean leftResult=StructureCmp(root1.leftChild, root2.leftChild); 219 boolean rightResult=StructureCmp(root1.rightChild, root2.rightChild); 220 return leftResult&&rightResult; 221 } 222 } 223 }
测试类:
1 package com.myutil.tree1; 2 3 public class Main { 4 public static void main(String[] args) { 5 BinaryTree bt = new BinaryTree(); 6 BinaryTree bt2 = new BinaryTree(); 7 /* 8 由初始化的时候可知:我创建了一个这样的树,供查看写的方法是否正确 9 这棵树起名为bt: 这棵树起名为bt2 供比较 10 A A 11 / \ / \ 12 B C B C 13 /\ \ /\ 14 D E F D E 15 */ 16 bt.createBinTree(bt.root); 17 bt2.createBinTree2(bt2.root); 18 19 //1.看结点数 20 System.out.println("1.树的结点个数为:" + bt.size(bt.root)); 21 //2.看深度 22 System.out.println("2.树的深度为:"+bt.getDepth(bt.root)); 23 //3. 前序遍历,中序遍历,后序遍历 24 System.out.print("3-1.先序遍历:"); 25 bt.preOrderTraverse(bt.root); 26 System.out.println(); 27 28 29 System.out.print("3-2.中序遍历:"); 30 bt.inOrderTraverse(bt.root); 31 System.out.println(); 32 33 System.out.print("3-3.后序遍历:"); 34 bt.postOrderTraverse(bt.root); 35 System.out.println(); 36 37 //4.将二叉树用层次遍历 38 System.out.print("4.二叉树层次遍历:"); 39 bt.levelTraverse(bt.root); 40 System.out.println(); 41 42 //5.二叉树K层有多少个结点:由上图绘制可知:0层没有,1层有一个根节点,第二层有俩,第三次有仨 43 System.out.println("5.二叉树K层结点个数:"); 44 System.out.println(" 当K=0时有"+bt.getNodeNumKthLevel(bt.root,0)+"个结点"); 45 System.out.println(" 当K=1时有"+bt.getNodeNumKthLevel(bt.root,1)+"个结点"); 46 System.out.println(" 当K=2时有"+bt.getNodeNumKthLevel(bt.root,2)+"个结点"); 47 System.out.println(" 当K=3时有"+bt.getNodeNumKthLevel(bt.root,3)+"个结点"); 48 49 //6.求二叉树中叶子节点的个数 50 System.out.print("6.二叉树叶子节点个数:"); 51 System.out.println(bt.getLeafNodeNum(bt.root)); 52 53 //7.比较两个二叉树相不相同 54 System.out.println("7.测试两树结构是否相同:"); 55 System.out.println(" b1和b1:"+bt.StructureCmp(bt.root,bt.root)); 56 System.out.println(" b1和b2:"+bt.StructureCmp(bt.root,bt2.root)); 57 } 58 }
相关连接:轻松搞定面试中的二叉树题目
java数据结构与算法之树基本概念及二叉树(BinaryTree)的设计与实现