【二叉树】二叉树操作汇总 - 木东驿站 - Powered by MoodBlog

CONTENT

【二叉树】二叉树操作汇总

二叉树这一块的盲点挺多的,好后悔上学期没好好学习《数据结构》啊,现在发现这门课真是有趣。

当时我在制作《梦战》,记得每个周末我都要去图书馆抢位置的,为的是抢到一个有插座的座位,好让笔记本电脑能够支撑一整天。

为什么不在宿舍写代码呢?

一方面是舍友总是很吵,影响自己集中注意力。

另一方面,宿舍太舒适了,网速还快,不弱于网吧的配置根本无法让人静下心来码字啊。

有同学问我后悔制作那款堪称"10万行水代码堆起来"的游戏吗,要说遗憾肯定是有的,毕竟让自己落下了一些课程。但绝对谈不上后悔,梦战的制作让我对面向对象以及架构设计的理解远高于其他同学,我觉得这份收获会使我终生受益。

今天下午抽了点时间实现了二叉树的各种操作,比如建立,各种遍历,线索化等等,分享给大家。

JAVA代码如下:

import java.util.Scanner;
class BTNode{
	char data;//数据节点
	BTNode lchild,rchild;//左右子树
	int ltag,rtag;//线索二叉树标记
}
class BTree{
	private BTNode topnode;//二叉树根节点
	private String s;//建立树的字符串
	private int index;//当前s位置
	
	private BTNode threadnode;//线索头节点
	private BTNode pre;//临时前驱节点 建立线索时使用
	
	private BTNode lastNode;//查找子树中序遍历最后节点
	BTree(String s){
		this.s = s;
	}
	//根据先序字符串建立二叉树
	void createBTree(BTNode node,int i,int kind){
		index++;
		if(index>=s.length()||s.charAt(index)==' '){
			return;
		}else{
			if(kind==0){
				node.lchild = new BTNode();
				node.lchild.data = s.charAt(index);
				createBTree(node.lchild,index,0);
				createBTree(node.lchild,index,1);
			}else if(kind==1){
				node.rchild = new BTNode();
				node.rchild.data = s.charAt(index);
				createBTree(node.rchild,index,0);
				createBTree(node.rchild,index,1);
			}
		}
	}
	void createBTree(){
		if(s.charAt(0)!=' '){
			topnode = new BTNode();
			topnode.data = s.charAt(0);
			index = 0;
			createBTree(topnode,index,0);
			createBTree(topnode,index,1);
		}
	}
	//先序遍历二叉树
	void preSearch(BTNode node){
		if(node!=null){
			System.out.print(node.data+" ");
			preSearch(node.lchild);
			preSearch(node.rchild);			
		}
	}
	void preSearch(){
		if(topnode!=null){
			System.out.print(topnode.data+" ");
			preSearch(topnode.lchild);
			preSearch(topnode.rchild);
		}
	}
	//中序遍历二叉树
	void inSearch(BTNode node){
		if(node!=null){
			inSearch(node.lchild);
			System.out.print(node.data+" ");
			inSearch(node.rchild);			
		}		
	}
	//中序线索遍历二叉树
	boolean inSearchByThread(){
		if(threadnode==null){
			return false;
		}
		BTNode node = threadnode.lchild;
		while(node!=threadnode){
			while(node.ltag==0){
				node = node.lchild;
			}
			System.out.print(node.data+" ");
			while(node.rtag==1&&node.rchild!=threadnode){
				node = node.rchild;
				System.out.print(node.data+" ");
			}
			node = node.rchild;
		}
		return true;
	}	
	void inSearch(){
		//优先使用线索遍历二叉树
		if(inSearchByThread()==true){
			return;
		}
		if(topnode!=null){
			inSearch(topnode.lchild);
			System.out.print(topnode.data+" ");
			inSearch(topnode.rchild);
		}
	}
	//后序遍历二叉树
	void laterSearch(BTNode node){
		if(node!=null){
			laterSearch(node.lchild);
			laterSearch(node.rchild);	
			System.out.print(node.data+" ");
		}			
	}
	void laterSearch(){
		if(topnode!=null){
			laterSearch(topnode.lchild);
			laterSearch(topnode.rchild);
			System.out.print(topnode.data+" ");
		}		
	}
	//建立中序线索
	void createThread(){
		threadnode = new BTNode();
		if(topnode==null){
			threadnode.lchild = threadnode;
		}else{
			threadnode.ltag = 0;
			threadnode.rtag = 1;
			pre = threadnode;
			threadnode.lchild = topnode;
			Thread(topnode);
			threadnode.rchild = pre;
			pre.rchild = threadnode;
			pre.rtag = 1;
		}
	}
	void Thread(BTNode node){
		if(node==null){
			return;
		}
		Thread(node.lchild);
		if(node.lchild!=null){
			node.ltag = 0;
		}else{
			node.ltag = 1;
			node.lchild = pre;
		}
		if(pre.rchild!=null){
			pre.rtag = 0;
		}else{
			pre.rtag = 1;
			pre.rchild = node;
		}
		pre = node;
		Thread(node.rchild);
	}
	//寻找子树中中序遍历第一节点
	BTNode searchFirstNode(BTNode node){
		while(node.ltag==0){
			node = node.lchild;
		}
		return node;
	}
	//寻找子树中序遍历最后一节点
	BTNode searchLastNode(BTNode node){
		if(node.ltag==0){
			lastNode = searchLastNode(node.lchild);
		}
		lastNode = node;
		if(node.rtag==0){
			lastNode = searchLastNode(node.rchild);
		}
		return lastNode;
	}
	//寻找中序线索二叉树某节点的上一个节点
	BTNode searchParentNode(BTNode node){
		if(node.ltag==1){
			return node.lchild;
		}else{
			return searchLastNode(node.lchild);
		}
	}
	//寻找中序线索二叉树某节点的下一个节点
	BTNode searchChildNode(BTNode node){
		if(node.rtag==1){
			return node.rchild;
		}else{
			return searchFirstNode(node.rchild);
		}
	}
}


个快快 2017年11月03日 天气 晴

REMARKS

© 2018 MoodBlog 0.2 个快快 作品 | 参考主题: mathilda by fuzzz. | 鲁ICP备16047814号