【code】java二叉树的实现

二叉树的顺序存储

public class ArrayBinTree<T>
{
	//使用数组来记录该树的所有节点
	private Object[] datas;
	private int DEFAULT_DEEP = 8;
	//保存该树的深度
	private int deep;
	private int arraySize;
	//以默认的深度来创建二叉树
	public ArrayBinTree()
	{
		this.deep = DEFAULT_DEEP;
		this.arraySize = (int)Math.pow(2 , deep) - 1;
		datas = new Object[arraySize];
	}
	//以指定深度来创建二叉树
	public ArrayBinTree(int deep)
	{
		this.deep = deep;
		this.arraySize = (int)Math.pow(2 , deep) - 1;
		datas = new Object[arraySize];
	}
	//以指定深度,指定根节点创建二叉树
	public ArrayBinTree(int deep , T data)
	{
		this.deep = deep;
		this.arraySize = (int)Math.pow(2 , deep) - 1;
		datas = new Object[arraySize];
		datas[0] = data;
	}
	/**
	 * 为指定节点添加子节点。
	 * @param index 需要添加子节点的父节点的索引
	 * @param data 新子节点的数据
	 * @param left 是否为左节点
	 */
	public void add(int index , T data , boolean left)
	{
		if (datas[index] == null)
		{
			throw new RuntimeException(index + "处节点为空，无法添加子节点");
		}
		if (2 * index + 1 >= arraySize)
		{
			throw new RuntimeException("树底层的数组已满，树越界异常");
		}
		//添加左子节点
		if (left)
		{
			datas[2 * index + 1] = data;
		}
		else
		{
			datas[2 * index + 2] = data;
		}
	}
	//判断二叉树是否为空。
	public boolean empty()
	{
		//根据根元素来判断二叉树是否为空
		return datas[0] == null;
	}
	//返回根节点。
	public T root()
	{
		return (T)datas[0] ;
	}
	//返回指定节点（非根节点）的父节点。
	public T parent(int index)
	{
		return (T)datas[(index - 1) / 2] ;
	}
	//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回null
	public T left(int index)
	{
		if (2 * index + 1 >= arraySize)
		{
			throw new RuntimeException("该节点为叶子节点，无子节点");
		}
		return (T)datas[index * 2 + 1] ;
	}
	//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回null
	public T right(int index)
	{
		if (2 * index + 1 >= arraySize)
		{
			throw new RuntimeException("该节点为叶子节点，无子节点");
		}
		return (T)datas[index * 2 + 2] ;
	}
	//返回该二叉树的深度。
	public int deep(int index)
	{
		return deep;
	}
	//返回指定节点的位置。
	public int pos(T data)
	{
		//该循环实际上就是按广度遍历来搜索每个节点
		for (int i = 0 ; i < arraySize ; i++)
		{
			if (datas[i].equals(data))
			{
				return i;
			}
		}
		return -1;
	}
	public String toString()
	{
		return java.util.Arrays.toString(datas);
	}
	
	public static void main(String[] args) 
	{
		ArrayBinTree<String> binTree = 
			new ArrayBinTree<String>(4, "根");
		binTree.add(0 , "第二层右子节点" , false);//是从0位置开始
		binTree.add(2 , "第三层右子节点" , false);
		binTree.add(6 , "第四层右子节点" , false);
		System.out.println(binTree);
	}
}

 

二叉树的链表存储

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 index 需要添加子节点的父节点的索引
	 * @param data 新子节点的数据
	 * @param isLeft 是否为左节点
	 * @return 新增的节点
	 */
	public TreeNode addNode(TreeNode parent , E data
		, boolean isLeft)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		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)
		{
			//让父节点的left引用指向新节点
			parent.left = newNode;
		}
		else
		{
			//让父节点的left引用指向新节点
			parent.right = newNode;
		}
		return newNode;
	}
	//判断二叉树是否为空。
	public boolean empty()
	{
		//根据根元素来判断二叉树是否为空
		return root.data == null;
	}
	//返回根节点。
	public TreeNode root()
	{
		if (empty())
		{
			throw new RuntimeException("树为空，无法访问根节点");
		}
		return root;
	}
	//返回指定节点（非根节点）的父节点。
	public E parent(TreeNode node)
	{
		//对于二叉链表存储法，如果要访问指定节点的父节点必须遍历二叉树
		return null;
	}
	//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回null
	public E leftChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		return parent.left == null ? null : (E)parent.left.data;
	}
	//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回null
	public E rightChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		return parent.right == null ? null : (E)parent.right.data;
	}
	//返回该二叉树的深度。
	public int deep()
	{
		//获取该树的深度
		return deep(root); 
	}
	//这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
	private int deep(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		//没有子树
		if (node.left == null
			&& node.right == null)
		{
			return 1;
		}
		else
		{
			int leftDeep = deep(node.left);
			int rightDeep = deep(node.right);
			//记录其所有左、右子树中较大的深度
			int max = leftDeep > rightDeep ? 
				leftDeep : rightDeep;
			//返回其左右子树中较大的深度 + 1
			return max + 1;
		}
	}
	
	public static void main(String[] args) 
    {
        TwoLinkBinTree<String> binTree = new TwoLinkBinTree("根节点");
		//依次添加节点
		TwoLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root()
			,  "第二层左节点" , true);
		TwoLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root()
			, "第二层右节点" ,false );
		TwoLinkBinTree.TreeNode tn3 = binTree.addNode(tn2 
			, "第三层左节点" , true);
		TwoLinkBinTree.TreeNode tn4 = binTree.addNode(tn2
			, "第三层右节点" , false);
		TwoLinkBinTree.TreeNode tn5 = binTree.addNode(tn3
			, "第四层左节点" , true);
		System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));
		System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));
		System.out.println(binTree.deep());
    }
}

 

二叉树的三叉链表存储

public class ThreeLinkBinTree<E>
{
	public static class TreeNode
	{
		Object data;
		TreeNode left;
		TreeNode right;
		TreeNode parent;
		public TreeNode()
		{
		}
		public TreeNode(Object data)
		{
			this.data = data;
		}
		public TreeNode(Object data , TreeNode left
			, TreeNode right , TreeNode parent)
		{
			this.data = data;
			this.left = left;
			this.right = right;
			this.parent = parent;
		}
	}
	private TreeNode root;
	//以默认的构造器来创建二叉树
	public ThreeLinkBinTree()
	{
		this.root = new TreeNode();
	}
	//以指定根元素来创建二叉树
	public ThreeLinkBinTree(E data)
	{
		this.root = new TreeNode(data);
	}
	/**
	 * 为指定节点添加子节点。
	 * @param index 需要添加子节点的父节点的索引
	 * @param data 新子节点的数据
	 * @param isLeft 是否为左节点
	 * @return 新增的节点
	 */
	public TreeNode addNode(TreeNode parent , E data
		, boolean isLeft)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		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)
		{
			//让父节点的left引用指向新节点
			parent.left = newNode;
		}
		else
		{
			//让父节点的left引用指向新节点
			parent.right = newNode;
		}
		//让新节点的parent引用到parent节点
		newNode.parent = parent;
		return newNode;
	}
	//判断二叉树是否为空。
	public boolean empty()
	{
		//根据根元素来判断二叉树是否为空
		return root.data == null;
	}
	//返回根节点。
	public TreeNode root()
	{
		if (empty())
		{
			throw new RuntimeException("树为空，无法访问根节点");
		}
		return root;
	}
	//返回指定节点（非根节点）的父节点。
	public E parent(TreeNode node)
	{
		if (node == null)
		{
			throw new RuntimeException(node +
				"节点为null，无法访问其父节点");
		}
		return (E)node.parent.data;
	}
	//返回指定节点（非叶子）的左子节点。当左子节点不存在时返回null
	public E leftChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		return parent.left == null ? null : (E)parent.left.data;
	}
	//返回指定节点（非叶子）的右子节点。当右子节点不存在时返回null
	public E rightChild(TreeNode parent)
	{
		if (parent == null)
		{
			throw new RuntimeException(parent +
				"节点为null，无法添加子节点");
		}
		return parent.right == null ? null : (E)parent.right.data;
	}
	//返回该二叉树的深度。
	public int deep()
	{
		//获取该树的深度
		return deep(root); 
	}
	//这是一个递归方法：每棵子树的深度为其所有子树的最大深度 + 1
	private int deep(TreeNode node)
	{
		if (node == null)
		{
			return 0;
		}
		//没有子树
		if (node.left == null
			&& node.right == null)
		{
			return 1;
		}
		else
		{
			int leftDeep = deep(node.left);
			int rightDeep = deep(node.right);
			//记录其所有左、右子树中较大的深度
			int max = leftDeep > rightDeep ? 
				leftDeep : rightDeep;
			//返回其左右子树中较大的深度 + 1
			return max + 1;
		}
	}
	
	public static void main(String[] args) 
    {
        ThreeLinkBinTree<String> binTree = new ThreeLinkBinTree("根节点");
		//依次添加节点
		ThreeLinkBinTree.TreeNode tn1 = binTree.addNode(binTree.root()
			,  "第二层左节点" , true);
		ThreeLinkBinTree.TreeNode tn2 = binTree.addNode(binTree.root()
			, "第二层右节点" ,false );
		ThreeLinkBinTree.TreeNode tn3 = binTree.addNode(tn2 
			, "第三层左节点" , true);
		ThreeLinkBinTree.TreeNode tn4 = binTree.addNode(tn2
			, "第三层右节点" , false);
		ThreeLinkBinTree.TreeNode tn5 = binTree.addNode(tn3
			, "第四层左节点" , true);
		System.out.println("tn2的父节点：" + binTree.parent(tn2));
		System.out.println("tn2的左子节点：" + binTree.leftChild(tn2));
		System.out.println("tn2的右子节点：" + binTree.rightChild(tn2));
		System.out.println(binTree.deep());
    }
}