博客

二叉链表：用链表来表示一棵二叉树




链表的每个结点由三个域组成，data域存放某j结点的数据信息，lChild与rChild分别存放指向左孩子和右孩子的指针。



–>结点定义

class Node<T>{
	Node<T> lChild;
	T data;
	Node<T> rChild;
	Node(){
		data=null;
		lChild=null;
	    rChild=null;
	}
	Node(T x){
		data=x;
		lChild=null;
	    rChild=null;
	}
}

–>建立一棵空二叉树

BinaryTree(){
	root=new Node<T>();
}

–>生成一棵二叉树

BinaryTree(T x){
	root=new Node<T>(x);
}

–>插入一个左孩子节点

boolean insertLeft(T x,Node<T> parent){
	if(parent==null){
		return false;
	}
	Node<T> p=new Node<T>(x);
	if(parent.lChild==null){
		parent.lChild=p;
	}else{
		p.lChild=parent.lChild;
		parent.lChild=p;
	}
	return true;
}	

–>插入一个右孩子节点

boolean insertRight(T x,Node<T> parent){
	if(parent==null){
		return false;
	}
	Node<T> p=new Node<T>(x);
	if(parent.rChild==null){
		parent.rChild=p;
	}else{
		p.rChild=parent.rChild;
		parent.rChild=p;
	}
	return true;
}

–>删除左子树

boolean deleteLeft(Node<T> parent){
	if(parent==null){
		return false;
	}else{
		parent.lChild=null;
		return true;
	}
}

–>删除右子树

boolean deleteRight(Node<T> parent){
	if(parent==null){
		return false;
	}else{
		parent.rChild=null;
		return true;
	}
}