当前位置:   article > 正文

java操作二叉树_java二叉树操作

java二叉树操作

下面聊聊二叉树的使用,二叉树的基本理论想必大家都很明白了,直接上代码,

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;
	}

}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

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);
		}
	}
	
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101

测试类:

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;
	}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118

未完待续…

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/747821
推荐阅读
相关标签
  

闽ICP备14008679号