建设厅网站生成案卷生成不了,适合大学生个体创业的网站建设,深圳vi设计公司联系,网店美工毕业设计论文1. 树
1.1 树的定义
树是一种非线性的数据结构#xff0c;它是由n (n 0)个有限结点组成的一个具有层次关系的集合。之所以将它称为“树”#xff0c;是因为它像一颗倒挂起来的树#xff0c;也就是说它是根朝上#xff0c;叶子在下的。
参考上面的图片#xff0c;…
1. 树
1.1 树的定义
树是一种非线性的数据结构它是由n (n 0)个有限结点组成的一个具有层次关系的集合。之所以将它称为“树”是因为它像一颗倒挂起来的树也就是说它是根朝上叶子在下的。
参考上面的图片我们需要注意到
树有一个特殊的结点–根节点根节点没有前驱结点除了根节点外其他结点可以被分成多个不可交互的集合构成与树类似的子树每颗子树的根节点有且只有一个前驱但是可以有0个或多个后继。树型结构中子树间不能有交集换句话说就是子树间不能构成回环否则就不是树形结构。
1.2 树的相关概念 以上面树为例说明
结点的度一个结点含有子树的个数称为该结点的度 如上图A的度为6树的度一棵树中所有结点度的最大值称为树的度 如上图树的度为6叶子结点度为0的结点称为叶结点 如上图B、C、H、I…等节点为叶结点父结点若一个结点含有子结点则这个结点称为其子结点的父结点 如上图A是B的父结点孩子结点一个结点含有的子树的根结点称为该结点的子结点 如上图B是A的孩子结点根结点一棵树中没有双亲结点的结点如上图A结点的层次从根开始定义起根为第1层根的子结点为第2层以此类推树的高度或深度树中结点的最大层次 如上图树的高度为4
2. 二叉树
2.1 二叉树的定义
一棵二叉树是结点的有限集合该集合是由一个根节点加上两颗被称为左子树和右子树的二叉树构成。也可由一个空集合构成。 根据名字可以所谓二叉树就是树中不存在度大于2的结点二叉树的子树有左右之分次序不能颠倒因此二叉树也是一颗有序树。也就是说二叉树的结构可以看成是以下几种情况复合而成的
二叉树中存在两种特殊的二叉树需要我们去了解满二叉树和完全二叉树。需要注意的是满二叉树其实也是一种特殊情况的完全二叉树。
2.1.1 满二叉树
对于一颗二叉树而言如果每层的结点树都达到最大值则这棵二叉树就是满二叉树。换成数学语言来解释就是一颗存在K层的二叉树结点总数是2^k - 1,根为第一层。
2.1.2 完全二叉树
对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树也就是说一棵从上到下、从左到右都是连续结点的二叉树叫做完全二叉树。
2.2 二叉树的性质
若规定根结点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1) (i0)个结点若规定只有根结点的二叉树的深度为1则深度为K的二叉树的最大结点数是2^k - 1(k0)对任何一棵二叉树, 如果其叶结点个数为 n0, 度为2的非叶结点个数为 n2,则有n0n21具有n个结点的完全二叉树的深度k为Log2(n1)向上取整。对于具有n个结点的完全二叉树如果按照从上至下从左至右的顺序对所有节点从0开始编号则对于序号为i的结点有 若i0父节点序号(i-1)/2当i0时i为根节点无父节点若2i1 n,左孩子序号为2i1若2i1 n时左孩子不存在若2i2 n,右孩子序号为2i1若2i2 n时右孩子不存在 2.3 二叉树的组织结构
我们组织二叉树的结构通常是采用链式存储即通过链表的形式来组织二叉树的一个一个结点我们常见的二叉树有两种表示方法
//孩子表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树}//孩子双亲表示法
class Node {int val; // 数据域Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树Node parent; // 表示当前节点的根节点多了一个存储父节点的引用}2.4 二叉树的基本操作
我们这里保存下二叉树中常见的操作:
// 获取树中节点的个数:根节点左子树节点数右子树节点数
public int size(TreeNode root) { if(root null) { return 0; } return size(root.left) size(root.right) 1;
}// 获取叶子节点的个数:左子树叶子节点数 右子树叶子节点数
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); }// 获取第K层节点的个数:左子树第k-1层节点数右子树第k-1层节点数
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);
}// 获取二叉树的高度左右子树最大高度 1根节点
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; }// 检测值为value的元素是否存在:检查根节点根节点不是再到左子树找左子树找不到就到右子树找都找不到就没有
public TreeNode find(TreeNode root, char val) { if(root null) { return null; } if(root.val val) { return root; } TreeNode leftFind find(root.left,val); if(leftFind ! null) { return leftFind; } TreeNode rightFind find(root.right,val); if(rightFind ! null) { return rightFind; } return null;
}//层序遍历:借助队列实现从上到下从左到右
public void levelOrder(TreeNode root) { if(root null) { return ; } QueueTreeNode queue new LinkedList(); queue.offer(root);//先押入一个结点 while(!queue.isEmpty()) { TreeNode cur queue.poll(); System.out.print(cur.val ); if(cur.left ! null) { queue.offer(cur.left); } if(cur.right ! null) { queue.offer(cur.right); } } System.out.println(); }// 判断一棵树是不是完全二叉树:借助队列实现
public boolean isCompleteTree(TreeNode root) { if(root null) { return true; } QueueTreeNode queue new LinkedList(); queue.offer(root); while(!queue.isEmpty()) { TreeNode cur queue.poll(); if(cur null) { break; } queue.offer(cur.left); queue.offer(cur.right); } while(!queue.isEmpty()) { TreeNode cur queue.poll(); if(cur ! null) { return false; } } return true;
}2.5 二叉树的模拟实现
import java.util.*; //锻炼分治思想将大问题化为相关的子问题
public class BinaryTree { static class TreeNode { public char val; public TreeNode left; public TreeNode right; public TreeNode(char val) { this.val val; } Override public String toString() { return TreeNode{ val val , left left , right right }; } } public TreeNode root; //手动方式创造一棵树 public TreeNode creatTree() { TreeNode node1 new TreeNode(A); TreeNode node2 new TreeNode(B); TreeNode node3 new TreeNode(C); TreeNode node4 new TreeNode(D); TreeNode node5 new TreeNode(E); TreeNode node6 new TreeNode(F); TreeNode node7 new TreeNode(G); TreeNode node8 new TreeNode(H); node1.left node2; node1.right node3; node2.left node4; node2.right node5; node3.left node6; node3.right node7; node5.right node8; this.root node1; return root; } // 前序遍历递归 public void preOrder(TreeNode root) { //先访问根节点再访问左子树最后访问右子树 if(root null) { return ;//遇到空树返回 } System.out.print(root.val ); preOrder(root.left); preOrder(root.right); } //非递归 public void preOrderNor(TreeNode root) { if(root null) { return ; } //申请栈来保存当前’最近‘未访问完分支结点的父节点 StackTreeNode stack new Stack(); while(root ! null || !stack.isEmpty()) { while(root ! null) { stack.push(root); System.out.print(root.val ); root root.left; } TreeNode cur stack.pop(); root cur.right;//压入右子树内容 } System.out.println(); } // 中序遍历递归 public void inOrder(TreeNode root) { //先访问左子树再访问根节点最后访问右子树 if(root null) { return ;//遇到空树返回 } inOrder(root.left); System.out.print(root.val ); inOrder(root.right); } //非递归 public void inOrderNor(TreeNode root) { if(root null) { return ; } //申请栈来保存当前’最近‘未访问完分支结点的父节点 StackTreeNode stack new Stack(); while(root ! null || !stack.isEmpty()) { while(root ! null) { stack.push(root); root root.left; } TreeNode cur stack.pop(); System.out.print(cur.val ); root cur.right; } System.out.println(); } // 后序遍历递归 public void postOrder(TreeNode root) { //先访问左子树再访问右子树最后访问根节点 if(root null) { return ;//遇到空树返回 } postOrder(root.left); postOrder(root.right); System.out.print(root.val ); } //非递归 //难点记录上一个打印过的值避免重复打印 public void postOrderNor(TreeNode root) { if(root null) { return ; } //申请栈来保存当前’最近‘未访问完分支结点的父节点 StackTreeNode stack new Stack(); TreeNode pre null;//记录上一个打印的结点 while(root ! null || !stack.isEmpty()) { while(root ! null) { stack.push(root); root root.left; } TreeNode peekNode stack.peek();//后序遍历不能直接pop需要先peek //右节点不存在时或访问过时peekNode.right pre直接打印当前结点 if(peekNode.right null || peekNode.right pre) { System.out.print(stack.pop().val ); pre peekNode;//记录打印过结点 }else { root peekNode.right;//当右节点存在时压入 } } System.out.println(); } // 获取树中节点的个数:根节点左子树节点数右子树节点数 public int size(TreeNode root) { if(root null) { return 0; } return size(root.left) size(root.right) 1; } // 获取叶子节点的个数:左子树叶子节点数 右子树叶子节点数 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); } // 获取第K层节点的个数:左子树第k-1层节点数右子树第k-1层节点数 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); } // 获取二叉树的高度左右子树最大高度 1根节点 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; } // 检测值为value的元素是否存在:检查根节点根节点不是再到左子树找左子树找不到就到右子树找都找不到就没有 public TreeNode find(TreeNode root, char val) { if(root null) { return null; } if(root.val val) { return root; } TreeNode leftFind find(root.left,val); if(leftFind ! null) { return leftFind; } TreeNode rightFind find(root.right,val); if(rightFind ! null) { return rightFind; } return null; } //层序遍历:借助队列实现从上到下从左到右 public void levelOrder(TreeNode root) { if(root null) { return ; } QueueTreeNode queue new LinkedList(); queue.offer(root);//先押入一个结点 while(!queue.isEmpty()) { TreeNode cur queue.poll(); System.out.print(cur.val ); if(cur.left ! null) { queue.offer(cur.left); } if(cur.right ! null) { queue.offer(cur.right); } } System.out.println(); } // 判断一棵树是不是完全二叉树:借助队列实现 public boolean isCompleteTree(TreeNode root) { if(root null) { return true; } QueueTreeNode queue new LinkedList(); queue.offer(root); while(!queue.isEmpty()) { TreeNode cur queue.poll(); if(cur null) { break; } queue.offer(cur.left); queue.offer(cur.right); } while(!queue.isEmpty()) { TreeNode cur queue.poll(); if(cur ! null) { return false; } } return true; } //翻转二叉树 public TreeNode invertTree(TreeNode root) { if(root null) { return null; } if(root.left null root.right null) { return root; } TreeNode leftTmp root.left; TreeNode rightTmp root.right; root.left invertTree(rightTmp); root.right invertTree(leftTmp); return root; } //检查两棵树是否相同 public boolean isSameTree(TreeNode p, TreeNode q) { if(p q) { return true; } //判断根节点相同不相同 if(p null q! null || q null p! null) { return false; } if(p null q null) { return true; } if(p.val ! q.val) { return false; } //判断各自左子树和右子树相同与否 return isSameTree(p.left,q.left) isSameTree(p.right,q.right); } //检查两棵树是否对称 public boolean isSymmetric(TreeNode root) { if(root null) { return true; } //判断左子树和右子树是否对称 return _isSymmetric(root.right,root.left); } //判断两棵树是不是对称树 public boolean _isSymmetric(TreeNode p, TreeNode q) { if(p null q! null || q null p! null) { return false; } if(p null q null) { return true; } if(p.val ! q.val) { return false; } //递归实现判断 //一棵树的左子树右子树和另一棵树的右子树左子树是否对成 return _isSymmetric(p.left,q.right) _isSymmetric(p.right,q.left); } //判断一棵树是否是另一棵树的子树:树中存在和子树一样的树就有子树 //分治 public boolean isSubtree(TreeNode root, TreeNode subRoot) { if(root null) { return false; } if(isSameTree(root,subRoot)) { return true; } //去左右子树中找是否存在和他相同的树相同则存在子树 if(isSubtree(root.left,subRoot) || isSubtree(root.right,subRoot)) { return true; } return false; } //判断一棵二叉树是否为平衡二叉树 //1 判断每个节点是否平衡 public boolean isBalanced1(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 isBalanced1(root.left) isBalanced1(root.right); } //2 求结点高度时的返回值是否正常来判断 public boolean isBalanced(TreeNode root) { if(root null) { return true; } return getHeight1(root) 0; } public int getHeight1(TreeNode root) { if(root null) { return 0; } //高度结点返回值不正常代表不是平衡二叉树 int leftHeight getHeight1(root.left); if(leftHeight -1) { return -1; } int rightHeight getHeight1(root.right); if(rightHeight -1) { return -1; } if(Math.abs(leftHeight - rightHeight) 1) { return -1; } return Math.max(leftHeight,rightHeight) 1; } //给定用’#‘表示null的字符串来创建和构造树 public static int i;//定义全局变量避免形参值传递不改变实参的现象 public static TreeNode creatTree(String str) { i0; TreeNode root _creatTree(str); return root; } public static TreeNode _creatTree(String str) { char ch str.charAt(i); i; TreeNode root null; //#代表空表示不用创建结点 if(ch ! # i str.length()) { root new TreeNode(ch);//创建根节点 root.left _creatTree(str);//创建左子树 root.right _creatTree(str);//创建右子树 } return root; } //中序后序还原二叉树:根据两排序结合先建立根节点再建立右子树最后建立左子树 //中序左 根节点 右 //后序左 右 根节点 public TreeNode buildTreePost(char[] inorder, char[] postorder) { postIndex postorder.length - 1; return _buildTreePost(inorder, 0, inorder.length - 1, postorder); } public static int postIndex;//定义全局变量不用传参当把全局定量传参时依然存在局部优先 public TreeNode _buildTreePost(char[] inorder, int left, int right, char[] postorder) { if(postIndex postorder.length || postIndex 0 || left right) { return null; } TreeNode root new TreeNode(postorder[postIndex--]); int valIndex findIndex(inorder,left,right,root.val); root.right _buildTreePost(inorder,valIndex 1,right,postorder); root.left _buildTreePost(inorder,left,valIndex - 1,postorder); return root; } //在范围内查找 public int findIndex(char[] inorder,int left,int right,int val) { for(int i left;i right;i) { if(inorder[i] val) { return i; } } return -1; } //前序中序还原二叉树 public TreeNode buildTreePre(char[] preorder, char[] inorder) { preIndex 0; return _buildTreePre(preorder,0,inorder.length - 1,inorder); } public static int preIndex; public TreeNode _buildTreePre(char[] preorder, int left, int right, char[] inorder) { if(left right || preIndex preorder.length) { return null; } TreeNode root new TreeNode(preorder[preIndex]); int valIndex findIndex(inorder,left,right,root.val); root.left _buildTreePre(preorder,left,valIndex-1,inorder); root.right _buildTreePre(preorder,valIndex1,right,inorder); return root; } //两个节点的最近公共祖先 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root null) { return null; } //有一个结点rootroot就是最近公共祖先 if(p root || q root) { return root; } //左右找最近共公祖先都有则root是否则则找到那边是 TreeNode leftRoot lowestCommonAncestor(root.left,p,q); TreeNode rightRoot lowestCommonAncestor(root.right,p,q); if(leftRoot ! null rightRoot ! null) { return root; }else if(leftRoot ! null) { return leftRoot; }else if(rightRoot ! null) { return rightRoot; } return null; } //层序遍历2给你二叉树的根节点 root 返回其节点值 自底向上的层序遍历 //即按从叶子节点所在层到根节点所在的层逐层从左向右遍历 //借助队列来实现广度优先遍历中间可以将每层结点的东西加入这一层的组合里 public ListListCharacter levelOrderBottom(TreeNode root) { ListListCharacter list new LinkedList(); if(root null) { return list; } QueueTreeNode queue new ArrayDeque(); queue.offer(root);//先押入一个节点 while(!queue.isEmpty()) { int size queue.size();//先判断每一层有多少节点 ListCharacter listCur new LinkedList();//设置存储每层节点 //往listCur塞入每层结点的val同时将下一层结点赛入queue while(size ! 0) { TreeNode cur queue.poll(); listCur.add(cur.val); if(cur.left ! null) { queue.offer(cur.left); } if(cur.right ! null) { queue.offer(cur.right); } size--; } list.add(0,listCur);//头插使得插入顺序实现逆序 } return list; } //层序遍历1 public ListListCharacter levelOrder1(TreeNode root) { ListListCharacter list new LinkedList(); if(root null) { return list; } QueueTreeNode queue new LinkedList(); queue.offer(root); while(!queue.isEmpty()) { int size queue.size(); ListCharacter listCur new LinkedList(); while(size ! 0) { TreeNode cur queue.poll(); listCur.add(cur.val); if(cur.left ! null) { queue.offer(cur.left); } if(cur.right ! null) { queue.offer(cur.right); } size--; } list.add(listCur); } return list; } //根据二叉树创建字符串:关键点在于括号的额外判断 public String tree2str(TreeNode root) { if(root null) { return ; } StringBuilder stringBuilder new StringBuilder(); tree2str(root,stringBuilder); return stringBuilder.toString(); } public void tree2str(TreeNode root,StringBuilder stringBuilder) { if(root null) { return ; } stringBuilder.append(root.val); //递归创建结点括号根据特定情况加 if(root.left ! null) { stringBuilder.append((); tree2str(root.left,stringBuilder); stringBuilder.append()); }else if(root.right ! null) { //左边为空右边不为空就加() stringBuilder.append(()); } if(root.right ! null) { stringBuilder.append((); tree2str(root.right,stringBuilder); stringBuilder.append()); } } }需要特别注意的是以上模拟二叉树实现的过程中不单单只是实现了与二叉树基础操作相关的内容同时加入了一些常见二叉树OJ题的实现 以下OJ题均已实现在二叉树的模拟实现中并配有相对应的注释
检查两棵树是否相同判断某棵树是否是另一棵树的子树翻转二叉树判断一棵二叉树是否是平衡二叉树对称二叉树的判断给定用’#‘表示null的先序遍历字符串来创建和构造树二叉树的层序遍历最近公共祖先根据一棵树的前序遍历与中序遍历构造二叉树根据一棵树的后序遍历与中序遍历构造二叉树二叉树创建字符串前序遍历的非递归中序遍历的非递归后序遍历的非递归
