树形结构：树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。 特点：有一个特殊的节点，称为根节点，根节点没有前驱节点 除根节点外，其余节点被分成M(M > 0)个互不相交的集合T1、T2、…、Tm，其中每一个集合 Ti (1 <= i<= m) 又是一棵与树类似的子树。每棵子树的根节点有且只有一个前驱，可以有0个或多个后继，树是递归定义的。 节点的度：一个节点含有的子树的个数称为该节点的度。 树的度：一棵树中，最大的节点的度称为树的度； 叶子节点或终端节点：度为0的节点称为叶节点； 双亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点； 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点； 根结点：一棵树中，没有双亲结点的结点； 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推； 树的高度或深度：树中节点的最大层次； 二叉树特点：1. 每个结点最多有两棵子树，即二叉树不存在度大于 2 的结点。 2. 二叉树的子树有左右之分，其子树的次序不能颠倒，因此二叉树是有序树。 特殊的二叉树：. . 1**.满二叉树**: 一个二叉树，如果每一个层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果 一个二叉树的层数为K，且结点总数是 ，则它就是满二叉树。 3. 完全二叉树: 完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。 要注意的是满二叉树是一种特殊的完全二叉树。 4. 二叉树的性质：1. 若规定根节点的层数为1，则一棵非空二叉树的第i层上最多有 (i>0)个结点。 2. 若规定只有根节点的二叉树的深度为1，则深度为K的二叉树的最大结点数是 (k>=0) 3. 对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0＝n2＋1。 4. 具有n个结点的完全二叉树的深度k为 上取整。 5. 对于具有n个结点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号，则对于序号为i 的结点有： 若i>0，双亲序号：(i-1)/2；i=0，i为根节点编号，无双亲节点 若2i+1<n，左孩子序号：2i+1，否则无左孩子 若2i+2<n，右孩子序号：2i+2，否则无右孩子 二叉树的前序中序后序遍历代码：
public class TreeTraversal { public static void preTraversal(TreeNode root){ if(root!=null){ //前序 System.out.printf("%c",root.v); preTraversal(root.left); preTraversal(root.right); } } public static void inTraversal(TreeNode root){ if(root!=null){ //后序 inTraversal(root.left); System.out.printf("%c",root.v); inTraversal(root.right); } } public static void postTraversal(TreeNode root){ if(root!=null){ //后序 postTraversal(root.left); postTraversal(root.right); System.out.printf("%c",root.v); } } public static void main(String[] args) { TreeNode a=BuildTree.buildTree(); System.out.printf("前序遍历: "); preTraversal(a); System.out.println(); System.out.printf("中序遍历: "); inTraversal(a); System.out.println(); System.out.printf("后序遍历: "); postTraversal(a); System.out.println(); } }// 遍历思路-求结点个数；void getSize1(Node root); // 子问题思路-求结点个数；int getSize2(Node root); // 遍历思路-求叶子结点个数；void getLeafSize1(Node root); // 子问题思路-求叶子结点个数；int getLeafSize2(Node root); // 子问题思路-求第 k 层结点个数；int getKLevelSize(Node root); // 获取二叉树的高度；int getHeight(Node root); // 查找 val 所在结点；Node find(Node root, int val);
public class SomeMethod { private static int n; public static int sumTreeNodeSize(TreeNode root){ //求树的节点采用遍历思路 n=0; preOrder(root); return n; } public static int sumTreeNodeSize2(TreeNode root){ // 求树的节点采用汇集思路 if(root==null){ return 0; }else{ int nodeRootSize=1; int leftSubNodeSize=sumTreeNodeSize2(root.left); int rightSubNodeSize=sumTreeNodeSize2(root.right); return nodeRootSize+leftSubNodeSize+rightSubNodeSize;//根+左子树+右子树 } } private static void preOrder(TreeNode root) { if(root!=null){ n++; // 遍历这个过程会经过每个节点 preOrder(root.left); preOrder(root.right); } } private static int leafN; private static int sumTreeLeafNodeSize(TreeNode root){ //求树中叶子节点个数采用遍历思路 // 注意，每次计算叶子结点个数之前，都必须归零 leafN = 0; // 2. 使用前序遍历方式，经过每一个结点 preOrder2(root); return leafN; } private static int sumTreeLeafNodeSize2(TreeNode root){//求树中叶子节点个数采用汇集思路 if(root==null){ return 0; // 空树 }else if(root.left==null&&root.right==null){ return 1; //只有一个结点 }else{ // 至少一个以上的结点 // 整棵树的叶子结点个数 = 左子树的叶子节点个数 + 右子树的叶子结点个数 int leftSubTreeLeafSize = sumTreeLeafNodeSize2(root.left); int rightSubTreeLeafSize = sumTreeLeafNodeSize2(root.right); return leftSubTreeLeafSize + rightSubTreeLeafSize; } } private static void preOrder2(TreeNode root) { if(root!=null){ if(root.left==null&&root.right==null){ leafN++; } preOrder2(root.left); preOrder2(root.right); } } public static int sumKLevelNodeSize(TreeNode root, int k){ //求第k层节点个数 if(root==null){ return 0; }else if(k==1){ return 1; }else{ int leftSumK_1=sumKLevelNodeSize(root.left,k-1); int rightSumK_1=sumKLevelNodeSize(root.right,k-1); return leftSumK_1+rightSumK_1; } } public static int getHeight(TreeNode root){ //获取树的高度 if(root==null){ return 0; }else if(root.left==null&&root.right==null){ return 1; }else{ int leftSubTreeHeight = getHeight(root.left); int rightSubTreeHeight = getHeight(root.right); return Math.max(leftSubTreeHeight,rightSubTreeHeight)+1; } } public static boolean contains2(TreeNode root, int v){ //树中是否包含v 思路：三个大思路：一空树 // 二 判断根中节点是否为v if(root==null){ //三 根中节点部位不为v，先判断左树，在判断右树 return false; // 注意 若左树有不用判断右树 } if(root.v==v){ return true; } boolean left = contains2(root.left, v); if (left) { return true; } return contains2(root.right, v); } public static boolean contains1(TreeNode root, int v) { if (root == null) { // 空树 return false; } else { if (root.v == v) { // 根里找到了 // 没必要再去左右子树找了 return true; } else { // 根里没找到 boolean leftSubTreeContains = contains1(root.left, v); if (leftSubTreeContains) { // 左子树里找到了 // 没必要再去右子树里找了 return true; } else { // 左子树里也没找到 boolean rightSubTreeContains = contains1(root.right, v); if (rightSubTreeContains) { // 右子树里找到了 return true; } else { return false; } } } } } public static TreeNode contains4(TreeNode root, int v){ if(root==null){ return null; } if(root.v==v){ return root; } TreeNode leftTreeNode = contains4(root.left, v); if(leftTreeNode!=null){ return leftTreeNode; } return contains4(root.right,v); } public static boolean contains3(TreeNode root, TreeNode node){ if(root==null){ return false; } if(root==node){ return true; } boolean leftTreeNode = contains3(root.left, node); if(leftTreeNode){ return true; } return contains3(root.right, node); } public static void main(String[] args) { TreeNode root=BuildTree.buildTree(); int sum=sumTreeNodeSize2(root); System.out.println(sum); int sumLeaf=sumTreeLeafNodeSize2(root); System.out.println(sumLeaf); int sumK=sumKLevelNodeSize(root,4); System.out.println(sumK); int heightTree=getHeight(root); System.out.println(heightTree); System.out.println(contains2(root,'A')); TreeNode a=contains4(root,'B'); System.out.println(a); } }二叉树的层序遍历，判断完全二叉树（层序遍历应用） 带层级的层序遍历代码
public class TreeLevelOrder { public static void levelOrderTraversal(TreeNode root){ if(root==null){ return; } //队列元素的元素是树的结点 Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); while (!queue.isEmpty()){ //把树的结点拖入队列在删除时候在托入他的左右孩子 以此循环 TreeNode node = queue.remove(); System.out.println(node.val); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } } public static boolean isCompleteTree(TreeNode root){ Queue<TreeNode> queue=new LinkedList<>(); queue.add(root); while (true){ TreeNode node = queue.remove(); if(node==null){ break; } queue.add(node.left); queue.add(node.right); } while (!queue.isEmpty()){ TreeNode node = queue.remove(); if(node==null){ } else{ return false; } } return true; } static class Nl{ int level; TreeNode node; public Nl(TreeNode node, int level) { this.level = level; this.node = node; } } public static void levelOrderWithLevel(TreeNode root){ if(root==null){ return; } Queue<Nl> queue=new LinkedList<>(); queue.add(new Nl(root,1)); while (!queue.isEmpty()){ Nl nl = queue.remove(); TreeNode node=nl.node; int level= nl.level; System.out.println(level); System.out.println(node.val); if (node.left != null) { queue.add(new Nl(node.left, level + 1)); } if (node.right != null) { queue.add(new Nl(node.right, level + 1)); } } } public static void main(String[] args) { TreeNode root=BuildTree.BuildTree1(); levelOrderTraversal(root); System.out.println(isCompleteTree(root)); levelOrderWithLevel(root); } }前中后序遍历非递归实现
public class FeiDiGui { public static void preOrder(TreeNode node){ Deque<TreeNode> stack=new LinkedList<>(); TreeNode current=node; while (!stack.isEmpty()||current!=null){ while (current!=null){ System.out.println(current.v); stack.push(current); current=current.left; } TreeNode top = stack.pop(); current=top.right; } } public static void main(String[] args) { TreeNode root=BuildTree.buildTree(); preOrder(root); System.out.println("-------------"); inOrder(root); System.out.println("-------------"); postOrder(root); } public static void inOrder(TreeNode node){ Deque<TreeNode> stack=new LinkedList<>(); TreeNode current=node; while (!stack.isEmpty()||current!=null){ while (current!=null){ stack.push(current); current=current.left; } TreeNode top = stack.pop(); System.out.println(top.v); current=top.right; } } public static void postOrder(TreeNode node){ Deque<TreeNode> stack=new LinkedList<>(); TreeNode current=node; TreeNode last=null; while (!stack.isEmpty()||current!=null){ while (current!=null){ System.out.println(current.v); stack.push(current); current=current.left; } TreeNode top = stack.peek(); if(top.right==null){ stack.pop(); last=top; System.out.println(top.v); } else if (top.right == last) { // 第三次经过 top // 说明从右子树回来 stack.pop(); last = top; System.out.println(top.v); } else { // 第二次经过 top // 说明从左子树回来的 current = top.right; } } } }