江苏网站建设流程,惠东网站设计,网站设计论文的摘要,网站建设一般多少钱app树二叉树二叉树具有唯一根节点二叉树每个节点最多有两个孩子#xff0c;最多有一个父亲二叉树具有天然递归结构二叉树不一定是 “满” 的#xff1a;一个节点也是二叉树、空节点也是二叉树二叉搜索树(BST)BST 的基本功能public class BST {private Node root;private int…树二叉树二叉树具有唯一根节点二叉树每个节点最多有两个孩子最多有一个父亲二叉树具有天然递归结构二叉树不一定是 “满” 的一个节点也是二叉树、空节点也是二叉树二叉搜索树(BST)BST 的基本功能public class BST {private Node root;private int size;public BST(){rootnull;size0;}public int size(){return size;}public boolean isEmpty(){return size0;}private class Node{public E e;public Node left,right;public Node(E e){this.ee;this.leftnull;this.rightnull;}}}添加元素思路对于如下的 BST向其中添加 2828 与根结点 41 比较应该插入左子树28 与左子树的根结点 22 比较应该插入该结点的右子树28 与 33 比较应该插入该结点的左子树该结点的左子树为空则将值为 28 的结点添加到该结点的左子树中最终将 28 添加到该 BST 中代码//向BST中添加新元素epublic void add(E e){if(rootnull){rootnew Node(e);size;return;}else{add(root,e);}}//向以node为根节点的BST树种插入元素eprivate void add(Node node,E e){if(e.equals(node.e)){//插入元素与根节点相等直接返回return;}else if(e.compareTo(node.e)0 node.leftnull){node.leftnew Node(e);size;return;}else if(e.compareTo(node.e)0 node.rightnull){node.rightnew Node(e);size;return;}if(e.compareTo(node.e)0){add(node.left,e);}else{ //e.compareTo(node.e)0add(node.right,e);}}改进添加元素前文中的添加操作对 rootnull 的情况进行了特殊处理,并且 add(Node,E) 中的递归条件也太冗长了。这里我们写一个 add() 方法返回插入新节点后该 BST 的根节点//向BST中添加新元素epublic void add(E e){rootadd(root,e);}//向以node为根节点的BST树种插入元素e//返回插入新元素后该BST的根private Node add(Node node,E e){if(nodenull){size;return new Node(e);}//注意对于e.equals(node.e)不做处理if(e.compareTo(node.e)0){node.leftadd(node.left,e);}else if(e.compareTo(node.e)0){node.rightadd(node.right,e);}return node;}查询元素//查看BST中是否包含元素epublic boolean contains(E e){return contains(root,e);}//查看以node为根节点的BST中是否包含元素eprivate boolean contains(Node node,E e){if(nodenull){return false;}if(e.compareTo(node.e)0){return true;}else if(e.compareTo(node.e)0){return contains(node.left,e);}else{return contains(node.right,e);}}遍历元素(递归形式)前序遍历//BST的前序遍历public void preOrder(){preOrder(root);}private void preOrder(Node node){if(nodenull){return;}System.out.println(node.e);preOrder(node.left);preOrder(node.right);}/*** 利用前序遍历打印 BST*/Overridepublic String toString() {StringBuilder resnew StringBuilder();generateBST(root,0,res);return res.toString();}//生成以node为根节点深度为depth的描述二叉树的字符串(利用前序遍历)private void generateBST(Node node,int depth,StringBuilder res){if(nodenull){res.append(generateDepth(depth)null\n);return;}res.append(generateDepth(depth)node.e\n);generateBST(node.left,depth1,res);generateBST(node.right,depth1,res);}private String generateDepth(int depth){StringBuilder resnew StringBuilder();for(int i0;ires.append(--);}return res.toString();}中序遍历//BST的中序遍历public void inOrder(){inOrder(root);}private void inOrder(Node node){if(nodenull){return;}inOrder(node.left);System.out.println(node.e);inOrder(node.right);}后序遍历//BST的后序遍历public void postOrder(){postOrder(root);}private void postOrder(Node node){if(nodenull){return;}postOrder(node.left);postOrder(node.right);System.out.println(node.e);}遍历元素(非递归形式)//枚举命令GO表示访问元素COUT表示打印元素private enum Command{GO,COUT};private class StackNode{Command command;Node node;StackNode(Command command,Node node){this.commandcommand;this.nodenode;}}前序遍历//BST的前序遍历(非递归方式)public void preOrderNR(){preOrderNR(root);}private void preOrderNR(Node node){if(nodenull){return;}Stack stacknew Stack();stack.push(new StackNode(Command.GO,node));while(!stack.isEmpty()){StackNode stackNodestack.pop();Node nstackNode.node;Command commandstackNode.command;if(commandCommand.COUT){System.out.println(stackNode.node.e);}else{if(n.right!null){stack.push(new StackNode(Command.GO,n.right));}if(n.left!null){stack.push(new StackNode(Command.GO,n.left));}stack.push(new StackNode(Command.COUT,n));}}}中序遍历//BST的中序遍历(非递归方式)public void inOrderNR(){inOrderNR(root);}private void inOrderNR(Node node){if(nodenull){return;}Stack stacknew Stack();stack.push(new StackNode(Command.GO,node));while(!stack.isEmpty()){StackNode stackNodestack.pop();Node nstackNode.node;Command commandstackNode.command;if(commandCommand.COUT){System.out.println(stackNode.node.e);}else{if(n.right!null){stack.push(new StackNode(Command.GO,n.right));}stack.push(new StackNode(Command.COUT,n));if(n.left!null){stack.push(new StackNode(Command.GO,n.left));}}}}后序遍历//BST的后序遍历(非递归方式)public void postOrderNR(){postOrderNR(root);}private void postOrderNR(Node node){if(nodenull){return;}Stack stacknew Stack();stack.push(new StackNode(Command.GO,node));while(!stack.isEmpty()){StackNode stackNodestack.pop();Node nstackNode.node;Command commandstackNode.command;if(commandCommand.COUT){System.out.println(stackNode.node.e);}else{stack.push(new StackNode(Command.COUT,n));if(n.right!null){stack.push(new StackNode(Command.GO,n.right));}if(n.left!null){stack.push(new StackNode(Command.GO,n.left));}}}}层序遍历//BST的层序遍历public void levelOrder(){Queue qnew LinkedList();q.add(root);while(!q.isEmpty()){Node nodeq.remove();System.out.println(node.e);if(node.left!null){q.add(node.left);}if(node.right!null){q.add(node.right);}}}删除元素删除最小值和最大值寻找 BST 中的最小元素和最大元素//寻找BST中的最小元素public E min(){if(size0){throw new IllegalArgumentException(BST is emmpty);}return min(root).e;}private Node min(Node node){if(node.leftnull){return node;}return min(node.left);}//寻找BST中的最大元素public E max(){if(size0){throw new IllegalArgumentException(BST is emmpty);}return max(root).e;}private Node max(Node node){if(node.rightnull){return node;}return max(node.right);}删除BST中的最大值和最小值情况一最小值是叶子节点。直接删除该节点情况二最小值有右子树。删除该节点再将该节点的右子树连接到原来的 BST 中代码//删除BST中的最小值public E delMin(){E resmin();delMin(root);return res;}//删除以node为根结点的BST中的最小值元素//这里考虑最小值只有右子树的情况因为叶子节点是其特例private Node delMin(Node node){if(node.leftnull){Node nodeRightnode.right;node.rightnull;size--;return nodeRight;}node.leftdelMin(node.left);return node;}//删除BST中的最大值public E delMax(){E resmax();delMax(root);return res;}//删除以node为根结点的BST中的最大值元素private Node delMax(Node node){if(node.rightnull){Node nodeLeftnode.left;node.leftnull;size--;return nodeLeft;}node.rightdelMax(node.right);return node;}删除任意元素删除只有左孩子的节点。直接删除即可删除只有右孩子的节点。直接删除即可删除左右孩子都有的节点Habbard-Deletiond 是待删除的节点s 节点是 d 的后继也就是 d 的右子树的最小值所在的节点。注意这里选择左子树的最大值所在的节点效果也是相同的。使用 s 代替 d最后删除 d 节点代码//删除BST中任意元素public void del(E e){rootdel(root,e);}private Node del(Node node,E e){if(nodenull){return null;}if(e.compareTo(node.e)0){node.leftdel(node.left,e);return node;}else if(e.compareTo(node.e)0){node.rightdel(node.right,e);return node;}else{//节点node就是要删除的节点//该节点只右有子树if(node.leftnull){Node rightNodenode.right;node.rightnull;size--;return rightNode;}//该节点只有左子树if(node.rightnull){Node leftNodenode.left;node.leftnull;size--;return leftNode;}//删除既有左子树又有右子树的节点Node smin(node.right);s.rightdelMin(node.right);s.leftnode.left;//删除nodenode.leftnode.rightnull;return s;}}哈夫曼树哈夫曼树的构造过程首先生成一颗哈夫曼树每次生成过程中选取频率最少的两个节点生成一个新节点作为它们的父节点并且新节点的频率为两个节点的和。选取频率最少的原因是生成过程使得先选取的节点位于树的更低层那么需要的编码长度更长频率更少可以使得总编码长度更少。生成编码时从根节点出发向左遍历则添加二进制位 0向右则添加二进制位 1直到遍历到叶子节点叶子节点代表的字符的编码就是这个路径编码。举例给定了四个结点abcd权值分别为7524。找出现有权值中最小的两个2 和 4 相应的结点 c 和 d 构建一个新的二叉树树根的权值为 2 4 6同时将原有权值中的 2 和 4 删掉将新的权值 6 加入。重复之前的步骤。所有的结点构建成了一个全新的二叉树这就是哈夫曼树。代码public class Huffman {private class Node implements Comparable {char ch;int freq;boolean isLeaf;Node left, right;public Node(char ch, int freq) {this.ch ch;this.freq freq;isLeaf true;}public Node(Node left, Node right, int freq) {this.left left;this.right right;this.freq freq;isLeaf false;}Overridepublic int compareTo(Node o) {return this.freq - o.freq;}}public Map encode(Map frequencyForChar) {PriorityQueue priorityQueue new PriorityQueue();for (Character c : frequencyForChar.keySet()) {priorityQueue.add(new Node(c, frequencyForChar.get(c)));}while (priorityQueue.size() ! 1) {Node node1 priorityQueue.poll();Node node2 priorityQueue.poll();priorityQueue.add(new Node(node1, node2, node1.freq node2.freq));}return encode(priorityQueue.poll());}private Map encode(Node root) {Map encodingForChar new HashMap();encode(root, , encodingForChar);return encodingForChar;}private void encode(Node node, String encoding, Map encodingForChar) {if (node.isLeaf) {encodingForChar.put(node.ch, encoding);return;}encode(node.left, encoding 0, encodingForChar);encode(node.right, encoding 1, encodingForChar);}}
