本文主要是介绍java用三叉链表构建二叉树,二叉树的三叉链表存储及其Java实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
三叉链表存储的思想是让每个节点持有三个引用parent、left、right，分别指向其父节点、左子节点和右子节点。如下图所示：
因此，三叉链表存储的节点大致如：
class Node{
T data;
Node parent;
Node left;
Node right;
}Java实现代码：
package com.liuhao.DataStructures;
import com.liuhao.DataStructures.TwoLinkBinTree.TreeNode;
public class ThreeLinkBinTree {
public static class TreeNode{
Object data;
TreeNode parent;
TreeNode left;
TreeNode right;
public TreeNode() {
}
public TreeNode(Object data) {
this.data = data;
}
public TreeNode(Object data, TreeNode parent, TreeNode left,
TreeNode right) {
this.data = data;
this.parent = parent;
this.left = left;
this.right = right;
}
}
private TreeNode root;
public ThreeLinkBinTree(){
this.root = new TreeNode();
}
//以指定元素创建
public ThreeLinkBinTree(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;
}
//让新节点的parent引用指向parent节点
newNode.parent = parent;
return newNode;
}
//判断二叉树是否为空
public boolean isEmpty(){
return root.data == null;
}
//获取根节点
public TreeNode getRoot(){
if(isEmpty()){
throw new RuntimeException("树为空，无法获取根节点！");
}
return root;
}
//获取指定节点的父节点
public TreeNode getParent(TreeNode node){
if(node == null){
throw new RuntimeException("节点为空，无法获取父节点！");
}
if(root == node){
throw new RuntimeException("根节点无法获取父节点！");
}
return node.parent;
}
//获取指定节点的左子节点
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);
}
}从上面的代码可以看出，三叉链表存储只是对而二叉链表的改进，通过增加一个parent的引用，可以让每个节点都能方便地访问其父节点。
这篇关于java用三叉链表构建二叉树,二叉树的三叉链表存储及其Java实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
