二叉树的二叉链表存储及其Java实现

二叉链表存储的思想是让每个节点都记住它的左、右两个子节点,为每个节点增加left、right两个指针,分别引用该节点的左、右两个子节点,如图所示:

二叉树的二叉链表存储及其Java实现

其中,每个节点大致有如下定义:

class Node{
		T data;
		Node left;
		Node right;
	}
 对于这种二叉链表存储的二叉树,如果程序需要,为指定节点添加子节点也非常容易,让父节点的left、right引用指向新节点即可。

 Java实现代码:

package com.liuhao.DataStructures;

public class TwoLinkBinTree<E> {

	public static class TreeNode{

		Object data;
		TreeNode left;
		TreeNode right;
		
		public TreeNode(){}
		
		public TreeNode(Object data){
			this.data = data;
		}
		
		public TreeNode(Object data, TreeNode left, TreeNode right) {
			this.data = data;
			this.left = left;
			this.right = right;
		}
		
	}
	
	private TreeNode root;
	
	//以默认的构造器创建
	public TwoLinkBinTree(){
		this.root = new TreeNode();
	}
	
	//以指定根元素创建
	public TwoLinkBinTree(E data){
		this.root = new TreeNode(data);
	}
	
	/**
	 * 为指定节点添加子节点
	 * @param parent 需要添加节点的父节点的索引
	 * @param data 新添加子节点的数据
	 * @param isLeft 是否是添加左子节点
	 * @return 新增的节点
	 */
	public TreeNode addNode(TreeNode parent, E data, boolean isLeft){
		if(parent == null){
			throw new RuntimeException(parent + "节点为空,不能添加子节点!");
		}
		
		if(isLeft && parent.left != null){
			throw new RuntimeException(parent + "节点已有左子节点,不能添加左子节点!");
		}
		
		if(!isLeft && parent.right != null){
			throw new RuntimeException(parent + "节点已有右子节点,不能添加右子节点!");
		}
		
		TreeNode newNode = new TreeNode(data);
		if(isLeft){
			parent.left = newNode;
		}else{
			parent.right = newNode;
		}
		
		return newNode;
	}
	
	//判断二叉树是否为空
	public boolean isEmpty(){
		return root.data == null;
	}
	
	//获取根节点
	public TreeNode getRoot(){
		if(isEmpty()){
			throw new RuntimeException("树为空,无法获取根节点!");
		}
		return root;
	}
	
	//获取指定节点的左子节点
	public TreeNode getLeft(TreeNode parent){
		if(parent == null){
			throw new RuntimeException(parent + "节点为空,不能获取子节点!");
		}
		
		return parent.left == null ? null : parent.left;
	}
	
	//获取指定节点的右子节点
	public TreeNode getRight(TreeNode parent){
		if(parent == null){
			throw new RuntimeException(parent + "节点为空,不能获取子节点!");
		}
		
		return parent.right == null ? null : parent.right;
	}
	
	//获取指定节点的深度
	private int getDeep(TreeNode node){
		if(node == null){
			return 0;
		}
		
		if(node.left == null && node.right == null){
			return 1;
		}else{
			int leftDeep = getDeep(node.left);
			int rightDeep = getDeep(node.right);
			
			int max = leftDeep > rightDeep ? leftDeep : rightDeep;
			return max + 1;
		}
	}
	
	public int getTreeDeep(){
		return this.getDeep(root);
	}
	
}
测试代码:
package com.liuhao.DataStructures;

import org.junit.Test;

public class TwoLinkBinTreeTest {

	@Test
	public void test() {
		TwoLinkBinTree<String> binTree = new TwoLinkBinTree<String>("根");
		
		TwoLinkBinTree.TreeNode node1 = binTree.addNode(binTree.getRoot(), "根左", true);
		TwoLinkBinTree.TreeNode node2 = binTree.addNode(binTree.getRoot(), "根右", false);
		TwoLinkBinTree.TreeNode node3 = binTree.addNode(node2, "根右左", true);
		TwoLinkBinTree.TreeNode node4 = binTree.addNode(node2, "根右右", false);
		TwoLinkBinTree.TreeNode node5 = binTree.addNode(node4, "根右右左", true);
		TwoLinkBinTree.TreeNode node6 = binTree.addNode(node3, "根右左右", false);
		TwoLinkBinTree.TreeNode node7 = binTree.addNode(node6, "根右左右右", false);
		
		System.out.println("node2的左子节点:" + binTree.getLeft(node2).data);
		System.out.println("node2的右子节点:" + binTree.getRight(node2).data);
		
		System.out.println("树的深度:" + binTree.getTreeDeep());
		
	}

}
对于这种二叉链表的二叉树,因为采用链表来记录树中所有节点,所以添加节点没有限制,而且不会希像顺序存储那样产生大量的空间浪费。当然,这种二叉链表的存储方式在遍历树节点时效率不高,指定节点访问其父节点时也是如此,程序必须采用遍历二叉树的方式来搜寻其父节点。

二叉树的二叉链表存储及其Java实现,布布扣,bubuko.com

二叉树的二叉链表存储及其Java实现

上一篇:JavaFX战旗类游戏开发 第二课 游戏地图绘制


下一篇:用Spring提高java观察者模式灵活性