java用三叉链表构建二叉树

java用三叉链表构建二叉树

package com.fcy.dataStruct;

/**

* 与二叉树的二叉链表存储相比，三叉链表存储

* 多了一个指针域来记录当前节点的父节点

*/

class ThreeLinkBinTree{

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(){

<=new TreeNode();

}

//以指定根元素来创建二叉树

public ThreeLinkBinTree(E data){

<=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+"节点为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{

//让父节点的right引用指向新节点

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;

}

//返回指定节点(非叶子)的左子节点

public E leftChild(TreeNode parent){

if(parent==null){

throw new RuntimeException("节点为Null,无法添加子节点");

}

return parent.left==null?null:(E)parent.left.data;

}

//返回指定节点(非叶子)的右子节点

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 class ThreeLinkBinDemo {

public static void main(String[] args) {

ThreeLinkBinTree binTree=new ThreeLinkBinTree<>("根节点");

ThreeLinkBinTree.TreeNode tn1=binTree.(),"第二层左节点",true);

ThreeLinkBinTree.TreeNode tn2=binTree.(),"第二层右节点",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.leftChild(tn2));

System.out.println("tn2的右子节点："+binTree.rightChild(tn2));

System.out.println("tn3的父节点："+binTree.parent(tn3));

System.out.println(binTree.deep());

}

}

运行结果：