目 录 二叉树与数组的转换 顺序存储的二叉树通常情况，只考虑完全二叉树！ 第n个元素的左子节点是：2*n+1； 将 数组 看成 完全二叉树！以数组的方式遍历二叉树！ 因为 根节点的左子节点 也会有 左子节点，所以需要递归。 大顶堆：父节点永远大于子节点！数值大的 在 上面！ 大顶堆 是 从大到小，小顶堆 是 从小到大！ 升序排序 使用 大顶堆；降序排序 使用 小顶堆。 左右指针，如果没有存东西，则 可以 将 该节点的指针 指向 该节点的前一个节点 或 后一个节点。 找一个标记 区分 左（右子树）、前（后节点）。 线索化二叉树时，一个节点的前一个节点，叫前驱节点； 不需要 使用 递归！！！
P34-4.7顺序存储的二叉树的概述
第n个元素的右子节点是：2*n+2；
第n个元素的父节点是：(n-1)/2；
P35-4.8顺序存储的二叉树的遍历
P36-4.9常用排序算法之堆排序
package demo4; import java.util.Arrays; public class HeapSort { public static void main(String[] args) { int[] arr = new int[] { 9, 6, 8, 7, 0, 1, 10, 4, 2 }; heapSort(arr); System.out.println(Arrays.toString(arr)); } public static void heapSort(int[] arr) { // 开始位置是最后一个非叶子节点，即最后一个节点的父节点 int start = (arr.length - 1) / 2; // 调整为大顶堆 for (int i = start; i >= 0; i--) { maxHeap(arr, arr.length, i); } // 先把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆 for (int i = arr.length - 1; i > 0; i--) { int temp = arr[0]; arr[0] = arr[i]; arr[i] = temp; maxHeap(arr, i, 0); } } public static void maxHeap(int[] arr, int size, int index) { // 左子节点 int leftNode = 2 * index + 1; // 右子节点 int rightNode = 2 * index + 2; int max = index; // 和两个子节点分别对比，找出最大的节点 if (leftNode < size && arr[leftNode] > arr[max]) { max = leftNode; } if (rightNode < size && arr[rightNode] > arr[max]) { max = rightNode; } // 交换位置 if (max != index) { int temp = arr[index]; arr[index] = arr[max]; arr[max] = temp; // 交换位置以后，可能会破坏之前排好的堆，所以，之前的排好的堆需要重新调整 maxHeap(arr, size, max); } } }P37-4.10线索二叉树的概述
线索化二叉树时，一个节点的后一个节点，叫后继节点。P38-4.11线索二叉树代码实现
1、TestThreadedBinaryTree.java
package demo7; public class TestThreadedBinaryTree { public static void main(String[] args) { // 创建一颗树 ThreadedBinaryTree binTree = new ThreadedBinaryTree(); // 创建一个根节点 ThreadedNode root = new ThreadedNode(1); // 把根节点赋给树 binTree.setRoot(root); // 创建一个左节点 ThreadedNode rootL = new ThreadedNode(2); // 把新创建的节点设置为根节点的子节点 root.setLeftNode(rootL); // 创建一个右节点 ThreadedNode rootR = new ThreadedNode(3); // 把新创建的节点设置为根节点的子节点 root.setRightNode(rootR); // 为第二层的左节点创建两个子节点 rootL.setLeftNode(new ThreadedNode(4)); ThreadedNode fiveNode = new ThreadedNode(5); rootL.setRightNode(fiveNode); // 为第二层的右节点创建两个子节点 rootR.setLeftNode(new ThreadedNode(6)); rootR.setRightNode(new ThreadedNode(7)); // 中序遍历树 binTree.midShow(); System.out.println("n==============="); // 中序线索化二叉树 binTree.threadNodes(); ThreadedNode afterFive = fiveNode.rightNode; System.out.println(afterFive.value); } }2、ThreadedBinaryTree.java
package demo7; public class ThreadedBinaryTree { ThreadedNode root; // 用于临时存储前驱节点 // 每次调用threadNodes()函数-临时节点都会改变 ThreadedNode pre = null; // 遍历线索二叉树 public void threadIterate() { // 用于临时存储当前遍历节点 ThreadedNode node = root; while (node != null) { // 循环找到最开始的节点 while (node.leftType == 0) { node = node.leftNode; } // 打印当前节点的值 System.out.println(node.value); // 如果当前节点的右指针指向的是后继节点， // 可能后继节点还有后继节点、 while (node.rightType == 1) { node = node.rightNode; System.out.println(node.value); } // 替换遍历的节点 node = node.rightNode; } } // 设置根节点 public void setRoot(ThreadedNode root) { this.root = root; } // 中序线索化二叉树-递归遍历-节点 public void threadNodes() { threadNodes(root); } // 中序线索化二叉树-递归遍历-根据root节点不断递归 public void threadNodes(ThreadedNode node) { // 当前节点如果为null，直接返回 if (node == null) { return; } // 处理左子树---左子树为空,指针指向前驱节点 threadNodes(node.leftNode); // 处理前驱节点 if (node.leftNode == null) { // 让当前节点的左指针指向前驱节点 node.leftNode = pre; // 改变当前节点左指针的类型 node.leftType = 1;// 指向前驱节点 } // 处理前驱的右指针，如果前驱节点的右指针是null(没有指向右子树) if (pre != null && pre.rightNode == null) { // 让前驱节点的右指针指向当前节点 pre.rightNode = node; // 改变前驱节点的右指针类型 pre.rightType = 1; } // 每处理一个节点，当前节点是下一个节点的前驱节点 pre = node; // 处理右子树 threadNodes(node.rightNode); } // 获取根节点 public ThreadedNode getRoot() { return root; } // 前序遍历 public void frontShow() { if (root != null) { root.frontShow(); } } // 中序遍历 public void midShow() { if (root != null) { root.midShow(); } } // 后序遍历 public void afterShow() { if (root != null) { root.afterShow(); } } // 前序查找 public ThreadedNode frontSearch(int i) { return root.frontSearch(i); } // 删除子树 public void delete(int i) { if (root.value == i) { root = null; } else { root.delete(i); } } }3、ThreadedNode.java
package demo7; public class ThreadedNode { int value;// 节点的权 ThreadedNode leftNode;// 左儿子 ThreadedNode rightNode;// 右儿子 // 标识指针类型-默认值为0,指向左右子树 int leftType; int rightType; public ThreadedNode(int value) { this.value = value; } // 设置左儿子 public void setLeftNode(ThreadedNode leftNode) { this.leftNode = leftNode; } // 设置右儿子 public void setRightNode(ThreadedNode rightNode) { this.rightNode = rightNode; } // 前序遍历 public void frontShow() { // 先遍历当前节点的内容 System.out.println(value); // 左节点 if (leftNode != null) { leftNode.frontShow(); } // 右节点 if (rightNode != null) { rightNode.frontShow(); } } // 中序遍历 public void midShow() { // 左子节点 if (leftNode != null) { leftNode.midShow(); } // 当前节点 System.out.print(value + "、"); // 右子节点 if (rightNode != null) { rightNode.midShow(); } } // 后序遍历 public void afterShow() { // 左子节点 if (leftNode != null) { leftNode.afterShow(); } // 右子节点 if (rightNode != null) { rightNode.afterShow(); } // 当前节点 System.out.println(value); } // 前序查找 public ThreadedNode frontSearch(int i) { ThreadedNode target = null; // 对比当前节点的值 if (this.value == i) { return this; // 当前节点的值不是要查找的节点 } else { // 查找左儿子 if (leftNode != null) { // 有可能可以查到，也可以查不到，查不到的话，target还是一个null target = leftNode.frontSearch(i); } // 如果不为空，说明在左儿子中已经找到 if (target != null) { return target; } // 查找右儿子 if (rightNode != null) { target = rightNode.frontSearch(i); } } return target; } // 删除一个子树 public void delete(int i) { ThreadedNode 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); } // 递归检查并删除右儿子 parent = rightNode; if (parent != null) { parent.delete(i); } } }P39-4.12线索二叉树的遍历
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算
官方软件产品操作指南 (170)
2202