drupal做虚拟发货网站高端建站是什么

当前位置： 首页 > news >正文

drupal做虚拟发货网站,高端建站是什么,python兼职网站开发,自己做国外网站前言#xff1a; 树这个结构想必在日常生活中很常见到#xff0c;而现在要介绍的是一种独特的数据结构–二叉树。 1.树 #xff08;1#xff09;定义#xff1a; 是一种非线性结构#xff0c;有一个特殊的节点叫做根节点#xff0c;树没有前驱节点#xff1b;树是递…前言 树这个结构想必在日常生活中很常见到而现在要介绍的是一种独特的数据结构–二叉树。 1.树 1定义 是一种非线性结构有一个特殊的节点叫做根节点树没有前驱节点树是递归定义的树形结构中子树不能有交集否则就不是树形结构。 2树相关重要概念如上图 节点的度一个节点含有的子树的个数。egA的度为2B的度为3。 树的度一棵树中所有节点的度中的最大值。 eg树的度为3. 叶子节点/终端节点节点的度为0的节点。eg叶子节点EDGF 双亲节点/父节点若有一个节点含有子节点则称这个节点为该子节点的双亲节点/父节点。 孩子节点/子节点一个节点含有的子树的根节点称为该节点的子节点。 根节点一颗树中没有双亲节点的节点。 节点的层次从根节点开始根为第一层根的子节点为第二层以此类推。 树的高度/深度树中节点的最大层次。eg树的深度/高度为3. 2.二叉树 1定义 该树中每个节点的度都小于等于2且子树有左右子树之分。下图都是二叉树。 2两种特殊的二叉树 a.完全二叉树如果一颗树的节点个数为n深度为K且树中每一个节点都是深度为K的满二叉树中编号从0~(n-1)的节点则称为完全二叉树。 b.满二叉树每层节点数都是最大值 如果一颗树的高度为n且树节点的总数为则称为满二叉树。 3二叉树的性质 a.若根节点的层数为1则一颗非空二叉树的第i层上的节点最多有个。 b.若规定只有根节点的二叉树的深度为1则深度为K的二叉树节点总数最多为。 c.对任何一颗二叉树如果叶子节点的个数为节点的度为2的节点个数为则1。 d.具有n个节点的完全二叉树则该树的深度为向上取整。 e.对于具有n个节点的完全二叉树如果按照从上到下从左到右的顺序对所有节点从0开始编号对于第i个节点有 如果i0则双亲节点/父节点如果i0则没有双亲节点/父节点 如果2i1n则该节点有左孩子否则没有左孩子。 如果2i2n则该节点有右孩子否则没有右孩子。 f.对于一颗完全二叉树来说如果该树节点总数为偶数个则节点的度为1的节点只有一个若为奇数个则没有节点的度为1的节点。 4二叉树的遍历及其代码实现 在实现二叉树的遍历之前首先需要创建一个类TreeNode二叉树的节点包含该节点的值该节点的左孩子节点该节点的右孩子节点所以 class TreeNode {public TreeNode left;//左孩子public TreeNode right;//右孩子public int val;public TreeNode(int val) {this.val val;} } a.前序遍历根节点 - 左子树 - 右子树 分析 代码实现 public void preorderTraversal(TreeNode root) {if(root null) {return;}System.out.print(root.val );preorderTraversal(root.left);preorderTraversal(root.right); } b.中序遍历左子树 - 根节点 - 右子树 分析 代码实现 public void inorderTraversal(TreeNode root) {if(root null) {return;}preorderTraversal(root.left);System.out.print(root.val );preorderTraversal(root.right); } c.后序遍历左子树 - 右子树 - 根节点 分析 代码实现 public void lastorderTraversal(TreeNode root) {if(root null) {return;}preorderTraversal(root.left);preorderTraversal(root.right);System.out.print(root.val ); } 5二叉树相关OJ题 二叉树所有的题都会涉及到递归。所有OJ题的前提都是已经创建好了一颗树并且知道根节点为root。 a.求树的高度。 题析 题解 public int getHeight(TreeNode root) {if(root null) {return 0;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return Math.max(leftHeight,rightHeight) 1;//这里也可以用条件运算符 } b.求树中叶子节点的个数。 题析 题解 public int getLeafNodeCount(TreeNode root) {if(root null) {return 0;}if(root.left null root.right null) {return 1;} return getLeafNodeCount(root.left) getLeafNodeCount(root.right); } c.第i层有多少个节点。 题析 题解 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); } d.判断某个val值是否存在于树中。 题析 题解 public TreeNode getVal(TreeNode root, int val) {if(root null) {return null;}if(root.val val) {return root;}TreeNode leftTree getVal(root.left,val);if(leftTree ! null) {return leftTree;}TreeNode rightTree getVal(root.right,val);if(rightTree ! null) {return rightTree;}return null; } e.节点的总个数。 题析 题解 public int size(TreeNode root) {if(root null) {return 0;}return size(root.left) size(root.right) 1; } f.检查两棵树是否相同 题析 题解 class Solution {public boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null) {return true;}if(p null q ! null || q null p ! null) {return false;}if(p.val ! q.val) {return false;}return isSameTree(p.left, q.left) isSameTree(p.right, q.right);} } g.另一棵树的子树 题析 题解 class Solution {//判断两棵树的结构是否相同private boolean isSameTree(TreeNode p, TreeNode q) {if(p null q null) {return true;}if(p null q ! null || q null p ! null) {return false;}if(p.val ! q.val) {return false;}return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}public boolean isSubtree(TreeNode root, TreeNode subRoot) {if(root null) {return false;}if(isSameTree(root,subRoot)) {return true; }return isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot);} } h.翻转二叉树 题析 题解 法一该种方法没有利用返回值先序遍历。 class Solution {public TreeNode invertTree(TreeNode root) {if(root null) {return null;}if(root.left null root.right null) {return root;}TreeNode tmp root.left;root.left root.right;root.right tmp;invertTree(root.left);invertTree(root.right);return root;} } 法二利用返回值后序遍历。 class Solution {public TreeNode invertTree(TreeNode root) {if(root null) {return null;}if(root.left null root.right null) {return root;}TreeNode leftNode invertTree(root.left);TreeNode rightNode invertTree(root.right);root.left rightNode;root.right leftNode;return root;} } i.是否为平衡二叉树 题析 题解 法一该方法的时间复杂度为 class Solution {public boolean isBalanced(TreeNode root) {if(root null) {return true;}int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);if(Math.abs(leftHeight - rightHeight) 1) {return false;} return isBalanced(root.left) isBalanced(root.right);}private int getHeight(TreeNode root) {if(root null) {return 0;}int leftHigh getHeight(root.left);int rightHigh getHeight(root.right);return Math.max(leftHigh,rightHigh) 1;} } 法二可以实现时间复杂度为只需要去修改getHeight方法在求高度的过程中去判断是否每一个节点的高度差 1。 题解 class Solution {public boolean isBalanced(TreeNode root) {if(root null) {return true;}return getHeight(root) 0;}private int getHeight(TreeNode root) {if(root null) {return 0;}int leftHigh getHeight(root.left);if(leftHigh -1) {return -1;}int rightHigh getHeight(root.right);if(rightHigh 0 Math.abs(leftHigh - rightHigh) 1) {return Math.max(leftHigh,rightHigh) 1;}return -1;} } j.二叉树的构建与遍历 题析 题解 import java.util.Scanner; class TreeNode {public char val;public TreeNode left;public TreeNode right;public TreeNode(char val) {this.val val;} }public class Main {private static int i;//注意static修饰的变量每次调用这个方法的时候都是对同一个变量进行修改的。//所以第二次调用该方法的时候i不为0.所以需要在while循环中将i置0/使用非静态方法private static TreeNode createTree(String str) {TreeNode root null;if (str.charAt(i) ! #) {root new TreeNode(str.charAt(i));i;root.left createTree(str);root.right createTree(str);}else {i;}return root; }//中序遍历private static void inOrder(TreeNode root) {if(root null) {return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}public static void main(String[] args) {Scanner in new Scanner(System.in);// 注意 hasNext 和 hasNextLine 的区别while (in.hasNextLine()) { // 注意 while 处理多个 caseString str in.nextLine();i 0;TreeNode root createTree(str);inOrder(root);}} } k.对称二叉树 题析 题解 class Solution {private boolean isSymmetricChild(TreeNode leftNode, TreeNode rightNode) {if(leftNode null rightNode ! null || rightNode null leftNode ! null){return false;}if(leftNode null rightNode null) {return true;}if(leftNode.val ! rightNode.val) {return false;}return isSymmetricChild(leftNode.left,rightNode.right) isSymmetricChild(leftNode.right,rightNode.left);}public boolean isSymmetric(TreeNode root) {return isSymmetricChild(root.left, root.right);} }