Java基础复习重点笔记数据结构二叉树和二叉树的遍历.doc

Java基本复习笔记08数据构造-二叉树和二叉树遍历刘岩Email:1. 二叉树普通树限制比较少，因此才提出了具备特色二叉树概念。二叉树顾名思义，每个节点最多有两个子节点，分别叫做左子节点和右子节点。有了这个限定性后，就可以干诸多树不能干事情了。如果树所有层，除了最后一层节点外都是两个子节点，那么称这个树为满二叉树。如下图若设二叉树高度为h，除第 h 层外，其他各层 (1h-1) 结点数都达到最大个数，第 h 层所有节点都持续集中在最左边，这就是完全二叉树。2. 二叉树操作二叉树具备为指定节点增长子节点操作、判断树与否为空、返回根节点、返回指定节点父节点，返回指定节点左子节点、返回指定节点右子节点、返回树深度、返回指定节点位置。3. 二叉树延伸其实二叉树只是一种引子，计算机界诸多算法都是依照二叉树所展开，例如排序二叉树、红黑树、哈夫曼树、线索二叉树等等。4. 顺序实现二叉树下面咱们来看看二叉树顺序实现方式，顺序实现二叉树就是运用数组存储所有二叉树节点。代码如下package dateStructer.tree.binaryTree;/* * 顺序二叉树 * * author liuyan */public class ArrayBinaryTree / 树默认深度private static final int DefTreeDeep = 4;/ 节点数组private Object datas;/ 指定树深度private int treeDeep;/ 实际数组个数private int arraySize;/* * 默认构造函数 */public ArrayBinaryTree() / 设立默认树深度treeDeep = DefTreeDeep;/ 2DefTreeDeep次方-1个数组元素arraySize = (int) Math.pow(2，DefTreeDeep) - 1;datas = new ObjectarraySize;/* * 指定深度构建二叉树 * param deep */public ArrayBinaryTree(int deep) / 按指定深度treeDeep = deep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new ObjectarraySize;/* * 指定深度和指定根节点构建二叉树 * param deep * param data */public ArrayBinaryTree(int deep，T data) / 按指定深度treeDeep = deep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new ObjectarraySize;datas0 = data;/* * 为指定节点索引增长子节点 * param index * param data * param isLeft * return */public boolean addNode(int index，T data，boolean isLeft) if (index * 2 + 2 arraySize | datasindex = null) throw new RuntimeException(标记无效);if (isLeft) datasindex * 2 + 1 = data; else datasindex * 2 + 2 = data;return true;/* * 判断二叉树与否为空 * * return */public boolean isEmpty() return arraySize = 0;/* * 返回根节点 * * return */SuppressWarnings(unchecked)public T getRoot() return (T) datas0;/* * 返回指定节点父节点 * return */SuppressWarnings(unchecked)public T getParent(int index) if (index arraySize | datasindex = null) throw new RuntimeException(标记无效);if (datas(index - 1) / 2 = null) throw new RuntimeException(无父节点);return (T) datas(index - 1) / 2;/* * 返回左子节点 * return */SuppressWarnings(unchecked)public T getLeftNode(int index) if (index * 2 + 2 arraySize | datasindex = null) throw new RuntimeException(标记无效);return (T) datasindex * 2 + 1;/* * 返回右子节点 * return */SuppressWarnings(unchecked)public T getRightNode(int index) if (index * 2 + 2 arraySize | datasindex = null) throw new RuntimeException(标记无效);return (T) datasindex * 2 + 2;/* * 返回树深度 * return */public int getTreeDeep() return treeDeep;/* * 返回指定节点索引位置 * param data * return */public int getNodeIndex(T data) for (int i = 0；i arraySize；i+) if (data = datasi) return i;return -1;Overridepublic String toString() StringBuffer str = new StringBuffer();for (int i = 0；i 0) return str.substring(0，str.lastIndexOf(,) + ;return str.append().toString();测试代码如下public static void main(String args) ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(4,汉献帝);System.out.println(arrayBinaryTree);arrayBinaryTree.addNode(0，刘备，true);arrayBinaryTree.addNode(0，曹操，false);arrayBinaryTree.addNode(1，关羽，true);arrayBinaryTree.addNode(1，张飞，false);arrayBinaryTree.addNode(2，张辽，true);arrayBinaryTree.addNode(2，许褚，false);System.out.println(arrayBinaryTree);System.out.println(arrayBinaryTree.getLeftNode(1);System.out.println(arrayBinaryTree.getRightNode(0);System.out.println(arrayBinaryTree.isEmpty();System.out.println(arrayBinaryTree.getParent(4);测试效果如下顺序实现是比较挥霍资源，可以看到数组没有元素位置都是null。如果将测试代码稍微变更一下，如下public static void main(String args) ArrayBinaryTree arrayBinaryTree = new ArrayBinaryTree(4,汉献帝);System.out.println(arrayBinaryTree);arrayBinaryTree.addNode(0，刘备，true);arrayBinaryTree.addNode(0，曹操，false);arrayBinaryTree.addNode(2，张辽，true);arrayBinaryTree.addNode(2，许褚，false);arrayBinaryTree.addNode(6，李典，true);arrayBinaryTree.addNode(6，乐进，false);System.out.println(arrayBinaryTree);System.out.println(arrayBinaryTree.getLeftNode(2);System.out.println(arrayBinaryTree.getRightNode(0);System.out.println(arrayBinaryTree.isEmpty();System.out.println(arrayBinaryTree.getParent(14);运营效果如下可以看到数组中间资源挥霍得很严重。5. 二叉链表实现二叉树为了弥补顺序实现空间挥霍问题，可以使用链表方式实现二叉树，但是链表又分为两种状况，一种是二叉链表，另一种稍后再说。二叉链表思想就是构造一种对象，记住它两个子节点，所谓记住两个子节点可以是子节点位置，可以是子节点实体对象。如果记录了位置，其实是离不开数组协助。如果记录了整个子节点对象，那么就可以完全脱离数组，完完全全，真真正正链表离散式存储。这次使用记录节点位置，算法如下package dateStructer.tree.binaryTree;/* * 二叉链表二叉树 * * author liuyan */public class TwoLinkedBinaryTree / 树默认深度private static final int DefTreeDeep = 4;/ 节点数组private TwoLinkNode datas;/ 指定树深度private int treeDeep;/ 实际数组个数private int arraySize;/节点个数private int nodeSize;/* * 二叉节点 */SuppressWarnings(hiding)class TwoLinkNode public int leftChildIndex;public int rightChildIndex;public int index;public T data;SuppressWarnings(unchecked)public TwoLinkedBinaryTree() treeDeep = DefTreeDeep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new TwoLinkNodearraySize;SuppressWarnings(unchecked)public TwoLinkedBinaryTree(int deep，T data) treeDeep = DefTreeDeep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new TwoLinkNodearraySize;TwoLinkNode twoLinkNode = new TwoLinkNode();twoLinkNode.data = data;twoLinkNode.leftChildIndex = 1;twoLinkNode.rightChildIndex = 2;twoLinkNode.index = 0;datas0 = twoLinkNode;nodeSize = 1;/* * 为指定节点索引增长子节点 * * param index * param data * param isLeft * return */public boolean addNode(int index，T data，boolean isLeft) if (index + 1 arraySize | datasindex = null) throw new RuntimeException(标记无效);for (int i = index + 1；i arraySize；i+) if (datasi = null) TwoLinkNode twoLinkNode = new TwoLinkNode();twoLinkNode.data = data;twoLinkNode.index = i;datasi = twoLinkNode;if (isLeft) datasindex.leftChildIndex = i; else datasindex.rightChildIndex = i;nodeSize +;return true;return false;/* * 判断二叉树与否为空 * * return */public boolean isEmpty() return nodeSize = 0;/* * 返回根节点 * * return */SuppressWarnings(unchecked)public T getRoot() return (T) datas0;/* * 返回指定节点父节点 * * return */public T getParent(int index) if (index arraySize | datasindex = null) throw new RuntimeException(标记无效);for (int i = 0；i arraySize | datasindex = null) throw new RuntimeException(标记无效);return (T) datasdatasindex.leftChildIndex.data;/* * 返回右子节点 * * return */public T getRightNode(int index) if (index + 2 arraySize | datasindex = null) throw new RuntimeException(标记无效);return (T) datasdatasindex.rightChildIndex.data;/* * 返回树深度 * * return */public int getTreeDeep() return treeDeep;/* * 返回指定节点索引位置 * * param data * return */public int getNodeIndex(T data) for (int i = 0；i arraySize；i+) if (data = datasi) return i;return -1;Overridepublic String toString() StringBuffer str = new StringBuffer();for (int i = 0；i 0) return str.substring(0，str.lastIndexOf(,) + ;return str.append().toString();使用这种实现其实是想运用好数组空间。别让中间任何节点空间白白挥霍了。但是可以发现找父节点时候比较麻烦。还得遍历一下整个节点。三叉链表就不必遍历，由于三叉链表比二叉链表多了记录了一种节点，那就是此节点父节点。无论是父节点位置或者父节点实体，都是同样思想。6. 三叉链表实现二叉树下面咱们基于上面二叉链表形式编写三叉链表。代码如下package dateStructer.tree.binaryTree;/* * 三叉链表实现 * * author liuyan */public class ThreeLinkedBinaryTree / 树默认深度private static final int DefTreeDeep = 4;/ 节点数组private ThreeLinkNode datas;/ 指定树深度private int treeDeep;/ 实际数组个数private int arraySize;/ 节点个数private int nodeSize;/* * 三叉节点 */SuppressWarnings(hiding)class ThreeLinkNode public int parentIndex;public int leftChildIndex;public int rightChildIndex;public int index;public T data;SuppressWarnings(unchecked)public ThreeLinkedBinaryTree() treeDeep = DefTreeDeep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new ThreeLinkNodearraySize;SuppressWarnings(unchecked)public ThreeLinkedBinaryTree(int deep，T data) treeDeep = DefTreeDeep;arraySize = (int) Math.pow(2，treeDeep) - 1;datas = new ThreeLinkNodearraySize;ThreeLinkNode threeLinkNode = new ThreeLinkNode();threeLinkNode.data = data;threeLinkNode.leftChildIndex = 1;threeLinkNode.rightChildIndex = 2;threeLinkNode.index = 0;threeLinkNode.parentIndex = -1;datas0 = threeLinkNode;nodeSize = 1;/* * 为指定节点索引增长子节点 * * param index * param data * param isLeft * return */public boolean addNode(int index，T data，boolean isLeft) if (index + 1 arraySize | datasindex = null) throw new RuntimeException(标记无效);for (int i = index + 1；i arraySize；i+) if (datasi = null) ThreeLinkNode threeLinkNode = new ThreeLinkNode();threeLinkNode.data = data;threeLinkNode.index = i;threeLinkNode.parentIndex = index;datasi = threeLinkNode;if (isLeft) datasindex.leftChildIndex = i; else datasindex.rightChildIndex = i;nodeSize+;return true;return false;/* * 判断二叉树与否为空 * * return */public boolean isEmpty() return nodeSize = 0;/* * 返回根节点 * * return */SuppressWarnings(unchecked)public T getRoot() return (T) datas0;/* * 返回指定节点父节点 * * return */SuppressWarnings(unchecked)public T getParent(int index) if (index arraySize | datasindex = null) throw new RuntimeException(标记无效);return (T) datasdatasindex.parentIndex;/* * 返回左子节点 * * return */public T getLeftNode(int index) if (index + 2 arraySize | datasindex = null| datasdatasindex.leftChildIndex = null) throw new RuntimeException(标记无效);return (T) datasdatasindex.leftChildIndex.data;/* * 返回右子节点 * * return */public T getRightNode(int index) if (index + 2 arraySize | datasindex = null| datasdatasindex.rightChildIndex = null) throw new RuntimeException(标记无效);return (T) datasdatasindex.rightChildIndex.data;/* * 返回树深度 * * return */public int getTreeDeep() return treeDeep;/* * 返回指定节点索引位置 * * param data * return */public int getNodeIndex(T data) for (int i = 0；i arraySize；i+) if (data = datasi) return i;return -1;Overridepublic String toString() StringBuffer str = new StringBuffer();for (int i = 0；i 0) return str.substring(0，str.lastIndexOf(,) + ;return str.append().toString();可以看到基本上办法实现都同样，就是找寻父节点时候更省事了。由于节点对象多存了父节点信息，固然就省事了。7. 二叉树遍历遍历二叉树事实上就是将一种非线性二维构造给排列呈线性过程。如果是顺序实现了二叉树构造，自然底层就是线性，无需转化。如果是纯链表实现呢，就需要将离散节点重新组织组织了。遍历也分为深度优先遍历、广度优先遍历。而对于深度优先遍历又分为三种模式：先根遍历、中根遍历、后根遍历。深度优先遍历：就是优先访问树中最深层次节点广度优先遍历：就是从根往下一层一层遍历访问先根遍历：先遍历根节点，之后解决其她子节点中根遍历：先遍历根节点左子树，之后遍历根节点，最后遍历右子树后根遍历：先遍历根节点左子树，之后遍历右子树，最后遍历根节点由于树自身就是具备递归性质构造。先根遍历算法如下public ListTwoLinkNode firstRoot(TwoLinkNode twoLinkNode) if (twoLinkNode = null) return null;ListTwoLinkNode list = new ArrayListTwoLinkNode();list.add(twoLinkNode);if (twoLinkNode.leftChildIndex 0) list.addAll(firstRoot(datastwoLinkNode.leftChildIndex);if (twoLinkNode.rightChildIndex 0) list.addAll(firstRoot(datastwoLinkNode.rightChildIndex);return list;中根遍历算法如下/* * 中根遍历 * * param twoLinkNode * return */public ListTwoLinkNode minRoot(TwoLinkNode twoLinkNode) if (twoLinkNode = null) return null;ListTwoLinkNode list = new ArrayListTwoLinkNode();if (twoLinkNode.leftChildIndex 0) list.addAll(minRoot(datastwoLinkNode.leftChildIndex);list.add(twoLinkNode);if (twoLinkNode.rightChildIndex 0) list.addAll(minRoot(datastwoLinkNode.rightChildIndex);return list;后根遍历/* * 后根遍历 * * param twoLinkNode * return */public ListTwoLinkNode afterRoot(TwoLinkNode twoLinkNode) if (twoLinkNode = null) return null;ListTwoLinkNode list = new ArrayListTwoLinkNode();if (twoLinkNode.leftChildIndex 0) list.addAll(afterRoot(datastwoLinkNode.leftChildIndex);if (twoLinkNode.rightChildIndex 0) list.addAll(afterRoot(datastwoLinkNode.rightChildIndex);list.add(twoLinkNode);return list;广度优先遍历/* * 后根遍历 * * param twoLinkNode * return */public ListTwoLinkNode deepFirst() ListTwoLinkNode list = new ArrayListTwoLinkNode();QueueTwoLinkNode queue = new ArrayDequeTwoLinkNode();queue.add(datas0);while (!queue.isEmpty() list.add(queue.peek();TwoLinkNode twoLinkNode = queue.poll();if (twoLinkNode.leftChildIndex 0) queue.add(datastwoLinkNode.leftChildIndex);if (twoLinkNode.rightChildIndex 0) queue.add(datast