Java-二叉树

一、概念1、核心定义节点的度一个节点拥有的子节点个数。叶子节点度为 0没有左右孩子的节点。根节点整棵树最顶层、没有双亲的唯一节点。层数根节点默认第 1 层往下依次累加。深度从根往下走到该节点的层数。高度从该节点往下走到最远叶子的层数整棵二叉树的高度 根节点的高度2、特殊的二叉树满二叉树每一层节点全部铺满所有叶子都在最底层所有非叶子节点都有左右两个孩子。完全二叉树前 h-1 层全满最后一层节点从左到右连续排列中间不能空。3、性质1规定根节点的层数为1则第 k 层最多有2^k-1个节点2规定只有根节点的二叉树深度为1则高度为 h 的二叉树最多总节点2^h-13任意二叉树叶子数n0度为 2 节点数n2n0n214一个n个节点的树有n-1条边5对具有n个节点的完全二叉树的深度为log2n1上取整6完全二叉树编号节点 i 的左孩子2i节点 i 的右孩子2i1节点 i 的双亲i/2向下取整二、二叉树二叉树不存在度大于2的节点有左右之分次序不能颠倒是有序树1、二叉树的存储顺序存储、链式存储类似链表2、二叉树的基本操作前序遍历根 → 左 → 右ABDECFG中序遍历左 → 根 → 右DBEAFCG后序遍历左 → 右 → 根DEBFGCA层序遍历按层次从上到下、同层从左到右用队列实现3、平衡二叉树任意一个节点的左右子树高度差的绝对值不超过 1是二叉树不是二叉树4、模拟实现package BinaryTree; public class TestBinaryTree { static class TreeNode{ public char val; public TreeNode left; public TreeNode right; public TreeNode(char val){ this.valval; } } public TreeNode createTree(){ TreeNode Anew TreeNode(A); TreeNode Bnew TreeNode(B); TreeNode Cnew TreeNode(C); TreeNode Dnew TreeNode(D); TreeNode Enew TreeNode(E); TreeNode Fnew TreeNode(F); TreeNode Gnew TreeNode(G); TreeNode Hnew TreeNode(H); A.leftB;A.rightC; B.leftD;B.rightE; C.leftF;C.rightG; E.rightH; return A; } //前序遍历 public void preOder(TreeNode root){ if(rootnull){ return; } System.out.print(root.val ); preOder(root.left); preOder(root.right); } //中序遍历 public void inOder(TreeNode root){ if(rootnull){ return; } inOder(root.left); System.out.print(root.val ); inOder(root.right); } //后序遍历 public void postOder(TreeNode root){ if(rootnull){ return; } postOder(root.left); postOder(root.right); System.out.print(root.val ); } //节点个数 public int size1(TreeNode root){ if(rootnull){ return 0; } return size1(root.left)size1(root.right)1; } public static int nodeSize0; //my public int size2(TreeNode root){ if(rootnull){ return 0; } nodeSize; size2(root.left); size2(root.right); return nodeSize; } //叶子结点个数 public int leafSize0; //my public int getLeafNodeCount1(TreeNode root){ if(rootnull){ return 0; } if(root.leftnullroot.rightnull){ leafSize; } getLeafNodeCount1(root.left); getLeafNodeCount1(root.right); return leafSize; } public int getLeafNodeCount2(TreeNode root){ if(rootnull){ return 0; } if(root.leftnullroot.rightnull){ return 1; } return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right); } //第k层有多少个节点 //根节点为第一层 public int getKLevelNodeCount(TreeNode root,int k){ if(rootnull){ return 0; } if(k1){ return 1; } return getKLevelNodeCount(root.left,k-1) getKLevelNodeCount(root.right,k-1); } //获取二叉树高度 //my public int getHeight1(TreeNode root){ int nsize1(root); int ret(int)(Math.log(n1)/Math.log(2))1; return ret; } public int getHeight2(TreeNode root){ //max(左树高度右树高度)1 if(rootnull){ return 0; } int leftHeightgetHeight2(root.left); int rightHeightgetHeight2(root.right); return leftHeightrightHeight? leftHeight1:rightHeight1; } //遍历二叉树找到val所在的节点 public TreeNode find(TreeNode root,char val){ if(rootnull){ return null; } if(root.valval){ return root; } TreeNode retfind(root.left,val); if(ret!null){ return ret; } retfind(root.right,val); if(ret!null){ return ret; } return null; } }