二叉树树的概念树是⼀种非线性的数据结构它是由nn0个有限结点组成⼀个具有层次关系的集合树的特点有⼀个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、…、Tm其中每⼀个集合Ti(1 i m)⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有0个或多个后继树是递归定义的【注意】树形结构中⼦树之间不能有交集否则就不是树形结构相关概念结点的度一个结点含有子树的个数称为该结点的度如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度如上图树的度为6叶子结点或终端结点度为0的结点称为叶结点如上图B、C、H、I.等节点为叶结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次如上图树的高度为4非终端结点或分支结点度不为0的结点如上图D、E、F、G.等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林二叉树一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成二叉树的模拟实现二叉树接口packageDataStructure.DS_BinaryTree;publicinterfaceITree{/** * 判断是否为完全二叉树 * param root 根节点 * return true 完全二叉树 */booleanisCompleteBinaryTree(TreeNoderoot);/** * 根据值查找节点 * param root 根 * param val 待查找值 * return 找到的TreeNodenull未找到 */TreeNodefind(TreeNoderoot,intval);/** * 获取树高度 * param root 根 * return 高度 */intgetHeight(TreeNoderoot);/** * 获取第k层节点数量 * param root 根 * param k 层数从1开始 * return 节点数 */intgetKLevelNodeCount(TreeNoderoot,intk);/** * 获取叶子结点个数 * param root 根 * return 叶子数量 */intgetLeafNodeCount(TreeNoderoot);/** * 二叉树总节点个数 * param root 根 * return 总节点数 */intsize(TreeNoderoot);/** * 先序遍历 * param root 根 */voidpreOrderTraverse(TreeNoderoot);/** * 中序遍历 * param root 根 */voidinOrderTraverse(TreeNoderoot);/** * 后序遍历 * param root 根 */voidpostOrderTraverse(TreeNoderoot);/** * 层序遍历 * param root 根 */voidlevelOrderTraverse(TreeNoderoot);}二叉树的功能前序遍历/** * 先序遍历根 - 左 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(rootnull)return;System.out.print(root.data );preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}中序遍历/** * 中序遍历左 - 根 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(rootnull)return;inOrderTraverse(root.lchild);System.out.print(root.data );inOrderTraverse(root.rchild);}后序遍历/** * 后序遍历左 - 右 - 根 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(rootnull)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data );}层序遍历/** * 层序遍历广度优先遍历 * 使用队列完成从上到下同一层从左到右打印 * param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.data );// 左孩子不为空入队if(cur.lchild!null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!null)queue.offer(cur.rchild);}}获取树中节点的个数/** * 统计二叉树结点总个数 * param root 根节点 * return 全部节点数量空树返回0 */publicintsize(TreeNoderoot){if(rootnull)return0;// 当前节点1个 左子树节点数 右子树节点数return1size(root.lchild)size(root.rchild);}获取叶⼦节点的个数/** * 获取叶子结点的个数 * 叶子节点左右孩子都为null的节点 * param root 根节点 * return 叶子节点总数空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(rootnull)return0;// 当前是叶子节点计数1if(root.lchildnullroot.rchildnull)return1;// 左子树叶子 右子树叶子returngetLeafNodeCount(root.lchild)getLeafNodeCount(root.rchild);}获取第K层节点的个数/** * 获取第K层的节点个数层数从1开始 * param root 根节点 * param k 目标层数k1 * return 第k层节点数量root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(rootnull||k0)return0;// k1代表当前就是目标层节点数为1if(k1)return1;// 左子树k-1层 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)getKLevelNodeCount(root.rchild,k-1);}获取⼆叉树的⾼度/** * 获取二叉树的高度深度 * 递归当前树高度 max(左子树高度,右子树高度) 1 * param root 根节点 * return 树的高度空树返回0 */publicintgetHeight(TreeNoderoot){if(rootnull)return0;intleftHeightgetHeight(root.lchild);intrightHeightgetHeight(root.rchild);returnMath.max(leftHeight,rightHeight)1;}检测值为value的元素是否存在/** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * param root 根节点 * param val 需要查找的目标数值 * return 找到返回对应TreeNode找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件当前节点为空if(rootnull)returnnull;// 当前节点就是目标节点直接返回if(root.dataval)returnroot;// 递归查找左子树TreeNodeleftfind(root.lchild,val);// 左子树找到直接返回if(left!null)returnleft;// 左子树没找到去右子树查找returnfind(root.rchild,val);}判断⼀棵树是不是完全⼆叉树/** * 判断一棵树是否为完全二叉树 * 思路层序遍历遇到null节点后后续不能再出现非null节点 * param root 二叉树根节点 * return true是完全二叉树false不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(rootnull)returntrue;QueueTreeNodequenewLinkedList();que.offer(root);// 标记是否已经遇到空节点booleanflagfalse;while(!que.isEmpty()){TreeNodenodeque.poll();if(nodenull){// 遇到空节点置标记为trueflagtrue;}else{// 如果之前已经遇到过null现在又出现非空节点说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}二叉树模拟实现完整代码packageDataStructure.DS_BinaryTree;importjava.util.LinkedList;importjava.util.Queue;/** * 二叉树基础实现类 * 提供二叉树遍历、统计节点、高度、查找、判断完全二叉树等基础功能 */publicclassMyBinaryTree{/** * 判断一棵树是否为完全二叉树 * 思路层序遍历遇到null节点后后续不能再出现非null节点 * param root 二叉树根节点 * return true是完全二叉树false不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(rootnull)returntrue;QueueTreeNodequenewLinkedList();que.offer(root);// 标记是否已经遇到空节点booleanflagfalse;while(!que.isEmpty()){TreeNodenodeque.poll();if(nodenull){// 遇到空节点置标记为trueflagtrue;}else{// 如果之前已经遇到过null现在又出现非空节点说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}/** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * param root 根节点 * param val 需要查找的目标数值 * return 找到返回对应TreeNode找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件当前节点为空if(rootnull)returnnull;// 当前节点就是目标节点直接返回if(root.dataval)returnroot;// 递归查找左子树TreeNodeleftfind(root.lchild,val);// 左子树找到直接返回if(left!null)returnleft;// 左子树没找到去右子树查找returnfind(root.rchild,val);}/** * 获取二叉树的高度深度 * 递归当前树高度 max(左子树高度,右子树高度) 1 * param root 根节点 * return 树的高度空树返回0 */publicintgetHeight(TreeNoderoot){if(rootnull)return0;intleftHeightgetHeight(root.lchild);intrightHeightgetHeight(root.rchild);returnMath.max(leftHeight,rightHeight)1;}/** * 获取第K层的节点个数层数从1开始 * param root 根节点 * param k 目标层数k1 * return 第k层节点数量root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(rootnull||k0)return0;// k1代表当前就是目标层节点数为1if(k1)return1;// 左子树k-1层 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)getKLevelNodeCount(root.rchild,k-1);}/** * 获取叶子结点的个数 * 叶子节点左右孩子都为null的节点 * param root 根节点 * return 叶子节点总数空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(rootnull)return0;// 当前是叶子节点计数1if(root.lchildnullroot.rchildnull)return1;// 左子树叶子 右子树叶子returngetLeafNodeCount(root.lchild)getLeafNodeCount(root.rchild);}/** * 统计二叉树结点总个数 * param root 根节点 * return 全部节点数量空树返回0 */publicintsize(TreeNoderoot){if(rootnull)return0;// 当前节点1个 左子树节点数 右子树节点数return1size(root.lchild)size(root.rchild);}/** * 先序遍历根 - 左 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(rootnull)return;System.out.print(root.data );preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}/** * 中序遍历左 - 根 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(rootnull)return;inOrderTraverse(root.lchild);System.out.print(root.data );inOrderTraverse(root.rchild);}/** * 后序遍历左 - 右 - 根 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(rootnull)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data );}/** * 层序遍历广度优先遍历 * 使用队列完成从上到下同一层从左到右打印 * param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.data );// 左孩子不为空入队if(cur.lchild!null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!null)queue.offer(cur.rchild);}}}
二叉树树的概念树是⼀种非线性的数据结构它是由nn0个有限结点组成⼀个具有层次关系的集合树的特点有⼀个特殊的结点称为根结点根结点没有前驱结点除根结点外其余结点被分成M(M0)个互不相交的集合T1、T2、…、Tm其中每⼀个集合Ti(1 i m)⼜是⼀棵与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱可以有0个或多个后继树是递归定义的【注意】树形结构中⼦树之间不能有交集否则就不是树形结构相关概念结点的度一个结点含有子树的个数称为该结点的度如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度如上图树的度为6叶子结点或终端结点度为0的结点称为叶结点如上图B、C、H、I.等节点为叶结点双亲结点或父结点若一个结点含有子结点则这个结点称为其子结点的父结点如上图A是B的父结点孩子结点或子结点一个结点含有的子树的根结点称为该结点的子结点如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次如上图树的高度为4非终端结点或分支结点度不为0的结点如上图D、E、F、G.等节点为分支结点兄弟结点具有相同父结点的结点互称为兄弟结点如上图B、C是兄弟结点堂兄弟结点双亲在同一层的结点互为堂兄弟如上图H、I互为兄弟结点结点的祖先从根到该结点所经分支上的所有结点如上图A是所有结点的祖先子孙以某结点为根的子树中任一结点都称为该结点的子孙。如上图所有结点都是A的子孙森林由mm0棵互不相交的树组成的集合称为森林二叉树一棵二叉树是结点的一个有限集合该集合或者为空或者是由一个根节点加上两棵别称为左子树和右子树的二叉树组成二叉树的模拟实现二叉树接口packageDataStructure.DS_BinaryTree;publicinterfaceITree{/** * 判断是否为完全二叉树 * param root 根节点 * return true 完全二叉树 */booleanisCompleteBinaryTree(TreeNoderoot);/** * 根据值查找节点 * param root 根 * param val 待查找值 * return 找到的TreeNodenull未找到 */TreeNodefind(TreeNoderoot,intval);/** * 获取树高度 * param root 根 * return 高度 */intgetHeight(TreeNoderoot);/** * 获取第k层节点数量 * param root 根 * param k 层数从1开始 * return 节点数 */intgetKLevelNodeCount(TreeNoderoot,intk);/** * 获取叶子结点个数 * param root 根 * return 叶子数量 */intgetLeafNodeCount(TreeNoderoot);/** * 二叉树总节点个数 * param root 根 * return 总节点数 */intsize(TreeNoderoot);/** * 先序遍历 * param root 根 */voidpreOrderTraverse(TreeNoderoot);/** * 中序遍历 * param root 根 */voidinOrderTraverse(TreeNoderoot);/** * 后序遍历 * param root 根 */voidpostOrderTraverse(TreeNoderoot);/** * 层序遍历 * param root 根 */voidlevelOrderTraverse(TreeNoderoot);}二叉树的功能前序遍历/** * 先序遍历根 - 左 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(rootnull)return;System.out.print(root.data );preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}中序遍历/** * 中序遍历左 - 根 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(rootnull)return;inOrderTraverse(root.lchild);System.out.print(root.data );inOrderTraverse(root.rchild);}后序遍历/** * 后序遍历左 - 右 - 根 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(rootnull)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data );}层序遍历/** * 层序遍历广度优先遍历 * 使用队列完成从上到下同一层从左到右打印 * param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.data );// 左孩子不为空入队if(cur.lchild!null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!null)queue.offer(cur.rchild);}}获取树中节点的个数/** * 统计二叉树结点总个数 * param root 根节点 * return 全部节点数量空树返回0 */publicintsize(TreeNoderoot){if(rootnull)return0;// 当前节点1个 左子树节点数 右子树节点数return1size(root.lchild)size(root.rchild);}获取叶⼦节点的个数/** * 获取叶子结点的个数 * 叶子节点左右孩子都为null的节点 * param root 根节点 * return 叶子节点总数空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(rootnull)return0;// 当前是叶子节点计数1if(root.lchildnullroot.rchildnull)return1;// 左子树叶子 右子树叶子returngetLeafNodeCount(root.lchild)getLeafNodeCount(root.rchild);}获取第K层节点的个数/** * 获取第K层的节点个数层数从1开始 * param root 根节点 * param k 目标层数k1 * return 第k层节点数量root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(rootnull||k0)return0;// k1代表当前就是目标层节点数为1if(k1)return1;// 左子树k-1层 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)getKLevelNodeCount(root.rchild,k-1);}获取⼆叉树的⾼度/** * 获取二叉树的高度深度 * 递归当前树高度 max(左子树高度,右子树高度) 1 * param root 根节点 * return 树的高度空树返回0 */publicintgetHeight(TreeNoderoot){if(rootnull)return0;intleftHeightgetHeight(root.lchild);intrightHeightgetHeight(root.rchild);returnMath.max(leftHeight,rightHeight)1;}检测值为value的元素是否存在/** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * param root 根节点 * param val 需要查找的目标数值 * return 找到返回对应TreeNode找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件当前节点为空if(rootnull)returnnull;// 当前节点就是目标节点直接返回if(root.dataval)returnroot;// 递归查找左子树TreeNodeleftfind(root.lchild,val);// 左子树找到直接返回if(left!null)returnleft;// 左子树没找到去右子树查找returnfind(root.rchild,val);}判断⼀棵树是不是完全⼆叉树/** * 判断一棵树是否为完全二叉树 * 思路层序遍历遇到null节点后后续不能再出现非null节点 * param root 二叉树根节点 * return true是完全二叉树false不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(rootnull)returntrue;QueueTreeNodequenewLinkedList();que.offer(root);// 标记是否已经遇到空节点booleanflagfalse;while(!que.isEmpty()){TreeNodenodeque.poll();if(nodenull){// 遇到空节点置标记为trueflagtrue;}else{// 如果之前已经遇到过null现在又出现非空节点说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}二叉树模拟实现完整代码packageDataStructure.DS_BinaryTree;importjava.util.LinkedList;importjava.util.Queue;/** * 二叉树基础实现类 * 提供二叉树遍历、统计节点、高度、查找、判断完全二叉树等基础功能 */publicclassMyBinaryTree{/** * 判断一棵树是否为完全二叉树 * 思路层序遍历遇到null节点后后续不能再出现非null节点 * param root 二叉树根节点 * return true是完全二叉树false不是完全二叉树 */publicbooleanisCompleteBinaryTree(TreeNoderoot){// 空树认为是完全二叉树if(rootnull)returntrue;QueueTreeNodequenewLinkedList();que.offer(root);// 标记是否已经遇到空节点booleanflagfalse;while(!que.isEmpty()){TreeNodenodeque.poll();if(nodenull){// 遇到空节点置标记为trueflagtrue;}else{// 如果之前已经遇到过null现在又出现非空节点说明不是完全二叉树if(flag)returnfalse;// 无论孩子是否为null全部入队que.offer(node.lchild);que.offer(node.rchild);}}returntrue;}/** * 在二叉树中查找值为val的节点 * 先序递归遍历查找 * param root 根节点 * param val 需要查找的目标数值 * return 找到返回对应TreeNode找不到返回null */publicTreeNodefind(TreeNoderoot,intval){// 递归终止条件当前节点为空if(rootnull)returnnull;// 当前节点就是目标节点直接返回if(root.dataval)returnroot;// 递归查找左子树TreeNodeleftfind(root.lchild,val);// 左子树找到直接返回if(left!null)returnleft;// 左子树没找到去右子树查找returnfind(root.rchild,val);}/** * 获取二叉树的高度深度 * 递归当前树高度 max(左子树高度,右子树高度) 1 * param root 根节点 * return 树的高度空树返回0 */publicintgetHeight(TreeNoderoot){if(rootnull)return0;intleftHeightgetHeight(root.lchild);intrightHeightgetHeight(root.rchild);returnMath.max(leftHeight,rightHeight)1;}/** * 获取第K层的节点个数层数从1开始 * param root 根节点 * param k 目标层数k1 * return 第k层节点数量root为null或k非法返回0 */publicintgetKLevelNodeCount(TreeNoderoot,intk){// 树为空 或者层数不合法直接返回0if(rootnull||k0)return0;// k1代表当前就是目标层节点数为1if(k1)return1;// 左子树k-1层 右子树k-1层节点之和returngetKLevelNodeCount(root.lchild,k-1)getKLevelNodeCount(root.rchild,k-1);}/** * 获取叶子结点的个数 * 叶子节点左右孩子都为null的节点 * param root 根节点 * return 叶子节点总数空树返回0 */publicintgetLeafNodeCount(TreeNoderoot){if(rootnull)return0;// 当前是叶子节点计数1if(root.lchildnullroot.rchildnull)return1;// 左子树叶子 右子树叶子returngetLeafNodeCount(root.lchild)getLeafNodeCount(root.rchild);}/** * 统计二叉树结点总个数 * param root 根节点 * return 全部节点数量空树返回0 */publicintsize(TreeNoderoot){if(rootnull)return0;// 当前节点1个 左子树节点数 右子树节点数return1size(root.lchild)size(root.rchild);}/** * 先序遍历根 - 左 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpreOrderTraverse(TreeNoderoot){if(rootnull)return;System.out.print(root.data );preOrderTraverse(root.lchild);preOrderTraverse(root.rchild);}/** * 中序遍历左 - 根 - 右 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidinOrderTraverse(TreeNoderoot){if(rootnull)return;inOrderTraverse(root.lchild);System.out.print(root.data );inOrderTraverse(root.rchild);}/** * 后序遍历左 - 右 - 根 * 递归实现直接打印节点数据 * param root 根节点 */publicvoidpostOrderTraverse(TreeNoderoot){if(rootnull)return;postOrderTraverse(root.lchild);postOrderTraverse(root.rchild);System.out.print(root.data );}/** * 层序遍历广度优先遍历 * 使用队列完成从上到下同一层从左到右打印 * param root 根节点 */publicvoidlevelOrderTraverse(TreeNoderoot){if(rootnull)return;QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){TreeNodecurqueue.poll();System.out.print(cur.data );// 左孩子不为空入队if(cur.lchild!null)queue.offer(cur.lchild);// 右孩子不为空入队if(cur.rchild!null)queue.offer(cur.rchild);}}}
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
