衡水网站联系电话,wordpress社群模板,wordpress页面设计插件,免费制作手机网页 #x1f48e;所属专栏#xff1a;数据结构与算法学习 #x1f48e; 欢迎大家互三#xff1a;2的n次方_ #x1f341;1. 树形结构的介绍 树是一种非线性的数据结构#xff0c;它是由n#xff08;n0#xff09;个有限结点组成一个具有层次关系的集合。把它叫做… 所属专栏数据结构与算法学习 欢迎大家互三2的n次方_ 1. 树形结构的介绍 树是一种非线性的数据结构它是由nn0个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树也就是说它是根朝上而叶朝下的。
以下是树的一些基本术语 节点的度一个节点含有子树的个数 树的度一棵树中所有节点度的最大值 叶子节点终端节点度为0的节点 双亲节点父节点一个节点的直接前驱节点 孩子节点子节点一个节点除了根节点的直接后继节点 根节点没有双亲节点的节点 2. 二叉树的介绍
二叉树是每个节点最多有两个子树的树结构通常称为左子树和右子树正如名字一样每一个节点最多有两个子树。 2.1 二叉树的类别
二叉树是树形结构中最重要的一种类型它有多种特殊形态如
完全二叉树除了最后一层外每一层都被完全填满并且所有节点都尽可能地向左对齐。满二叉树除了叶子节点外每个节点都有两个子节点。平衡二叉树如AVL树、红黑树任何节点的两个子树的高度最大差别为一。搜索二叉树BST左子树上所有节点的值均小于它的根节点的值右子树上所有节点的值均大于它的根节点的值。 2.2 二叉树的基本性质
对于任意一棵二叉树深度为 k 的二叉树最多有 2的k次方 - 1 个节点。
在任何一棵二叉树中如果度为2的节点数为 n₂叶节点数为 n₀则有关系式 n₀n₂1。
任意一棵包含 n 个节点的二叉树的高度至少为 log₂(n1)即完全二叉树的高度最多为 n即所有节点构成一个链表。
在具有2 n 个节点的完全二叉树中叶子节点的个数为 n2n - 1个节点的完全二叉树中叶子节点的个数为 n 2.3 二叉树的存储
二叉树可以通过链式存储和顺序存储的方式存储这一节主要介绍链式存储
链式存储方式使用节点Node对象来表示二叉树的结构。每个节点包含数据部分和两个指针分别指向其左子节点和右子节点。
例如使用孩子兄弟表示法存储树的效果如下图所示 3. 二叉树的实现 class TreeNode {int val;TreeNode left;//左孩子TreeNode right;//右孩子TreeNode(int x) {val x;}
}3.1 二叉树的遍历
树的遍历是树的基本操作之一常见的遍历方式有 前序遍历先访问根节点然后遍历左子树最后遍历右子树。中序遍历在二叉搜索树中先遍历左子树然后访问根节点最后遍历右子树。后序遍历先遍历左子树然后遍历右子树最后访问根节点。层序遍历按从上到下、从左到右的顺序访问树中的每个节点 3.1.1 先序中序后序遍历 //先序遍历根左右public void preOrder(TreeNode root){if(root null) return;System.out.print(root.val );preOrder(root.left);preOrder(root.right);}//中序遍历左根右public void inOrder(TreeNode root){if(root null) return;inOrder(root.left);System.out.print(root.val );inOrder(root.right);}//后序遍历左右根public void postOrder(TreeNode root){if(root null) return;postOrder(root.left);postOrder(root.right);System.out.print(root.val );} 3.1.2 层序遍历
层序遍历的实现需要借助队列来实现由于队列先进先出的特性可以依次把头结点左孩子和右孩子依次入队接着出队打印就可以实现层序遍历的效果 public void levelOrder(TreeNode root) {if (root null) return;QueueTreeNode q new LinkedList();TreeNode cur root;q.offer(root);while (!q.isEmpty()) {cur q.poll();System.out.print(cur.val );if (cur.left ! null) q.offer(cur.left);if (cur.right ! null) q.offer(cur.right);}} 102. 二叉树的层序遍历
可以试一下这道力扣上的题 这道题对返回值有了要求其它的还是正常的层序遍历答案的形式就是每一层作为一个数组最终的答案以一个二维顺序表的形式返回 只需要每次入队时计算一下当前队列的元素把当前层的元素都出队每次入队的元素也都是下一层的元素 class Solution {public ListListInteger levelOrder(TreeNode root) {ListListInteger res new ArrayList();if (root null) return res;QueueTreeNode q new LinkedList();TreeNode cur root;q.offer(root);while (!q.isEmpty()) {ListInteger list new ArrayList();int size q.size();//当这一层的元素都出队后下一层的元素也都能入队while (size!0) {cur q.poll();list.add(cur.val);if (cur.left ! null) q.offer(cur.left);if (cur.right ! null) q.offer(cur.right);size--;}//添加每层的答案res.add(list);}return res;}
} 3.2 size() 求节点数
这里给出遍历和子问题两种思想进行实现 通过前序遍历的方法通过计数的方式得到二叉树的节点数分解子问题就是一棵二叉树的每个分支又可以看作一棵二叉树整个二叉树的节点数就是左子树加上右子树再加上根节点数根结点数就是1 public static int sizeNode 0;//遍历思想public int size(TreeNode root) {if (root null) return 0;sizeNode;size(root.left);size(root.right);return sizeNode;}//子问题思想public int size2(TreeNode root) {if (root null) return 0;return size2(root.left) size2(root.right) 1;} 3.3 getLeafNodeCount(TreeNode root)
求叶子节点数
依然可以使用两种方法通过遍历找出叶子节点分解子问题就是左子树的叶子节点加上右子树的叶子节点等于二叉树的叶子节点因为根节点肯定不是叶子节点 public static int leafSize 0;public int getLeafNodeCount(TreeNode root) {if (root null) return 0;//判断叶子节点if (root.left null root.right null) {leafSize;}getLeafNodeCount(root.left);getLeafNodeCount(root.right);return leafSize;}public int getLeafNodeCount2(TreeNode root) {if (root null) return 0;if (root.left null root.right null) return 1;return getLeafNodeCount2(root.left) getLeafNodeCount2(root.right);} 3.4 getKLeveLNodeCount(TreeNode root, int k)
获取第 k 层的节点数 public int getKLeveLNodeCount(TreeNode root, int k) {if (root null) {return 0;}if (k 1) return 1;return getKLeveLNodeCount(root.left, k - 1) getKLeveLNodeCount(root.right, k - 1);} 3.5 getHeight(TreeNode root)
获取二叉树的高度
还是通过递归来实现二叉树的高度其实也就是左子树和右子树的最大值再加上根节点的一层就是整棵树的高度 public int getHeight(TreeNode root) {if (root null) return 0;return Math.max(getHeight(root.left),getHeight(root.right)) 1;} 3.6 findVal(TreeNode root,char val)
检测val是否存在二叉树中
只需要依次判断根节点左子树右子树通过分解子问题左子树又可以分为根节点左子树右子树依次达到遍历整棵树的效果判断val是否存在 public TreeNode findVal(TreeNode root,char val){if(root null) return null;if(root.val val) return root;TreeNode t1 findVal(root.left,val);if(t1 ! null) return t1;TreeNode t2 findVal(root.right,val);if(t2! null) return t2;return null;} 3.7 isCompleteTree(TreeNode root)
判断是否为完全二叉树
当遍历二叉树时如果遍历到的cur节点此时为null并且此时队列中剩余元素也都是null,那么就是完全二叉树 反之如果剩余元素有不为null的那么就不是完全二叉树例如下面的图中当遍历到B的左孩子为null时此时队列中还有E,G等不为null的元素 public boolean isCompleteTree(TreeNode root) {if (root null) return false;QueueTreeNode q new LinkedList();q.offer(root);//找到cur为空时的位置while (!q.isEmpty()) {TreeNode cur q.poll();if (cur ! null) {q.offer(cur.left);q.offer(cur.right);}else {break;}}//继续判断剩余队列是否有不为null的元素while(!q.isEmpty()){if(q.peek()!null) return false;q.poll();}return true;}
