首页 > 代码库 > java二叉树实现代码
java二叉树实现代码
public class Tree { private TreeNode root = null; public Tree() { root = new TreeNode(1, "A"); } private class TreeNode { private int key; private String data; private boolean isVisted; private TreeNode leftChild; private TreeNode rightChild; public TreeNode(int key, String data) { this.key = key; this.data =http://www.mamicode.com/ data; this.leftChild = null; this.rightChild = null; this.isVisted = false; } } /** * 创建一颗二叉树 * A * B C * D E F * createBinTree:(). * @author 卫健 * @param root */ public void createBinTree(TreeNode root) { TreeNode newNodeB = new TreeNode(2, "B"); TreeNode newNodeC = new TreeNode(3, "C"); TreeNode newNodeD = new TreeNode(4, "D"); TreeNode newNodeE = new TreeNode(5, "E"); TreeNode newNodeF = new TreeNode(6, "F"); root.leftChild = newNodeB; root.rightChild = newNodeC; // newNodeC.rightChild = newNodeF; // newNodeB.leftChild = newNodeD; // newNodeB.rightChild = newNodeE; root.rightChild.rightChild = newNodeF; root.leftChild.leftChild = newNodeD; root.leftChild.rightChild = newNodeE; } public boolean isEmpty() { return root == null; } //树的高度 public int height() { return height(root); } //节点个数 public int size() { return size(root); } private int height(TreeNode subTree) { if (subTree == null) return 0; int i = height(subTree.leftChild); int j = height(subTree.rightChild); return i < j ? j + 1 : i + 1; } private int size(TreeNode subTree) { if (subTree == null) return 0; return 1 + size(subTree.leftChild) + size(subTree.rightChild); } //返回双亲节点 public TreeNode parent(TreeNode element) { return (root == null || root == element) ? null : parent(root, element); } public TreeNode parent(TreeNode subTree, TreeNode element) { if (subTree == null) return null; if (subTree.leftChild == element || subTree.rightChild == element) { //返回父节点地址 return subTree; } TreeNode p; //先在左子树中查找,如果左子树中没有找到,则到右子树中查找 if ((p = parent(subTree.leftChild, element)) != null) return p; //递归左子树中搜索 else return parent(subTree.rightChild, element); } public TreeNode getLeftChildNode(TreeNode element) { return element != null ? element.leftChild : null; } public TreeNode getRightChildNode(TreeNode element) { return element != null ? element.rightChild : null; } public TreeNode getRoot() { return root; } //在释放某个节点时,该节点的左右子树都已经释放, //所以应该采用后续遍历,当访问某个节点时将该节点的存储空间释放 public void distroy(TreeNode subTree) { //删除根为subTree的子树 if (subTree != null) { //删除左子树 distroy(subTree.leftChild); //删除右子树 distroy(subTree.rightChild); //删除根节点 subTree = null; } } public void traverse(TreeNode subTree) { System.out.println("key:" + subTree.key + "--name:" + subTree.data); traverse(subTree.leftChild); traverse(subTree.rightChild); } //前序遍历 public void perOrder(TreeNode subTree) { if (subTree != null) { visted(subTree); perOrder(subTree.leftChild); perOrder(subTree.rightChild); } } //中序遍历 public void inOrder(TreeNode subTree) { if (subTree != null) { perOrder(subTree.leftChild); visted(subTree); perOrder(subTree.rightChild); } } //后序遍历 public void postOrder(TreeNode subTree) { if (subTree != null) { perOrder(subTree.leftChild); perOrder(subTree.rightChild); visted(subTree); } } //将二叉树镜面对称 public void mirror(TreeNode subTree) { if (subTree == null) return; TreeNode node = new TreeNode(subTree.key, subTree.data); node.leftChild = subTree.leftChild; subTree.leftChild = subTree.rightChild; subTree.rightChild = node.leftChild; mirror(subTree.leftChild); mirror(subTree.rightChild); } public void visted(TreeNode subTree) { subTree.isVisted = true; System.out.println("key:" + subTree.key + "---data:" + subTree.data); } //测试 public static void main(String[] args) { Tree bt = new Tree(); bt.createBinTree(bt.root); System.out.println(bt.size() + "---size"); System.out.println(bt.height() + "---height"); System.out.println("**************前序遍历************"); bt.perOrder(bt.root); System.out.println("************镜面对称**前序遍历************"); bt.mirror(bt.root); bt.perOrder(bt.root); // System.out.println("**************中序遍历************"); // bt.inOrder(bt.root); // // System.out.println("**************后序遍历************"); // bt.postOrder(bt.root); } }
java二叉树实现代码
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。