数据结构之二叉树

 

 

    二叉树存储结构结点定义：

public class BinaryTreeNode implements Node {
	private Object data; //数据域
	private BinaryTreeNode parent; //父结点
	private BinaryTreeNode lChild; //左孩子
	private BinaryTreeNode rChild; //右孩子
	private int height; //以该结点为根的子树的高度
	private int size; //该结点子孙数（包括结点本身）

	public BinaryTreeNode() { this(null); }
	public BinaryTreeNode(Object e) {
		data = e; height = 0; size = 1;
		parent = lChild = rChild = null;
	}
	
	/******Node 接口方法******/
	public Object getData() { return data; }
	public void setData(Object obj) { data = obj;}
	/******辅助方法,判断当前结点位置情况******/
	//判断是否有父亲
	public boolean hasParent() { return parent != null;}
	//判断是否有左孩子
	public boolean hasLChild() { return lChild ! =null;}
	//判断是否有右孩子
	public boolean hasRChild() { return rChild != null;}
	//判断是否为叶子结点
	public boolean isLeaf() { return !hasLChild() && !hasRChild();}
	//判断是否为某结点的左孩子
	public boolean isLChild() { return (hasParent() && this == parent.lChild);}
	//判断是否为某结点的右孩子
	public boolean isRChild() { return (hasParent() && this == parent.rChild);}
	/******与height 相关的方法******/
	//取结点的高度,即以该结点为根的树的高度
	public int getHeight() { return height; }
	//更新当前结点及其祖先的高度
	public void updateHeight() {
		int newH = 0;//新高度初始化为0,高度等于左右子树高度加1 中的大者
		if (hasLChild()) newH = Math.max(newH, 1 + getLChild().getHeight());
		if (hasRChild()) newH = Math.max(newH, 1 + getRChild().getHeight());
		if (newH == height) return; //高度没有发生变化则直接返回
		height = newH; //否则更新高度
		if (hasParent()) getParent().updateHeight(); //递归更新祖先的高度
	}
	/******与size 相关的方法******/
	//取以该结点为根的树的结点数
	public int getSize() { return size; }
	//更新当前结点及其祖先的子孙数
	public void updateSize() {
		size = 1; //初始化为1,结点本身
		if (hasLChild()) size += getLChild().getSize(); //加上左子树规模
		if (hasRChild()) size += getRChild().getSize(); //加上右子树规模
		if (hasParent()) getParent().updateSize(); //递归更新祖先的规模
	}
	/******与parent 相关的方法******/
	//取父结点
	public BinaryTreeNode getParent() { return parent; }
	//断开与父亲的关系
	public void sever() {
		if (!hasParent()) return;
		if (isLChild()) parent.lChild = null;
		else parent.rChild = null;
		parent.updateHeight(); //更新父结点及其祖先高度
		parent.updateSize(); //更新父结点及其祖先规模
		parent = null;
	}
	/******与lChild 相关的方法******/
	//取左孩子
	public BinaryTreeNode getLChild() { return lChild; }
	//设置当前结点的左孩子,返回原左孩子
	public BinaryTreeNode setLChild(BinaryTreeNode lc) {
		BinaryTreeNode oldLC = this.lChild;
		if (hasLChild()) { lChild.sever();} //断开当前左孩子与结点的关系
		if (lc != null){
			lc.sever(); //断开lc 与其父结点的关系
			this.lChild = lc; //确定父子关系
			lc.parent = this;
			this.updateHeight(); //更新当前结点及其祖先高度
			this.updateSize(); //更新当前结点及其祖先规模
		}
		return oldLC; //返回原左孩子
	}
	/******与rChild 相关的方法******/
	//取右孩子
	public BinaryTreeNode getRChild() { return rChild; }
	//设置当前结点的右孩子,返回原右孩子
	public BinaryTreeNode setRChild(BinaryTreeNode rc) {
		BinaryTreeNode oldRC = this.rChild;
		if (hasRChild()) { rChild.sever();} //断开当前右孩子与结点的关系
		if (rc != null){
			rc.sever(); //断开lc 与其父结点的关系
			this.rChild = rc; //确定父子关系
			rc.parent = this;
			this.updateHeight(); //更新当前结点及其祖先高度
			this.updateSize(); //更新当前结点及其祖先规模
		}
		return oldRC; //返回原右孩子
	}
}

 

 

    二叉树遍历：

public class BinaryTree { 
	private BinaryTreeNode root;
	private Strategy strategy;
	
	public BinaryTree() { this(null, null); }
	public BinaryTree(BinaryTreeNode root, Strategy strategy) {
		this.root = root;
		this.strategy = strategy;
	}
	
	//先序遍历二叉树
	public Iterator preOrder() {
		LinkedList list = new LinkedListDLNode();
		preOrderRecursion(this.root, list);
		//preOrderTraverse (root,list);
		return list.elements();
	}
	//先序遍历的递归算法
	private void preOrderRecursion(BinaryTreeNode rt, LinkedList list) {
		if (rt == null) return; //递归基,空树直接返回
		list.insertLast(rt); //访问根结点
		preOrderRecursion(rt.getLChild(), list); //遍历左子树
		preOrderRecursion(rt.getRChild(), list); //遍历右子树
	}
	//先序遍历的非递归算法
	private void preOrderTraverse(BinaryTreeNode rt, LinkedList list) {
		if (rt == null) return;
		BinaryTreeNode p = rt;
		Stack s = new StackLinked();
		while (p != null) {
			while (p != null) { //向左走到尽头
				list.insertLast(p);	//当前遍历节点
				if (p.hasRChild())
					s.push(p.getRChild()); //右子树根结点入栈
				p = p.getLChild();
			}
			if (!s.isEmpty()) p = (BinaryTreeNode) s.pop(); //右子树根退栈遍历右子树
		}
	}
	//中序遍历二叉树
	public Iterator inOrder() {
		LinkedList list = new LinkedListDLNode();
		inOrderTraverse(this.root, list);
		return list.elements();
	}
	//中序遍历的非递归算法
	private void inOrderTraverse(BinaryTreeNode rt, LinkedList list) {
		if (rt == null) return;
		BinaryTreeNode p = rt;
		Stack s = new StackLinked();
		while (p != null || !s.isEmpty()) {
			while (p != null) { //一直向左走
				s.push(p); //将根结点入栈
				p = p.getLChild();
			}
			if (!s.isEmpty()) {
				p = (BinaryTreeNode) s.pop();//取出栈顶根结点访问之
				list.insertLast(p);
				p = p.getRChild(); //转向根的右子树进行遍历
			}//if
		}//out while
	}
	//后序遍历二叉树
	public Iterator postOrder() {
		LinkedList list = new LinkedListDLNode();
		postOrderTraverse (this.root,list);
		return list.elements();
	}
	//后序遍历的非递归算法
	private void postOrderTraverse(BinaryTreeNode rt, LinkedList list) {
		if (rt == null) return;
		BinaryTreeNode p = rt;
		Stack s = new StackLinked();
		while(p != null || !s.isEmpty()) {
			while (p != null){ //先左后右不断深入
				s.push(p); //将根节点入栈
				if (p.hasLChild()) 
					p = p.getLChild();
				else 
					p = p.getRChild();
			}
			if (!s.isEmpty()) {
				p = (BinaryTreeNode) s.pop(); //取出栈顶根结点访问之
				list.insertLast(p);
			}
			//满足条件时，说明栈顶根节点右子树已访问，应出栈访问之
			while (!s.isEmpty() && ((BinaryTreeNode) s.peek()).getRChild() == p) {
				p = (BinaryTreeNode)s.pop();
				list.insertLast(p);
			}
			//转向栈顶根结点的右子树继续后序遍历
			if (!s.isEmpty()) 
				p = ((BinaryTreeNode) s.peek()).getRChild();
			else 
				p = null;
		}
	}
	//按层遍历二叉树
	public Iterator levelOrder() {
		LinkedList list = new LinkedListDLNode();
		levelOrderTraverse(this.root, list);
		return list.elements();
	}
	//使用队列完成二叉树的按层遍历
	private void levelOrderTraverse(BinaryTreeNode rt, LinkedList list) {
		if (rt == null) return;
		Queue q = new QueueArray();
		q.enqueue(rt); //根结点入队
		while (!q.isEmpty()) {
			BinaryTreeNode p = (BinaryTreeNode) q.dequeue(); //取出队首结点p 并访问
			list.insertLast(p);
			if (p.hasLChild()) 
				q.enqueue(p.getLChild());//将p 的非空左右孩子依次入队
			if (p.hasRChild()) 
				q.enqueue(p.getRChild());
		}
	}
	//在树中查找元素e，返回其所在结点
	public BinaryTreeNode find(Object e) {
		return searchElement(this.root, e);
	}
	//递归查找元素e
	private BinaryTreeNode searchElement(BinaryTreeNode rt, Object e) {
		if (rt == null) 
			return null;
		if (strategy.equal(rt.getData(), e)) 
			return rt; //如果是根结点，返回根
		BinaryTreeNode result = searchElement(rt.getLChild(), e); //否则在左子树中找
		if (result == null)
			result = searchElement(rt.getRChild(), e); //没找到，在右子树中找
		return result;
	}
}