文章目录

各类树的构造基本的二叉树二叉排序树赫夫曼树完全二叉树（树的顺序存储）TODO

各类树的构造

基本的二叉树

package 数据结构与算法; // 根节点 // 父节点 // 子节点 // 度（子节点个数） // 节点的权（值） // 叶子节点（无子节点） // 子树 // 层 // 树高度 ，最大树深度 // 森林 public class 树结构 { public static void main(String[] args) { // 创建一棵树 BinaryTree binTree = new BinaryTree(); // 创建一个根节点 TreeNode root = new TreeNode(1); // 把根节点赋给树 binTree.setRoot(root); // 创建左子节点 TreeNode rootl = new TreeNode(2); root.setLeftNode(rootl); // 创建右子节点 TreeNode rootr = new TreeNode(3); root.setRightNode(rootr); // 为第二次层开始创建节点 rootl.setLeftNode(new TreeNode(4)); rootl.setRightNode(new TreeNode(5)); rootr.setLeftNode(new TreeNode(6)); rootr.setRightNode(new TreeNode(7)); // 遍历 binTree.frontShow(); } } // 二叉树 // 满二叉树 所有叶子节点在最后一层，节点总数为: 2*n-1 ; n 为层数 // 完全二叉树： 所有叶子节点都在最后一层或倒数第二层 // ——并且最后一层的叶子节点在左边连续，倒数第二次的叶子节点在右边连续 class BinaryTree { TreeNode root; // 设置根节点 public void setRoot(TreeNode root) { this.root = root; } // 返回根节点 public TreeNode getRoot() { return root; } public void frontShow() { if (root != null) { root.frontShow(); } } public void midShow() { root.midShow(); } public void afterShow() { root.afterShow(); } public TreeNode frontSearch(int i) { return root.frontSearch(i); } public void delete(int i) { root.delete(i); } } class TreeNode { // 权 int value; // 左儿子 、 TreeNode leftNode, rightNode; // 构造 public TreeNode(int value) { this.value = value; } // 设左儿子 public void setLeftNode(TreeNode lNode) { this.leftNode = lNode; } // 设右儿子 public void setRightNode(TreeNode rNode) { this.rightNode = rNode; } // 前序遍历 public void frontShow() { System.out.println(this.value); if (leftNode != null) { leftNode.frontShow(); } if (rightNode != null) { rightNode.frontShow(); } } // 中序遍历 public void midShow() { if (leftNode != null) { leftNode.midShow(); } System.out.println(value); if (rightNode != null) { rightNode.midShow(); } } // 后序遍历 public void afterShow() { if (leftNode != null) { leftNode.afterShow(); } if (rightNode != null) { rightNode.afterShow(); } System.out.println(value); } // 前序查找 public TreeNode frontSearch(int i) { TreeNode target = null; // 对比当前节点的值 if (this.value == i) { return this; // 当前节点的值不是要查找的值 } else { // 找左儿子 if (leftNode != null) { target = leftNode.frontSearch(i); } // 如果非空，说明在左儿子中已经找到 if (target != null) { return target; } // 查找右儿子 if (rightNode != null) { target = rightNode.frontSearch(i); } } return target; } // 子树删除 public void delete(int i) { TreeNode parent = this; // 判断左儿子 if (parent.leftNode != null && parent.leftNode.value == i) { parent.leftNode = null; return; } // 判断右儿子 if (parent.rightNode != null && parent.rightNode.value == i) { parent.rightNode = null; return; } // 递归检查并删除 parent = leftNode; if (parent != null) { parent.delete(i); return; } parent = rightNode; if (parent != null) { parent.delete(i); return; } } }

二叉排序树

package 数据结构与算法; // 二叉排序树，也叫二叉查找树，二叉搜索树BST // 对于二叉树中的任何一个非叶子节点，要求左子节点比当前的节点值小 // 右子节点比当前节点值大 public class 树_二叉排序树 { public static void main(String[] args) { int[] arr = {7, 3, 10, 12, 5, 1, 9}; // 创建一颗二叉排序数 BinarySortTree bst = new BinarySortTree(); // 循环添加 for (int i : arr) { bst.add(new kNode(i)); } // 查看树中的值 bst.midShow(); System.out.println("----------"); // 查找 System.out.println(bst.search(10).value); System.out.println(bst.search(20)); System.out.println("----------"); // 测试 kNode p1 = bst.searchParent(10); System.out.println(p1.value); System.out.println("----------"); // 删除 bst.delete(9); bst.midShow(); } } class BinarySortTree { kNode root; // 新增节点 public void add(kNode node) { if (root == null) { root = node; } else { root.add(node); } } /** * 中序遍历二叉排序树，从小到大排序 */ public void midShow() { if (root != null) { root.midShow(root); } } // 查找 public kNode search(int value) { if (root == null) return null; else return root.search(value); } /** * 删除节点 * @param value */ public void delete(int value) { if (root == null) { return; } else { // 找到这个节点 kNode target = search(value); // 如果没有 if (target == null) { return; } // 找父节点 kNode parent = searchParent(value); // 删除节点是叶子节点 if (target.leftNode==null&&target.rightNode==null) { // 要删除的是左子节点 if (parent.leftNode.value == value) { parent.leftNode = null; } // 要删除的是右子节点 else { parent.rightNode = null; } } } } /** * 搜索父节点 * @param value * @return */ public kNode searchParent(int value) { if (root==null) { return null; } else { return root.searchParent(value); } } } class kNode { int value; kNode leftNode; kNode rightNode; public kNode(int value) { this.value = value; } /** * 向子树中添加节点 * @param node */ public void add(kNode node) { if (node == null) return; // 判断传入节点的值比当前子树的根节点大还是小 // 添加节点比当前节点的值更小 if (node.value < this.value) { // 左为空 if (this.leftNode == null) this.leftNode = node; else this.leftNode.add(node); } else { // 右为空 if (this.rightNode == null) this.rightNode = node; else this.rightNode.add(node); } } /** * 中序遍历 * @param node */ public void midShow(kNode node) { if (node == null) return; midShow(node.leftNode); System.out.println(node.value); midShow(node.rightNode); } /** * 查找节点 * @param value */ public kNode search(int value) { if(this.value == value) { return this; } else if (this.value > value) { if (leftNode == null) return null; return leftNode.search(value); } else { if (rightNode == null) return null; return rightNode.search(value); } } /** * 搜索父节点 * @param value * @return */ public kNode searchParent(int value) { if ((this.leftNode != null && this.leftNode.value==value) || (this.rightNode != null && this.rightNode.value==value)) { return this; } else { if (this.value > value && this.leftNode != null) { return this.leftNode.searchParent(value); } else if (this.value < value && this.rightNode != null) { return this.rightNode.searchParent(value); } } return null; } }

赫夫曼树

package 数据结构与算法; import java.util.ArrayList; import java.util.Collections; // 最优二叉树 // 是n个带权 ‘叶子节点’ 构成的所有二叉树中 ‘带权路径’ 最小的二叉树 // 带权路径WPL // 权值越大的结点离根节点越近 // 赫夫曼编码的运用 public class 树_赫夫曼树 { public static void main(String[] args) { int[] arr = { 3, 7, 8, 29, 5, 11, 23, 14 }; myNode node = createHuffmanTree(arr); System.out.println(node); } // 构建赫夫曼树 /** * * @param arr * @return */ public static myNode createHuffmanTree(int[] arr) { // 利用数组创建若干颗二叉树 ArrayList<myNode> nodes = new ArrayList<>(); for (int value : arr) { nodes.add(new myNode(value)); } // 处理 while (nodes.size() > 1) { // 排序 Collections.sort(nodes); // 取出权值最小的两个二叉树 // 取出权值最小的二叉树 myNode left = nodes.get(nodes.size() - 1); // 取出权值次小的二叉树 myNode right = nodes.get(nodes.size() - 2); // 创建一颗新的二叉树 myNode parent = new myNode(left.value + right.value); // 把取出来的两个二叉树移除 nodes.remove(left); nodes.remove(right); // 放入原来的二叉树集合中 nodes.add(parent); } return nodes.get(0); } } class myNode implements Comparable<myNode> { int value; myNode left; myNode right; public myNode(int value) { this.value = value; } // 重写(排序方式) @Override public int compareTo(myNode o) { return -this.value - o.value; } // 输出格式 @Override public String toString() { return "Node [value=" + value + "]"; } }

完全二叉树（树的顺序存储）

package 数据结构与算法; // 顺序存储的二叉树通常只考虑完全二叉树 // 第n个元素的左子节点是：2*n+1 // 第n个元素的右子节点是：2*n+2 // 第n个元素的父节点是： n-1 >> 1 // 数组以 0 开始 public class 树的顺序存储 { public static void main(String[] args) { int[] data = {1, 2, 3, 4, 5, 6, 7}; ArrayBinaryTree tree = new ArrayBinaryTree(data); tree.frontShow(0); } } class ArrayBinaryTree { int [] data; public ArrayBinaryTree(int[] data) { this.data = data; } public void frontShow(int index) { if (data == null || data.length == 0) { return; } // 先遍历当前节点内容 System.out.println(data[index]); // 2*index+1左子树 if (2*index+1 < data.length) frontShow(2*index+1); // 2*index+2 if (2*index+2 < data.length) frontShow(2*index+2); } }

TODO