数据结构:二叉树

数据结构-二叉树

为什么使用二叉树

结合了另外两种数据结构的优点

• 有序数组-在树中查找数据项的速度在和有序数组中查找一样快
• 链表-插入和删除数据项也和链表一样快

树的结构

节点Node.java

public class Node{
	int iData;		//当前值
	Node leftChild;	//左节点
	Node rightChild;	//右节点
}

树骨架Tree.java

public class Tree{
	private Node node;
	//插入某个节点
	public void insert(int iData){}
	//查找某个节点
	public void find(int iData){}
	//删除某个节点
	public void delete(int iData){}
	//省略其他方法...
}

1.插入方法

代码

public void insert(int iData){
	//构造一个节点
	Node newNode=new Node();
	newNode.iData=iData;
	//如果该树为空时，直接把根节点变为该节点
	if(root==null){
		root=newNode;
	}else{
		Node parent=root;	//每次记录上一级节点
		Node current=root;	//从根节点开始遍历
		while(true){
			parent=current;
			if(iData<current.iData){	//如果新值小于当前节点
				current=current.leftChild;	//就往左节点遍历
				if(current==null){			//左边空时
					parent.leftChild=newNode;	//把新节点赋值到该父级左节点
					return;					//退出
				}
			}else{
				current=current.rightChild;
				if(current==null){
					parent.rightChild=newNode;
					return;
				}
			}
		}
	}
}

2.插入方法

代码

public Node find(int iData){
	Node current=root;		//每次从根节点开始查找
	while(current!=null){
		if(current.iData==iData){	//找到了就跳出循环
			break;
		}else if(iData<current.iData){	//当前节点大于查找值时遍历左边孩子节点
			current=current.leftChild;
		}else{
			current=current.rightChild;
		}
	}
	return current;
}

3.中序，前序，后序遍历

代码

//中序遍历  打印的顺序时左->中->右节点顺序 
public void inOrder(Node node){
	if(node!=null){
		inOrder(node.leftChild);//每次打印最左边节点
		System.out.print(node.iData+" ");
		inOrder(node.rightChild);
	}
}
//前序遍历  打印的顺序时中->左->右节点顺序 
public void preOrder(Node node){
	if(node!=null){
		System.out.print(node.iData+" ");
		preOrder(node.leftChild);
		preOrder(node.rightChild);
	}
}

//后序遍历  打印的顺序时左->右->中节点顺序 
public void postOrder(Node node){
	if(node!=null){
		postOrder(node.leftChild);
		postOrder(node.rightChild);
		System.out.print(node.iData+" ");
	}
}

输出
1 2 3 4 5 6 7 8 9 10 11 12 15 16 中序
5 1 2 3 4 6 7 8 9 10 11 12 15 16 前序
1 2 3 4 6 7 8 9 10 11 12 15 16 5 后序

4.删除目标节点

有多少子节点	删除步骤
无子节点	直接删除该节点即可
一个子节点	判断删除节点的子节点剩下的是左还是右，然后把删除的子节点挂到父节点的左或者右节点
两个子节点	1.找后继节点(继承被删除节点的位置)，默认是删除节点的右节点
	2.找新后继节点-循环遍历默认后继节点的左节点
	3.交换后继节点和删除节点的位置，后继节点的左节点变为null,删除节点的右节点变为删除节点的右节点

寻找要删除的节点代码

public boolean findDeleteNode(int iData){
	if(root==null){		//如果没有数据就返回false
		return false;
	}
		
	Node parent=root;
	Node current=root;
	boolean isLeftChild=false;
	//寻找要删除的节点
	while(current.iData!=iData){		//一直循环到找到删除的节点
		parent=current;		
		if(iData<current.iData){
			isLeftChild=true;
			current=current.leftChild;
			if(current==null){			//找不到删除节点时跳出循环
				break;
			}
		}else{
			isLeftChild=false;
			current=current.rightChild;
			if(current==null){
				break;
			}
		}
	}
	if(current==null){//没找到要删除的节点
		return false;
	}
	//删除节点无子节点时
	if(current.leftChild==null && current.rightChild==null){
		deleteNoneChild(parent,current,isLeftChild);
	}else if(current.leftChild==null){
		deleteOneChild(parent,current,current.rightChild,isLeftChild);
	}else if(current.rightChild==null){
		deleteOneChild(parent,current,current.leftChild,isLeftChild);
	}else{
		deleteTwoChild(parent,current,isLeftChild);
	}
	return true;
}

1.删除节点无子节点时

private void deleteNoneChild(Node parent,Node delNode,boolean isLeftChild){
	if(delNode==root){
		root=null;
	}else if(isLeftChild){	//如果删除节点是左节点，就把父节点的左节点变为null
		parent.leftChild=null;
	}else{
		parent.rightChild=null;
	}
}

2.删除节点有一个子节点时

private void deleteOneChild(Node parent,Node delNode,Node childNode,boolean isLeftChild){
	if(delNode=root){
		root=childNode;
	}else if(isLeftChild){
		parent.leftChild=childNode;
	}else{
		parent.rightChild=childNode;
	}
}

3.删除节点有两个子节点时

删除逻辑

public void deleteTwoChild(Node parent,Node delNode,boolean isLeftChild){
	Node successor=getSuccessor(delNode);		//获取后继节点
	if(delNode==root){
		root=successor;
	}else if(isLeftChild){		//挂靠父节点的左边位置
		parent.leftChild=successor;
	}else{
		parent.rightChild=successor;
	}
	successor.leftChild=delNode.leftChild;		//后继节点的左节点变为删除节点的左节点
}

获取后继节点逻辑 后继节点的右节点变为删除节点的右节点，并且和删除节点调换位置

public Node getSuccessor(Node delNode){
	Node successorParent=delNode;		//后继节点父级初始值
	Node successor=delNode;		//后继节点初始值
	Node current=delNode.rightChild;		//由于已经判断了有两个子节点了，第一默认后继节点就是右子节点
	
	while(current!=null){		//一直循环查找后继节点->查找最左子节点
		successorParent=successor;
		successor=current;
		current=current.leftChild;
	}
	
	if(successor!=delNode.rightChild){		//如果后继节点不是删除节点的右节点，那就可判断后继节点是最左节点
		successorParent.leftChild=successor.rightChild;		//父级左节点变为后继右节点(其实就null)
		successor.rightChild=delNode.rightChild;		//后继右节点变为删除节点的右节点
	}
	return successor;
}

注:该内容为Java数据结构和算法读后学习感悟

赏

谢谢你的激励

微信