赞
踩
下面聊聊二叉树的使用,二叉树的基本理论想必大家都很明白了,直接上代码,
1、首先是一个节点Node,这个节点有下面几个属性,数据项,以及对左右子节点的引用,
public class Node { // 数据项 public long data; private String sData; // 左子节点 public Node leftChild; // 右子节点 public Node rightChild; /** * 构造方法 * * @param data */ public Node(long data,String sData) { this.data = data; this.sData = sData; } }
2、操作二叉树的类,
public class Tree { // 定义根节点 public Node root; /** * 插入节点 * * @param value */ public void insert(long value,String sValue) { // 封装节点 Node newNode = new Node(value,sValue); // 引用当前节点 Node current = root; // 引用父节点 Node parent; // 如果root为null,也就是第一插入的时候 if (root == null) { root = newNode; return; } else { while (true) { // 父节点指向当前节点 parent = current; // 如果当前指向的节点数据比插入的要大,则向左走 if (current.data > value) { current = current.leftChild; if (current == null) { parent.leftChild = newNode; return; } } else { current = current.rightChild; if (current == null) { parent.rightChild = newNode; return; } } } } } /** * 查找一个节点 * @param value * @return */ public Node find(long value) { Node current = root; while(value != current.data){ if(value > current.data){ current = current.rightChild; }else{ current = current.leftChild; } if(current == null){ return null; } } return current; } /** * 前序遍历,从根节点开始,每次遍历都从左子树开始一直到最后 * @param currNode */ public void frontOrder(Node currNode){ if(currNode != null){ System.out.println(currNode.data + " ," + currNode.sData); frontOrder(currNode.leftChild); frontOrder(currNode.rightChild); } } /** * 中序遍历 顺序:左子树 ---》 根节点 ---》右子树 * @param currNode */ public void centOrder(Node currNode){ if(currNode != null){ frontOrder(currNode.leftChild); System.out.println(currNode.data + " ," + currNode.sData); frontOrder(currNode.rightChild); } } /** * 后序遍历 顺序:左子树 ---》 右子树 ---》根节点 * @param currNode */ public void afterOrder(Node currNode){ if(currNode != null){ frontOrder(currNode.leftChild); frontOrder(currNode.rightChild); System.out.println(currNode.data + " ," + currNode.sData); } } }
测试类:
public class TestTree { public static void main(String[] args) { Tree tree = new Tree(); tree.insert(10,"james"); tree.insert(20,"kobe"); tree.insert(15,"maikeer"); tree.insert(3,"maidi"); /*System.out.println(tree.root.data); System.out.println(tree.root.leftChild.data); System.out.println(tree.root.rightChild.data);*/ System.out.println("================="); Node node = tree.find(3); System.out.println(node.data); } } /** * 删除一个节点,分为4种情况 * 1、删除的节点为叶子节点 * 2、删除的节点只有左子节点 * 3、删除的节点只有右子节点 * 4、删除的节点左右节点都存在, ----》》需要通过中序后继查找可替换的那个值 * @param value * @return */ public boolean delete(long value) { //引用当前节点,从根节点开始 Node current = root; //当前节点的父节点 Node parent = root; boolean isLeftChild = true; while(current.data != value){ parent = current; if(current.data > value){ //从当前节点的左子节点开始找 current = current.leftChild; isLeftChild = true; }else{ current = current.rightChild; isLeftChild = false; } //如果都没有找到 if(current == null){ return false; } } //执行删除操作,当前没有叶子节点的情况下的删除 if(current.leftChild == null && current.rightChild == null){ if(current == root){ root = null; }else if(isLeftChild){ //如果是左子节点 parent.leftChild = null; }else{ parent.rightChild = null; } } //如果要删除的节点的左子树节点存在 else if(current.leftChild != null && current.rightChild == null ){ if(current == root){ root = current.leftChild; }else if(isLeftChild){ parent.leftChild = current.leftChild; }else{ parent.rightChild = current.leftChild; } } //如果要删除的节点的右子树节点存在 else if(current.leftChild == null && current.rightChild != null){ if(current == root){ root = current.rightChild; }else if(isLeftChild){ parent.leftChild = current.rightChild; }else{ parent.rightChild = current.rightChild; } //如果要删除的节点的左右节点都存在 }else{ Node succesor = deleteNode(current); if(current == root){ root = succesor; }else if(isLeftChild){ parent.leftChild = succesor; }else{ parent.rightChild = succesor; } succesor.leftChild = current.leftChild; } return true; } //通过中序遍历获取可以替换的节点 public Node deleteNode(Node deleteNode){ Node succesor = deleteNode; Node succesorParent = deleteNode; Node current = deleteNode.rightChild; while(current != null){ succesorParent = succesor; succesor = current; current = current.leftChild; } if(succesor != deleteNode.rightChild){ succesorParent.leftChild = succesor.rightChild; succesor.rightChild = deleteNode.rightChild; } return succesor; }
未完待续…
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。