《java实现树和二叉树》 桃扇骨 2022-02-28 03:56 231阅读 0赞 ### 《java实现树和二叉树》 ### * 父节点表示树 * 子节点表示树(未掌握) * 顺序存储二叉树 * 链式存储二叉树 * 三叉链表存储的二叉树 * 哈夫曼树(带权路径最短的树) 未掌握 * 排序二叉树(未掌握 重点) * 红黑树(未掌握) # 父节点表示树 # 树中除根结点外每个结点都有一个父节点，要记录树中结点与结点直接的关系，只需要给每一个结点增加一个parent的父节点索引，根节点的parent索引为-1，如此将所有的结点存储于结点数组中，结点数组就是相当于一颗树。新增一个树结点只需要存入数据和parent索引，查找某个结点的所有子节点，只需要遍历所有结点的parent索引，相等即用List存储。 **如何遍历父节点表示树的深度(难点)**？遍历所有的结点数组array，得到结点的parent索引后p，看array\[p\]是否为空，或者p == -1，那么该次深度遍历结果结束，进行下一个结点自下而上计算深度，遍历出最大深度即是树的深度。 import java.util.ArrayList; import java.util.List; public class TreeParent<E> { public static class Node<T> { T data; // 记录其父节点的位置 int parent; public Node() { } public Node(T data) { this.data = data; } public Node(T data , int parent) { this.data = data; this.parent = parent; } public String toString() { return "TreeParent$Node[data=" + data + ", parent=" + parent + "]"; } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; // 使用一个Node[]数组来记录该树里的所有节点 private Node<E>[] nodes; // 记录节点数 private int nodeNums; // 以指定根节点创建树 @SuppressWarnings("unchecked") public TreeParent(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data , -1); nodeNums++; } // 以指定根节点、指定treeSize创建树 @SuppressWarnings("unchecked") public TreeParent(E data ,int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data , -1); nodeNums++; } // 为指定节点添加子节点 public void addNode(E data , Node parent) { for (int i = 0 ; i < treeSize ; i++) { // 找到数组中第一个为null的元素，该元素保存新节点 if (nodes[i] == null) { //创建新节点，并用指定的数组元素保存它 nodes[i] = new Node<E>(data , pos(parent));; nodeNums++; return; } } throw new RuntimeException("该树已满，无法添加新节点"); } // 判断树是否为空。 public boolean empty() { // 根节点是否为null return nodes[0] == null; } // 返回根节点 public Node<E> root() { // 返回根节点 return nodes[0]; } // 返回指定节点（非根节点）的父节点。 public Node<E> parent(Node node) { // 每个节点的parent记录了其父节点的位置 return nodes[node.parent]; } // 返回指定节点（非叶子节点）的所有子节点。 public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); for (int i = 0 ; i < treeSize ; i++) { // 如果当前节点的父节点的位置等于parent节点的位置 if (nodes[i] != null && nodes[i].parent == pos(parent)) { list.add(nodes[i]); } } return list; } // 返回该树的深度。 public int deep() { // 用于记录节点的最大深度 int max = 0; for(int i = 0 ; i < treeSize && nodes[i] != null ; i++) { // 初始化本节点的深度 int def = 1; // m记录当前节点的父节点的位置 int m = nodes[i].parent; // 如果其父节点存在 while(m != -1 && nodes[m] != null) { // 向上继续搜索父节点 m = nodes[m].parent; def++; } if(max < def) { max = def; } } // 返回最大深度 return max; } // 返回包含指定值的节点。 public int pos(Node node) { for (int i = 0 ; i < treeSize ; i++) { // 找到指定节点 if (nodes[i] == node) { return i; } } return -1; } public static void main(String[] args) { TreeParent<String> tp = new TreeParent<String>("root"); TreeParent.Node root = tp.root(); System.out.println(root); tp.addNode("节点1" , root); System.out.println("此树的深度:" + tp.deep()); tp.addNode("节点2" , root); // 获取根节点的所有子节点 List<TreeParent.Node<String>> nodes = tp.children(root); System.out.println("根节点的第一个子节点：" + nodes.get(0)); // 为根节点的第一个子节点新增一个子节点 tp.addNode("节点3" , nodes.get(0)); System.out.println("此树的深度:" + tp.deep()); } } 运行结果： ![在这里插入图片描述][20190324161854683.png] # 子节点表示树(未掌握) # 父节点表示法思想是让每个节点都“记住”它父节点的索引，而子节点表示法，每个节点要记住多个子节点，则需要采用“子节点链”表示法。 需要注意： 1. TreeChild需要有两个内部类，SonNode与Node，其中SonNode是链表，只存储当前结点的index 2. TreeChild中底层还是使用Node\[\]数组，Node中还有变量data存储数值 3. TreeChild中添加一个结点时，add()函数要传入该结点值与结点的父节点，添加时要遍历所有的Node\[\]数组，如果有空，则新建Node存储于该位置，接下来需要看parent是否有子节点链，有则遍历子节点链到最后，维护该结点与父节点的关系。 4. **递归求深度(难)：当每个结点的子树用链式存储，递归求树的深度比较复杂，每棵子树的深度为其所有子树的最大深度 + 1** import java.util.*; public class TreeChild<E> { private static class SonNode { // 记录当前节点的位置 private int pos; private SonNode next; public SonNode(int pos , SonNode next) { this.pos = pos; this.next = next; } } public static class Node<T> { T data; // 记录第一个子节点 SonNode first; public Node(T data) { this.data = data; this.first = null; } public String toString() { if (first != null) { return "TreeChild$Node[data=" + data + ", first=" + first.pos + "]"; } else { return "TreeChild$Node[data=" + data + ", first=-1]"; } } } private final int DEFAULT_TREE_SIZE = 100; private int treeSize = 0; // 使用一个Node[]数组来记录该树里的所有节点 private Node<E>[] nodes; // 记录节点数 private int nodeNums; // 以指定根节点创建树 @SuppressWarnings("unchecked") public TreeChild(E data) { treeSize = DEFAULT_TREE_SIZE; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 以指定根节点、指定treeSize创建树 @SuppressWarnings("unchecked") public TreeChild(E data ,int treeSize) { this.treeSize = treeSize; nodes = new Node[treeSize]; nodes[0] = new Node<E>(data); nodeNums++; } // 为指定节点添加子节点 public void addNode(E data , Node parent) { for (int i = 0 ; i < treeSize ; i++) { // 找到数组中第一个为null的元素，该元素保存新节点 if (nodes[i] == null) { // 创建新节点，并用指定数组元素来保存它 nodes[i] = new Node<E>(data); if (parent.first == null) { parent.first = new SonNode(i , null); } else { SonNode next = parent.first; while (next.next != null) { next = next.next; } next.next = new SonNode(i , null); } nodeNums++; return; } } throw new RuntimeException("该树已满，无法添加新节点"); } // 判断树是否为空。 public boolean empty() { // 根节点是否为null return nodes[0] == null; } // 返回根节点 public Node<E> root() { // 返回根节点 return nodes[0]; } // 返回指定节点（非叶子节点）的所有子节点。 public List<Node<E>> children(Node parent) { List<Node<E>> list = new ArrayList<Node<E>>(); // 获取parent节点的第一个子节点 SonNode next = parent.first; // 沿着孩子链不断搜索下一个孩子节点 while (next != null) { // 添加孩子链中的节点 list.add(nodes[next.pos]); next = next.next; } return list; } // 返回指定节点（非叶子节点）的第index个子节点。 public Node<E> child(Node parent , int index) { // 获取parent节点的第一个子节点 SonNode next = parent.first; // 沿着孩子链不断搜索下一个孩子节点 for (int i = 0 ; next != null ; i++) { if (index == i) { return nodes[next.pos]; } next = next.next; } return null; } // 返回该树的深度。 public int deep() { // 获取该树的深度 return deep(root()); } // 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1 private int deep(Node node) { if (node.first == null) { return 1; } else { // 记录其所有子树的最大深度 int max = 0; SonNode next = node.first; // 沿着孩子链不断搜索下一个孩子节点 while (next != null) { // 获取以其子节点为根的子树的深度 int tmp = deep(nodes[next.pos]); if (tmp > max) { max = tmp; } next = next.next; } // 最后返回其所有子树的最大深度 + 1 return max + 1; } } // 返回包含指定值的节点。 public int pos(Node node) { for (int i = 0 ; i < treeSize ; i++) { // 找到指定节点 if (nodes[i] == node) { return i; } } return -1; } public static void main(String[] args) { TreeChild<String> tp = new TreeChild<String>("root"); TreeChild.Node root = tp.root(); System.out.println("根节点：" + root); tp.addNode("节点1" , root); tp.addNode("节点2" , root); tp.addNode("节点3" , root); System.out.println("添加子节点后的根节点：" + root); System.out.println("此树的深度:" + tp.deep()); // 获取根节点的所有子节点 List<TreeChild.Node<String>> nodes = tp.children(root); System.out.println("根节点的第一个子节点：" + nodes.get(0)); // 为根节点的第一个子节点新增一个子节点 tp.addNode("节点4" , nodes.get(0)); System.out.println("根节点的第一个子节点：" + nodes.get(0)); System.out.println("此树的深度:" + tp.deep()); } } 运行结果： ![在这里插入图片描述][20190325152837475.png] # 顺序存储二叉树 # 顺序存储二叉树是最简单实现的二叉树，思想是将树中不同的节点存入数组的固定的位置。比如，根节点永远使用数组的第一个元素来保存，第二层的第2个节点，永远使用数组的第3个元素来保存:第三层最右边的节点，永远使用数组的第7个元素来保存，一依此类推。但是还是要初始化顺序存储二叉树的数组大小，每次添加结点传入参数父节点的index，以及该结点是父节点的左结点还是右结点，决定了存储在Object\[2*index +1\]还是在Object\[2*index +2\]中。 public class ArrayBinTree<T> { // 使用数组来记录该树的所有节点 private Object[] datas; private int DEFAULT_DEEP = 8; // 保存该树的深度 private int deep; private int arraySize; // 以默认的深度来创建二叉树 public ArrayBinTree() { this.deep = DEFAULT_DEEP; this.arraySize = (int)Math.pow(2 , deep) - 1; datas = new Object[arraySize]; } // 以指定深度来创建二叉树 public ArrayBinTree(int deep) { this.deep = deep; this.arraySize = (int)Math.pow(2 , deep) - 1; datas = new Object[arraySize]; } // 以指定深度,指定根节点创建二叉树 public ArrayBinTree(int deep , T data) { this.deep = deep; this.arraySize = (int)Math.pow(2 , deep) - 1; datas = new Object[arraySize]; datas[0] = data; } /** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param left 是否为左节点 */ public void add(int index , T data , boolean left) { if (datas[index] == null) { throw new RuntimeException(index + "处节点为空，无法添加子节点"); } if (2 * index + 1 >= arraySize) { throw new RuntimeException("树底层的数组已满，树越界异常"); } // 添加左子节点 if (left) { datas[2 * index + 1] = data; } else { datas[2 * index + 2] = data; } } // 判断二叉树是否为空。 public boolean empty() { // 根据根元素来判断二叉树是否为空 return datas[0] == null; } // 返回根节点。 @SuppressWarnings("unchecked") public T root() { return (T)datas[0] ; } // 返回指定节点（非根节点）的父节点。 @SuppressWarnings("unchecked") public T parent(int index) { return (T)datas[(index - 1) / 2] ; } // 返回指定节点（非叶子）的左子节点。 // 当左子节点不存在时返回null。 @SuppressWarnings("unchecked") public T left(int index) { if (2 * index + 1 >= arraySize) { throw new RuntimeException("该节点为叶子节点，无子节点"); } return (T)datas[index * 2 + 1] ; } // 返回指定节点（非叶子）的右子节点。 // 当右子节点不存在时返回null。 @SuppressWarnings("unchecked") public T right(int index) { if (2 * index + 1 >= arraySize) { throw new RuntimeException("该节点为叶子节点，无子节点"); } return (T)datas[index * 2 + 2] ; } // 返回该二叉树的深度。 public int deep(int index) { return deep; } // 返回指定节点的位置。 public int pos(T data) { // 该循环实际上就是按广度遍历来搜索每个节点 for (int i = 0 ; i < arraySize ; i++) { if (datas[i].equals(data)) { return i; } } return -1; } public String toString() { return java.util.Arrays.toString(datas); } public static void main(String[] args) { ArrayBinTree<String> binTree = new ArrayBinTree<String>(4, "根"); binTree.add(0 , "第二层右子节点" , false); binTree.add(2 , "第三层右子节点" , false); binTree.add(6 , "第四层右子节点" , false); System.out.println(binTree); } } 运行结果： ![在这里插入图片描述][20190325154423133.png] # 链式存储二叉树 # 二叉树存储添加结点，除了指定结点的数据，还需要指定父节点，以及插入的该结点是否为左结点。二叉树链式存储有左右子节点，递归求树的深度会相对容易。 public class TwoLinkBinTree<E> { public static class TreeNode { Object data; TreeNode left; TreeNode right; public TreeNode() { } public TreeNode(Object data) { this.data = data; } public TreeNode(Object data , TreeNode left , TreeNode right) { this.data = data; this.left = left; this.right = right; } } private TreeNode root; // 以默认的构造器来创建二叉树 public TwoLinkBinTree() { this.root = new TreeNode(); } // 以指定根元素来创建二叉树 public TwoLinkBinTree(E data) { this.root = new TreeNode(data); } /** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param isLeft 是否为左节点 * @return 新增的节点 */ public TreeNode addNode(TreeNode parent , E data , boolean isLeft) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } if (isLeft && parent.left != null) { throw new RuntimeException(parent + "节点已有左子节点，无法添加左子节点"); } if (!isLeft && parent.right != null) { throw new RuntimeException(parent + "节点已有右子节点，无法添加右子节点"); } TreeNode newNode = new TreeNode(data); if (isLeft) { // 让父节点的left引用指向新节点 parent.left = newNode; } else { // 让父节点的right引用指向新节点 parent.right = newNode; } return newNode; } // 判断二叉树是否为空。 public boolean empty() { // 根据根元素来判断二叉树是否为空 return root.data == null; } // 返回根节点。 public TreeNode root() { if (empty()) { throw new RuntimeException("树为空，无法访问根节点"); } return root; } // 返回指定节点（非根节点）的父节点。 public E parent(TreeNode node) { // 对于二叉链表存储法，如果要访问指定节点的父节点必须遍历二叉树 return null; } // 返回指定节点（非叶子）的左子节点。当左子节点不存在时返回null @SuppressWarnings("unchecked") public E leftChild(TreeNode parent) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } return parent.left == null ? null : (E)parent.left.data; } // 返回指定节点（非叶子）的右子节点。当右子节点不存在时返回null @SuppressWarnings("unchecked") public E rightChild(TreeNode parent) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } return parent.right == null ? null : (E)parent.right.data; } // 返回该二叉树的深度。 public int deep() { // 获取该树的深度 return deep(root); } // 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1 private int deep(TreeNode node) { if (node == null) { return 0; } // 没有子树 if (node.left == null && node.right == null) { return 1; } else { int leftDeep = deep(node.left); int rightDeep = deep(node.right); // 记录其所有左、右子树中较大的深度 int max = leftDeep > rightDeep ? leftDeep : rightDeep; // 返回其左右子树中较大的深度 + 1 return max + 1; } } public static void main(String[] args) { TwoLinkBinTree<String> binTree = new TwoLinkBinTree<>("根节点"); // 依次添加节点 TwoLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root() , "第二层左节点" , true); TwoLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root() , "第二层右节点" ,false ); TwoLinkBinTree.TreeNode tn3 = binTree.addNode(tn2 , "第三层左节点" , true); TwoLinkBinTree.TreeNode tn4 = binTree.addNode(tn2 , "第三层右节点" , false); TwoLinkBinTree.TreeNode tn5 = binTree.addNode(tn3 , "第四层左节点" , true); System.out.println("tn2的左子节点：" + binTree.leftChild(tn2)); System.out.println("tn2的右子节点：" + binTree.rightChild(tn2)); System.out.println(binTree.deep()); } } 运行结果： ![在这里插入图片描述][20190325161712173.png] # 三叉链表存储的二叉树 # 三叉链表存储相对于二叉链存储多了指向父节点的指针，只是在增加删除时需要多维护一下parent。 import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class ThreeLinkBinTree<E> { public static class TreeNode { Object data; TreeNode left; TreeNode right; TreeNode parent; public TreeNode() { } public TreeNode(Object data) { this.data = data; } public TreeNode(Object data , TreeNode left , TreeNode right , TreeNode parent) { this.data = data; this.left = left; this.right = right; this.parent = parent; } public String toString() { return "TreeNode[data=" + data + "]"; } } private TreeNode root; // 以默认的构造器来创建二叉树 public ThreeLinkBinTree() { this.root = new TreeNode(); } // 以指定根元素来创建二叉树 public ThreeLinkBinTree(E data) { this.root = new TreeNode(data); } /** * 为指定节点添加子节点。 * @param index 需要添加子节点的父节点的索引 * @param data 新子节点的数据 * @param isLeft 是否为左节点 * @return 新增的节点 */ public TreeNode addNode(TreeNode parent , E data , boolean isLeft) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } if (isLeft && parent.left != null) { throw new RuntimeException(parent + "节点已有左子节点，无法添加左子节点"); } if (!isLeft && parent.right != null) { throw new RuntimeException(parent + "节点已有右子节点，无法添加右子节点"); } TreeNode newNode = new TreeNode(data); if (isLeft) { // 让父节点的left引用指向新节点 parent.left = newNode; } else { // 让父节点的right引用指向新节点 parent.right = newNode; } // 让新节点的parent引用到parent节点 newNode.parent = parent; return newNode; } // 判断二叉树是否为空。 public boolean empty() { // 根据根元素来判断二叉树是否为空 return root.data == null; } // 返回根节点。 public TreeNode root() { if (empty()) { throw new RuntimeException("树为空，无法访问根节点"); } return root; } // 返回指定节点（非根节点）的父节点。 @SuppressWarnings("unchecked") public E parent(TreeNode node) { if (node == null) { throw new RuntimeException(node + "节点为null，无法访问其父节点"); } return (E)node.parent.data; } // 返回指定节点（非叶子）的左子节点，当左子节点不存在时返回null @SuppressWarnings("unchecked") public E leftChild(TreeNode parent) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } return parent.left == null ? null : (E)parent.left.data; } // 返回指定节点（非叶子）的右子节点，当右子节点不存在时返回null @SuppressWarnings("unchecked") public E rightChild(TreeNode parent) { if (parent == null) { throw new RuntimeException(parent + "节点为null，无法添加子节点"); } return parent.right == null ? null : (E)parent.right.data; } // 返回该二叉树的深度。 public int deep() { // 获取该树的深度 return deep(root); } // 这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1 private int deep(TreeNode node) { if (node == null) { return 0; } // 没有子树 if (node.left == null && node.right == null) { return 1; } else { int leftDeep = deep(node.left); int rightDeep = deep(node.right); // 记录其所有左、右子树中较大的深度 int max = leftDeep > rightDeep ? leftDeep : rightDeep; // 返回其左右子树中较大的深度 + 1 return max + 1; } } // 实现先序遍历 public List<TreeNode> preIterator() { return preIterator(root); } private List<TreeNode> preIterator(TreeNode node) { List<TreeNode> list = new ArrayList<TreeNode>(); // 处理根节点 list.add(node); // 递归处理左子树 if (node.left != null) { list.addAll(preIterator(node.left)); } // 递归处理右子树 if (node.right != null) { list.addAll(preIterator(node.right)); } return list; } // 实现中序遍历 public List<TreeNode> inIterator() { return inIterator(root); } private List<TreeNode> inIterator(TreeNode node) { List<TreeNode> list = new ArrayList<TreeNode>(); // 递归处理左子树 if (node.left != null) { list.addAll(inIterator(node.left)); } // 处理根节点 list.add(node); // 递归处理右子树 if (node.right != null) { list.addAll(inIterator(node.right)); } return list; } public List<TreeNode> postIterator() { return postIterator(root); } // 实现后序遍历 private List<TreeNode> postIterator(TreeNode node) { List<TreeNode> list = new ArrayList<TreeNode>(); // 递归处理左子树 if (node.left != null) { list.addAll(postIterator(node.left)); } // 递归处理右子树 if (node.right != null) { list.addAll(postIterator(node.right)); } // 处理根节点 list.add(node); return list; } // 广度优先遍历 public List<TreeNode> breadthFirst() { Queue<TreeNode> queue = new ArrayDeque<TreeNode>(); List<TreeNode> list = new ArrayList<TreeNode>(); if( root != null) { // 将根元素加入“队列” queue.offer(root); } while(!queue.isEmpty()) { // 将该队列的“头部”的元素添加到List中 list.add(queue.peek()); // 将该队列的“头部”的元素移出队列 TreeNode p = queue.poll(); // 如果左子节点不为null，将它加入“队列” if(p.left != null) { queue.offer(p.left); } // 如果右子节点不为null，将它加入“队列” if(p.right != null) { queue.offer(p.right); } } return list; } public static void main(String[] args) { ThreeLinkBinTree<String> binTree = new ThreeLinkBinTree<>("根节点"); // 依次添加节点 ThreeLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root() , "二左" , true); ThreeLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root() , "二右" ,false ); ThreeLinkBinTree.TreeNode tn3 = binTree.addNode(tn1 , "三左" , true); ThreeLinkBinTree.TreeNode tn4 = binTree.addNode(tn1 , "三右" , false); ThreeLinkBinTree.TreeNode tn5 = binTree.addNode(tn3 , "四右" , false); ThreeLinkBinTree.TreeNode tn6 = binTree.addNode(tn4 , "四右左" , true); ThreeLinkBinTree.TreeNode tn7 = binTree.addNode(tn4 , "四右右" , false); ThreeLinkBinTree.TreeNode tn8 = binTree.addNode(tn5 , "五左" , true); ThreeLinkBinTree.TreeNode tn9 = binTree.addNode(tn5 , "五右" , false); System.out.println(binTree.preIterator()); System.out.println(binTree.inIterator()); System.out.println(binTree.postIterator()); System.out.println(binTree.breadthFirst()); } } 运行结果： ![在这里插入图片描述][20190325162800445.png] # 哈夫曼树(带权路径最短的树) 未掌握 # 节点的带权路径长度:从该节点到根节点之间的路径长度与节点的权的乘积。图11.16表示节点到根结点的路径长度，图11.17树的带权路径长度。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70] 对于哈夫曼树，有一个很重要的定理：对于具有n个叶子节点的哈夫曼树.一共需要2*n-1个节点。因为对于二叉树来说，有三种类型节点，即度数为2的节点、度数为1的节点和度数为0的叶子节点，而哈夫曼树的非叶子节点都是由两个节点合并产生的，所以不会出现度数为1的节点。而生成的非叶子节点的个数为叶子节点个数一1，因此n个叶子节点的哈夫曼树，一共需要2*n一l个节点。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1] 例如下图：先找出最小两个结点即2、4，然后作为一颗二叉树，然后将两者和加入到原来的数组中，而除掉2、4结点，此时数组中有7、6、5，在选出数组最小的两个值作为二叉树左右结点，即5和、6，然后5+6 = 11，再次重复，最后得到的根结点权重18。创建哈夫曼树需要事先创建结点数组，结点Node用二叉链链式存储结构。 难点：每次需要对节点数组进行排序。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2] import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class HuffmanTree { public static class Node<E> { E data; double weight; Node<E> leftChild; Node<E> rightChild; public Node(E data , double weight) { this.data = data; this.weight = weight; } public String toString() { return "Node[data=" + data + ", weight=" + weight + "]"; } } public static void main(String[] args) { List<Node<String>> nodes = new ArrayList<>(); nodes.add(new Node<String>("A" , 40.0)); nodes.add(new Node<String>("B" , 7.0)); nodes.add(new Node<String>("C" , 10.0)); nodes.add(new Node<String>("D" , 30.0)); nodes.add(new Node<String>("E" , 12.0)); nodes.add(new Node<String>("F" , 2.0)); Node<String> root = HuffmanTree.createTree(nodes); System.out.println(breadthFirst(root)); } /** * 构造哈夫曼树 * @param nodes 节点集合 * @return 构造出来的哈夫曼树的根节点 */ private static <E> Node<E> createTree(List<Node<E>> nodes) { // 只要nodes数组中还有2个以上的节点 while (nodes.size() > 1) { quickSort(nodes); // 获取权值最小的两个节点 Node<E> left = nodes.get(nodes.size() - 1); Node<E> right = nodes.get(nodes.size() - 2); // 生成新节点，新节点的权值为两个子节点的权值之和 Node<E> parent = new Node<>(null , left.weight + right.weight); // 让新节点作为权值最小的两个节点的父节点 parent.leftChild = left; parent.rightChild = right; // 删除权值最小的两个节点 nodes.remove(nodes.size() - 1); nodes.remove(nodes.size() - 1); // 将新生成的父节点添加到集合中 nodes.add(parent); } // 返回nodes集合中唯一的节点，也就是根节点 return nodes.get(0); } // 将指定数组的i和j索引处的元素交换 private static <E> void swap(List<Node<E>> nodes, int i, int j) { Node<E> tmp; tmp = nodes.get(i); nodes.set(i , nodes.get(j)); nodes.set(j , tmp); } // 实现快速排序算法，用于对节点进行排序 private static <E> void subSort(List<Node<E>> nodes , int start , int end) { // 需要排序 if (start < end) { // 以第一个元素作为分界值 Node base = nodes.get(start); // i从左边搜索，搜索大于分界值的元素的索引 int i = start; // j从右边开始搜索，搜索小于分界值的元素的索引 int j = end + 1; while(true) { // 找到大于分界值的元素的索引，或i已经到了end处 while(i < end && nodes.get(++i).weight >= base.weight); // 找到小于分界值的元素的索引，或j已经到了start处 while(j > start && nodes.get(--j).weight <= base.weight); if (i < j) { swap(nodes , i , j); } else { break; } } swap(nodes , start , j); // 递归左子序列 subSort(nodes , start , j - 1); // 递归右边子序列 subSort(nodes , j + 1, end); } } public static <E> void quickSort(List<Node<E>> nodes) { subSort(nodes , 0 , nodes.size() - 1); } // 广度优先遍历 public static List<Node> breadthFirst(Node root) { Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if( root != null) { // 将根元素入“队列” queue.offer(root); } while(!queue.isEmpty()) { // 将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); // 如果左子节点不为null，将它加入“队列” if(p.leftChild != null) { queue.offer(p.leftChild); } // 如果右子节点不为null，将它加入“队列” if(p.rightChild != null) { queue.offer(p.rightChild); } } return list; } } 运行结果： ![在这里插入图片描述][20190325180136783.png] # 排序二叉树(未掌握 重点) # 对于排序二叉树，若按中序遍历就可以得到由小到大的有序序列。 import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class SortedBinTree<T extends Comparable> { static class Node { Object data; Node parent; Node left; Node right; public Node(Object data , Node parent , Node left , Node right) { this.data = data; this.parent = parent; this.left = left; this.right = right; } public String toString() { return "[data=" + data + "]"; } public boolean equals(Object obj) { if (this == obj) { return true; } if (obj.getClass() == Node.class) { Node target = (Node)obj; return data.equals(target.data) && left == target.left && right == target.right && parent == target.parent; } return false; } } private Node root; // 两个构造器用于创建排序二叉树 public SortedBinTree() { root = null; } public SortedBinTree(T o) { root = new Node(o , null , null , null); } // 添加节点 @SuppressWarnings("unchecked") public void add(T ele) { // 如果根节点为null if (root == null) { root = new Node(ele , null , null , null); } else { Node current = root; Node parent = null; int cmp = 0; // 搜索合适的叶子节点，以该叶子节点为父节点添加新节点 do { parent = current; cmp = ele.compareTo(current.data); // 如果新节点的值大于当前节点的值 if (cmp > 0) { // 以右子节点作为当前节点 current = current.right; } // 如果新节点的值小于当前节点的值 else { // 以左子节点作为当前节点 current = current.left; } } while (current != null); // 创建新节点 Node newNode = new Node(ele , parent , null , null); // 如果新节点的值大于父节点的值 if (cmp > 0) { // 新节点作为父节点的右子节点 parent.right = newNode; } // 如果新节点的值小于父节点的值 else { // 新节点作为父节点的左子节点 parent.left = newNode; } } } // 删除节点 public void remove(T ele) { // 获取要删除的节点 Node target = getNode(ele); // 如果要删除的节点为null，直接返回 if (target == null) { return; } // 如果要删除的节点的左、右子树为空 if (target.left == null && target.right == null) { // 如果要删除节点是根节点 if (target == root) { root = null; } else { // 要删除节点是父节点的左子节点 if (target == target.parent.left) { // 将target的父节点的left设为null target.parent.left = null; } // 要删除节点是父节点的左子节点 else { // 将target的父节点的right设为null target.parent.right = null; } target.parent = null; } } // 如果要删除的节点只有右子树 else if (target.left == null && target.right != null) { // 如果要删除节点是根节点 if (target == root) { root = target.right; } else { // 如果要删除节点是父节点的左子节点 if (target == target.parent.left) { // 让target的父节点的left指向target的右子树 target.parent.left = target.right; } // 如果要删除节点是父节点的右子节点 else { // 让target的父节点的right指向target的右子树 target.parent.right = target.right; } //让target的右子树的parent指向target的parent target.right.parent = target.parent; } } // 如果要删除的节点只有左子树 else if(target.left != null && target.right == null) { // 被删除节点是根节点 if (target == root) { root = target.left; } else { // 被删除节点是父节点的左子节点 if (target == target.parent.left) { // 让target的父节点的left指向target的左子树 target.parent.left = target.left; } else { // 让target的父节点的right指向target的左子树 target.parent.right = target.left; } // 让target的左子树的parent指向target的parent target.left.parent = target.parent; } } // 如果要删除节点既有左子树，又有右子树 else { // leftMaxNode用于保存target节点的左子树中值最大的节点 Node leftMaxNode = target.left; // 搜索target节点的左子树中值最大的节点 while (leftMaxNode.right != null) { leftMaxNode = leftMaxNode.right; } // 从原来的子树中删除leftMaxNode节点 leftMaxNode.parent.right = null; // 让leftMaxNode的parent指向target的parent leftMaxNode.parent = target.parent; // 要删除节点是父节点的左子节点 if (target == target.parent.left) { // 让target的父节点的left指向leftMaxNode target.parent.left = leftMaxNode; } // 要删除节点是父节点的右子节点 else { // 让target的父节点的right指向leftMaxNode target.parent.right = leftMaxNode; } leftMaxNode.left = target.left; leftMaxNode.right = target.right; target.parent = target.left = target.right = null; } } // 根据给定的值搜索节点 @SuppressWarnings("unchecked") public Node getNode(T ele) { //从根节点开始搜索 Node p = root; while (p != null) { int cmp = ele.compareTo(p.data); // 如果搜索的值小于当前p节点的值 if (cmp < 0) { // 向左子树搜索 p = p.left; } // 如果搜索的值大于当前p节点的值 else if (cmp > 0) { // 向右子树搜索 p = p.right; } else { return p; } } return null; } // 广度优先遍历 public List<Node> breadthFirst() { Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if( root != null) { // 将根元素加入“队列” queue.offer(root); } while(!queue.isEmpty()) { // 将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); // 如果左子节点不为null，将它加入“队列” if(p.left != null) { queue.offer(p.left); } // 如果右子节点不为null，将它加入“队列” if(p.right != null) { queue.offer(p.right); } } return list; } public static void main(String[] args) { SortedBinTree<Integer> tree = new SortedBinTree<Integer>(); // 添加节点 tree.add(5); tree.add(20); tree.add(10); tree.add(3); tree.add(8); tree.add(15); tree.add(30); System.out.println(tree.breadthFirst()); // 删除节点 tree.remove(20); System.out.println(tree.breadthFirst()); } } 运行结果： ![在这里插入图片描述][20190325182324751.png] # 红黑树(未掌握) # import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Queue; public class RedBlackTree<T extends Comparable> { // 定义红黑树的颜色 private static final boolean RED = false; private static final boolean BLACK = true; static class Node { Object data; Node parent; Node left; Node right; // 节点的默认颜色是黑色 boolean color = BLACK; public Node(Object data , Node parent , Node left , Node right) { this.data = data; this.parent = parent; this.left = left; this.right = right; } public String toString() { return "[data=" + data + ", color=" + color + "]"; } public boolean equals(Object obj) { if (this == obj) { return true; } if (obj.getClass() == Node.class) { Node target = (Node)obj; return data.equals(target.data) && color == target.color && left == target.left && right == target.right && parent == target.parent; } return false; } } private Node root; // 两个构造器用于创建排序二叉树 public RedBlackTree() { root = null; } public RedBlackTree(T o) { root = new Node(o , null , null , null); } // 添加节点 public void add(T ele) { // 如果根节点为null if (root == null) { root = new Node(ele , null , null , null); } else { Node current = root; Node parent = null; int cmp = 0; // 搜索合适的叶子节点，以该叶子节点为父节点添加新节点 do { parent = current; cmp = ele.compareTo(current.data); // 如果新节点的值大于当前节点的值 if (cmp > 0) { // 以右子节点作为当前节点 current = current.right; } // 如果新节点的值小于当前节点的值 else { // 以左子节点作为当前节点 current = current.left; } } while (current != null); // 创建新节点 Node newNode = new Node(ele , parent , null , null); // 如果新节点的值大于父节点的值 if (cmp > 0) { // 新节点作为父节点的右子节点 parent.right = newNode; } // 如果新节点的值小于父节点的值 else { //新节点作为父节点的左子节点 parent.left = newNode; } // 维护红黑树 fixAfterInsertion(newNode); } } // 删除节点 public void remove(T ele) { // 获取要删除的节点 Node target = getNode(ele); // 如果要删除节点的左子树、右子树都不为空 if (target.left != null && target.right != null) { // 找到target节点中序遍历的前一个节点 // s用于保存target节点的左子树中值最大的节点 Node s = target.left; // 搜索target节点的左子树中值最大的节点 while (s.right != null) { s = s.right; } // 用s节点来代替p节点 target.data = s.data; target = s; } // 开始修复它的替换节点，如果该替换节点不为null Node replacement = (target.left != null ? target.left : target.right); if (replacement != null) { // 让replacement的parent指向target的parent replacement.parent = target.parent; // 如果target的parent为null，表明target本身是根节点 if (target.parent == null) { root = replacement; } // 如果target是其父节点的左子节点 else if (target == target.parent.left) { // 让target的父节点left指向replacement target.parent.left = replacement; } // 如果target是其父节点的右子节点 else { // 让target的父节点right指向replacement target.parent.right = replacement; } // 彻底删除target节点 target.left = target.right = target.parent = null; // 修复红黑树 if (target.color == BLACK) { fixAfterDeletion(replacement); } } // target本身是根节点 else if (target.parent == null) { root = null; } else { // target没有子节点，把它当成虚的替换节点。 // 修复红黑树 if (target.color == BLACK) { fixAfterDeletion(target); } if (target.parent != null) { // 如果target是其父节点的左子节点 if (target == target.parent.left) { // 将target的父节点left设为null target.parent.left = null; } // 如果target是其父节点的右子节点 else if (target == target.parent.right) { // 将target的父节点right设为null target.parent.right = null; } // 将target的parent设置null target.parent = null; } } } // 根据给定的值搜索节点 public Node getNode(T ele) { // 从根节点开始搜索 Node p = root; while (p != null) { int cmp = ele.compareTo(p.data); // 如果搜索的值小于当前p节点的值 if (cmp < 0) { // 向左子树搜索 p = p.left; } // 如果搜索的值大于当前p节点的值 else if (cmp > 0) { // 向右子树搜索 p = p.right; } else { return p; } } return null; } // 广度优先遍历 public List<Node> breadthFirst() { Queue<Node> queue = new ArrayDeque<Node>(); List<Node> list = new ArrayList<Node>(); if( root != null) { // 将根元素入“队列” queue.offer(root); } while(!queue.isEmpty()) { // 将该队列的“队尾”的元素添加到List中 list.add(queue.peek()); Node p = queue.poll(); // 如果左子节点不为null，将它入“队列” if(p.left != null) { queue.offer(p.left); } // 如果右子节点不为null，将它入“队列” if(p.right != null) { queue.offer(p.right); } } return list; } // 插入节点后修复红黑树 private void fixAfterInsertion(Node x) { x.color = RED; // 直到x节点的父节点不是根，且x的父节点不是红色 while (x != null && x != root && x.parent.color == RED) { // 如果x的父节点是其父节点的左子节点 if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { // 获取x的父节点的兄弟节点 Node y = rightOf(parentOf(parentOf(x))); // 如果x的父节点的兄弟节点是红色 if (colorOf(y) == RED) { // 将x的父节点设为黑色 setColor(parentOf(x), BLACK); // 将x的父节点的兄弟节点设为黑色 setColor(y, BLACK); // 将x的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); x = parentOf(parentOf(x)); } // 如果x的父节点的兄弟节点是黑色 else { // 如果x是其父节点的右子节点 if (x == rightOf(parentOf(x))) { // 将x的父节点设为x x = parentOf(x); rotateLeft(x); } // 把x的父节点设为黑色 setColor(parentOf(x), BLACK); // 把x的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); rotateRight(parentOf(parentOf(x))); } } // 如果x的父节点是其父节点的右子节点 else { // 获取x的父节点的兄弟节点 Node y = leftOf(parentOf(parentOf(x))); // 如果x的父节点的兄弟节点是红色 if (colorOf(y) == RED) { // 将x的父节点设为黑色。 setColor(parentOf(x), BLACK); // 将x的父节点的兄弟节点设为黑色 setColor(y, BLACK); // 将x的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); // 将x设为x的父节点的节点 x = parentOf(parentOf(x)); } // 如果x的父节点的兄弟节点是黑色 else { // 如果x是其父节点的左子节点 if (x == leftOf(parentOf(x))) { //将x的父节点设为x x = parentOf(x); rotateRight(x); } // 把x的父节点设为黑色 setColor(parentOf(x), BLACK); // 把x的父节点的父节点设为红色 setColor(parentOf(parentOf(x)), RED); rotateLeft(parentOf(parentOf(x))); } } } // 将根节点设为黑色 root.color = BLACK; } // 删除节点后修复红黑树 private void fixAfterDeletion(Node x) { // 直到x不是根节点，且x的颜色是黑色 while (x != root && colorOf(x) == BLACK) { // 如果x是其父节点的左子节点 if (x == leftOf(parentOf(x))) { // 获取x节点的兄弟节点 Node sib = rightOf(parentOf(x)); // 如果sib节点是红色 if (colorOf(sib) == RED) { // 将sib节点设为黑色 setColor(sib, BLACK); // 将x的父节点设为红色 setColor(parentOf(x), RED); rotateLeft(parentOf(x)); // 再次将sib设为x的父节点的右子节点 sib = rightOf(parentOf(x)); } // 如果sib的两个子节点都是黑色 if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { // 将sib设为红色 setColor(sib, RED); // 让x等于x的父节点 x = parentOf(x); } else { // 如果sib的只有右子节点是黑色 if (colorOf(rightOf(sib)) == BLACK) { // 将sib的左子节点也设为黑色 setColor(leftOf(sib), BLACK); // 将sib设为红色 setColor(sib, RED); rotateRight(sib); sib = rightOf(parentOf(x)); } // 设置sib的颜色与x的父节点的颜色相同 setColor(sib, colorOf(parentOf(x))); // 将x的父节点设为黑色 setColor(parentOf(x), BLACK); // 将sib的右子节点设为黑色 setColor(rightOf(sib), BLACK); rotateLeft(parentOf(x)); x = root; } } // 如果x是其父节点的右子节点 else { // 获取x节点的兄弟节点 Node sib = leftOf(parentOf(x)); // 如果sib的颜色是红色 if (colorOf(sib) == RED) { // 将sib的颜色设为黑色 setColor(sib, BLACK); // 将sib的父节点设为红色 setColor(parentOf(x), RED); rotateRight(parentOf(x)); sib = leftOf(parentOf(x)); } // 如果sib的两个子节点都是黑色 if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { // 将sib设为红色 setColor(sib, RED); //让x等于x的父节点 x = parentOf(x); } else { // 如果sib只有左子节点是黑色 if (colorOf(leftOf(sib)) == BLACK) { // 将sib的右子节点也设为黑色 setColor(rightOf(sib), BLACK); // 将sib设为红色 setColor(sib, RED); rotateLeft(sib); sib = leftOf(parentOf(x)); } // 将sib的颜色设为与x的父节点颜色相同 setColor(sib, colorOf(parentOf(x))); // 将x的父节点设为黑色 setColor(parentOf(x), BLACK); // 将sib的左子节点设为黑色 setColor(leftOf(sib), BLACK); rotateRight(parentOf(x)); x = root; } } } setColor(x, BLACK); } // 获取指定节点的颜色 private boolean colorOf(Node p) { return (p == null ? BLACK : p.color); } // 获取指定节点的父节点 private Node parentOf(Node p) { return (p == null ? null: p.parent); } // 为指定节点设置颜色 private void setColor(Node p, boolean c) { if (p != null) { p.color = c; } } // 获取指定节点的左子节点 private Node leftOf(Node p) { return (p == null) ? null: p.left; } // 获取指定节点的右子节点 private Node rightOf(Node p) { return (p == null) ? null: p.right; } /** * 执行如下转换 * p r * r p * q q */ private void rotateLeft(Node p) { if (p != null) { // 取得p的右子节点 Node r = p.right; Node q = r.left; // 将r的左子节点链到p的右节点链上 p.right = q; // 让r的左子节点的parent指向p节点 if (q != null) { q.parent = p; } r.parent = p.parent; // 如果p已经是根节点 if (p.parent == null) { root = r; } // 如果p是其父节点的左子节点 else if (p.parent.left == p) { // 将r设为p的父节点的左子节点 p.parent.left = r; } else { // 将r设为p的父节点的右子节点 p.parent.right = r; } r.left = p; p.parent = r; } } /** * 执行如下转换 * p l * l p * q q */ private void rotateRight(Node p) { if (p != null) { // 取得p的左子节点 Node l = p.left; Node q = l.right; // 将l的右子节点链到p的左节点链上 p.left = q; // 让l的右子节点的parent指向p节点 if (q != null) { q.parent = p; } l.parent = p.parent; // 如果p已经是根节点 if (p.parent == null) { root = l; } // 如果p是其父节点的右子节点 else if (p.parent.right == p) { // 将l设为p的父节点的右子节点 p.parent.right = l; } else { // 将l设为p的父节点的左子节点 p.parent.left = l; } l.right = p; p.parent = l; } } // 实现中序遍历 public List<Node> inIterator() { return inIterator(root); } private List<Node> inIterator(Node node) { List<Node> list = new ArrayList<Node>(); // 递归处理左子树 if (node.left != null) { list.addAll(inIterator(node.left)); } // 处理根节点 list.add(node); // 递归处理右子树 if (node.right != null) { list.addAll(inIterator(node.right)); } return list; } public static void main(String[] args) { RedBlackTree<Integer> tree = new RedBlackTree<Integer>(); //添加节点 tree.add(5); tree.add(20); tree.add(10); tree.add(3); tree.add(8); tree.add(15); tree.add(30); System.out.println(tree.breadthFirst()); //删除节点 tree.remove(20); System.out.println(tree.breadthFirst()); // System.out.println(tree.inIterator()); } } 运行结果： ![在这里插入图片描述][20190325182641608.png] [20190324161854683.png]: /images/20220228/1d4f78636da54be79b392744553e86b9.png [20190325152837475.png]: /images/20220228/51df6a850553466aa3857efa8bfc7430.png [20190325154423133.png]: /images/20220228/3bd387287c06485f9ea9b54ebb9d2d7c.png [20190325161712173.png]: /images/20220228/78a5a6fbd44847aba651077daf739463.png [20190325162800445.png]: /images/20220228/ca30f825a60c44608e323a89a2dafdcf.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70]: /images/20220228/f70bc76d56324c0ebe0e7008c570f86c.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 1]: /images/20220228/d3d7dce92ff44b4aabf89c7a5c06169b.png [watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTI2MjQ1Mw_size_16_color_FFFFFF_t_70 2]: /images/20220228/c98584c11e674a1585f02a84a299dca2.png [20190325180136783.png]: /images/20220228/489d1fb7f1f04f93bdffce870f8512fa.png [20190325182324751.png]: /images/20220228/dc8fdfe40477465cbdd66f7c749571c8.png [20190325182641608.png]: /images/20220228/e9042931e53748609e1ab00f418d3f7e.png
相关 树和二叉树 树和二叉树 一、基本术语 二、性质 三、前/中/后序遍历 四、霍夫曼树（满二叉树） 五、图的遍历 一、基本术语 1. 树结点：包含 谁借莪１个温暖的怀抱￠/ 2023年10月05日 14:41/ 0 赞/ 25 阅读
相关 二叉树和排序二叉树 二叉树 > 相关名词 > > 根节点 > > 左叶子节点 > > 右叶子节点 > > 子树 > > 高度 > 二叉树的排序方式： > > - 广度遍历（ 灰太狼/ 2023年08月17日 16:53/ 0 赞/ 230 阅读
相关 树和二叉树 树型结构是一类重要的非线性数据结构. 树是n个结点的有限集.树的结构定义是一个递归定义,即在树的定义中又用到树的概念,它道出树的固有特性. 树的结点包含一个 骑猪看日落/ 2023年07月01日 15:56/ 0 赞/ 2 阅读
相关 树和二叉树 一、树的概述 1. 树结构概述 根节点：该节点没有父节点 双亲结点：有父节点和子节点 子节点：一个节点的下面一个节点为子节 拼搏现实的明天。/ 2023年06月23日 06:54/ 0 赞/ 33 阅读
相关 树和二叉树 树的定义 树（Tree）是n(n>=0)个结点的有限集。在任意一棵非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结点可分为m(m>0) 末蓝、/ 2022年06月08日 00:49/ 0 赞/ 230 阅读
相关 树和二叉树 树 > 不同于队列、栈等一对一的数据结构，树是一对多的数据结构。树（Tree）是n（n>=0）各节点的有限集。当n=0，为空树。 在任意一颗非空树中： 1. 有且只 落日映苍穹つ/ 2022年05月16日 01:36/ 0 赞/ 300 阅读
相关 Java实现二叉树 这里创建二叉树是顺序结构存储二叉树原理，即一个节点 i 的左孩子为 i\2+1,右孩子为 i\2+2。程序创建的二叉树如图所示： ![70][] Demo： im 缺乏、安全感/ 2022年05月14日 07:36/ 0 赞/ 182 阅读
相关 《java实现树和二叉树》 《java实现树和二叉树》 父节点表示树 子节点表示树(未掌握) 顺序存储二叉树 链式存储二叉树 三叉链表存储的二叉树 哈夫曼树(带权 桃扇骨/ 2022年02月28日 03:56/ 0 赞/ 232 阅读
谁借莪１个温暖的怀抱￠
灰太狼
骑猪看日落
太过爱你忘了你带给我的痛
还没有评论，来说两句吧...