文档章节

二叉树(3)——三叉链表示的二叉树

自由的角马
 自由的角马
发布于 2015/01/10 13:57
字数 1772
阅读 11
收藏 0

三叉链表示的二叉树定义

所畏的三叉链表示是指二叉树由指向左孩子结点、右孩子结点、父亲结点【三叉】的引用(指针)数据和数据组成。
package datastructure.tree.btree;
/**
 * 三叉链表示的二叉树定义
 * @author Administrator
 *
 */
public class BinTreeNode{
	private Object data; // 数据域
	private BinTreeNode parent; // 父节点
	private BinTreeNode lChild; // 左孩子
	private BinTreeNode rChild; // 右孩子
	private int height; // 以该节点为根的子树的高度
	private int size; // 该节点子孙数(包括结点本身)

	public BinTreeNode() {
		this(null);
	}

	public BinTreeNode(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;
	}
	

	//-------------辅助方法,判断当前结点位置的情况------------
	/**
	 * 判断是否有父亲
	 * @return
	 */
	public boolean hasParent() {
		return parent != null;
	}
	
	/**
	 *  判断是否有左孩子
	 * @return 如果有左孩子结点返回true,否则返回false
	 */
	public boolean hasLChild() {
		return null != lChild;
	}

	/**
	 *  判断是否有右孩子
	 * @return
	 */
	public boolean hasRChild() {
		return null != rChild;
	}

	/**
	 *  判断是否为叶子结点
	 * @return
	 */
	public boolean isLeaf() {
		return (!hasLChild() && !hasRChild());
	}

	/**
	 *  判断是否为某节点的左孩子
	 * @return
	 */
	public boolean isLChild() {
		return (hasParent() && this == parent.lChild);
	}

	/**
	 *  判断是否为某结点的右孩子
	 * @return
	 */
	public boolean isRChild() {
		return (hasParent()) && this == parent.rChild;
	}
	
	//-------------- 与height相关的方法-----------------	
	/**
	 * 取结点的高度,即以该节点为根的树的高度
	 * @return
	 */
	public int getHeight() {
		return height;
	}
	
	/**
	 *  更新当前结点及其祖先的高度
	 */
	public void updateHeight() {
		int newH = 0;// 新高度初始化为0,高度等于左右子树加1中的较大值
		if (hasLChild())
			newH = Math.max(newH, (lChild.getHeight() + 1));// //////////////???
		if (hasRChild())
			newH = Math.max(newH, (rChild.getHeight() + 1));// 先0和左孩子的高度加1进行比较,后左孩子高度加1和右孩子高度加1进行比较
		if (newH == height)
			return; // 高度没有发生变化则直接返回
		height = newH; // 否则,更新高度
		if (hasParent()) // 递归更新祖先的高度
			parent.updateHeight();
	}

	/********* 与size相关的方法 **********/
	/**
	 *  取以该节点为根的树的结点数
	 * @return
	 */
	public int getSize() {
		return size;
	}

	/**
	 *  更新当前结点及祖先的子孙数
	 */
	public void updateSize() {
		size = 1; // 初始化为1,结点本身
		if (hasLChild())
			size = size + lChild.getSize(); // 加上左子树的规模
		if (hasRChild())
			size = size + rChild.getSize(); // 加上右子树的规模
		if (hasParent())
			parent.updateSize();
	}

	/********** 与parent相关的方法 **********/
	/**
	 *  取父节点
	 * @return
	 */
	public BinTreeNode 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相关的方法 ********/
	/**
	 *  取左孩子
	 * @return
	 */
	public BinTreeNode getLChild() {
		return lChild;
	}

	/**
	 *  设置当前结点的左孩子,返回原左孩子
	 * @param lc
	 * @return
	 */
	public BinTreeNode setLChild(BinTreeNode lc) {
		BinTreeNode oldLC = this.lChild;
		if (hasLChild()) {
			lChild.sever();
		} // 断开当前左孩子与结点的关系
		if (null != lc) {
			lc.sever(); // 判断lc与其父节点的关系
			this.lChild = lc; // 确定父子关系
			lc.parent = this;
			this.updateHeight(); // 更新当前结点及其祖先的高度
			this.updateSize(); // 更新当前结点及其祖先的规模
		}
		return oldLC; // 返回原左孩子
	}

	//********** 与rChild相关的方法 *********/
	/**
	 *  取右孩子
	 * @return
	 */
	public BinTreeNode getRChild() {
		return rChild;
	}

	/**
	 *  设置当前结点为右孩子,返回原右孩子
	 * @param rc
	 * @return
	 */
	public BinTreeNode setRChild(BinTreeNode rc) {
		BinTreeNode oldRC = this.rChild;
		if (hasRChild()) {
			rChild.sever();
		} // 断开当前右孩子与结点的关系
		if (null != rc) {
			rc.sever(); // 断开rc与其父节点的关系
			this.rChild = rc; // 确定父子关系
			rc.parent = this;
			this.updateHeight(); // 更新当前结点及其祖先的高度
			this.updateSize(); // 更新当前结点及其祖先的规模
		}
		return oldRC; // 返回原右孩子
	}
	/**
	 * 重写toString方法
	 */
	public String toString() {
		return "" + data;
	}

}

三叉链表示的二叉树的遍历

package datastructure.tree.btree;

import java.util.*;

import datastructure.common.Strategy;

import datastructure.queue.Queue;
import datastructure.queue.ArrayQueue;
/**
 * 三叉链表示的二叉树的遍历
 * @author luoweifu
 *
 */
public class BinaryTreeOrder {
	private int leafSize = 0;
	private BinTreeNode root = null;
	Strategy strategy = new StrategyEqual();
	
	/**
	 * 构造函数,传入树的根结点
	 * @param node
	 *            树的根结点
	 */
	public BinaryTreeOrder(BinTreeNode node) {
		this.root = node;
		Strategy strategy = new StrategyEqual();
	}
	
	public BinTreeNode getRoot() {
		return root;
	}

	/**
	 * 前序遍历
	 * 
	 * @return 返回一个Iterator容器
	 */
	public Iterator preOrder() {
		List<BinTreeNode> list = new LinkedList();
		preOrderRecursion(this.root, list);
		return list.iterator();
	}

	/**
	 * 递归定义前序遍历
	 * @param rt
	 *            树根结点
	 * @param list
	 *            LinkedList容器
	 */
	private void preOrderRecursion(BinTreeNode rt, List list) {
		if (null == rt)
			return; // 递归基,空树直接返回
		list.add(rt); // 访问根节点
		preOrderRecursion(rt.getLChild(), list);// 遍历左子树
		preOrderRecursion(rt.getRChild(), list);// 遍历右子树
	}

	/**
	 * 中序遍历
	 * 
	 * @return
	 */
	public Iterator inOrder() {
		List<BinTreeNode> list = new LinkedList();
		inOrderRecursion(this.root, list);
		return list.iterator();
	}

	/**
	 * 递归定义中序遍历
	 * @param rt
	 *            树根结点
	 * @param list
	 *            LinkedList容器
	 */
	private void inOrderRecursion(BinTreeNode rt, List list) {
		if (null == rt)
			return; // 递归基,空树直接返回
		inOrderRecursion(rt.getLChild(), list);// 遍历左子树
		list.add(rt); // 访问根节点
		inOrderRecursion(rt.getRChild(), list);// 遍历右子树
	}

	/**
	 *  后序遍历
	 * @return
	 */
	public Iterator postOrder() {
		List<BinTreeNode> list = new LinkedList();
		postOrderRecursion(this.root, list);
		return list.iterator();
	}
	
	/**
	 * 递归定义后序遍历
	 * @param rt
	 *            树根结点
	 * @param list
	 *            LinkedList容器
	 */
	private void postOrderRecursion(BinTreeNode rt, List list) {
		if (null == rt)
			return; // 递归基,空树直接返回
		postOrderRecursion(rt.getLChild(), list);// 遍历左子树
		postOrderRecursion(rt.getRChild(), list);// 遍历右子树
		list.add(rt);// 访问根节点
	}

	/**
	 *  按层遍历
	 * @return
	 */
	public Iterator levelOrder() {
		List<BinTreeNode> list = new LinkedList();
		levelOrderTraverse(this.root, list);
		return list.iterator();
	}

	/**
	 *  使用队列完成二叉树的按层遍历
	 * @param rt
	 * @param list
	 */
	private void levelOrderTraverse(BinTreeNode rt, List list) {
		if (null == rt)
			return;
		Queue q = new ArrayQueue();
		q.push(rt);// 根节点入队列
		while (!q.isEmpty()) {
			BinTreeNode p = (BinTreeNode) q.deQueue(); // 取出队首节点p并访问
			list.add(p);
			if (p.hasLChild())
				q.push(p.getLChild()); // 将p的非空左右孩子依次入队列
			if (p.hasRChild())
				q.push(p.getRChild());
		}
	}

	/**
	 *  在树中查找元素e,并返回其所在的结点
	* @param e 要查找的数据元素
	 * @return 返回找到的结点
	 */
	public BinTreeNode find(Object e) {
		return searchE(root, e);
	}

	/**
	 * 递归查找元素e
	 * @param rt 树的根
	 * @param e 要查找的数据元素
	 * @return 返回找到的结点
	 */
	private BinTreeNode searchE(BinTreeNode rt, Object e) {
		if (null == rt)
			return null;
		if (strategy.equal(rt.getData(), e))
			return rt;
		BinTreeNode v = searchE(rt.getLChild(), e);
		if (null == v)
			v = searchE(rt.getRChild(), e);
		return v;
	}
	/**
	 * 打印二叉树
	 * @return
	 */
	public String printBinTree() {
		StringBuilder sb = new StringBuilder();
		printBinTree(root, 0, sb);
		return sb.toString();
	}

	/**
	 * 打印二叉树
	 * @param btree 根结点
	 * @param n 结点层数
	 * @param sb 用于保存记录的字符串
	 */
	private void printBinTree(BinTreeNode btree, int n, StringBuilder sb) {
		if (null == btree)
			return;
		printBinTree(btree.getRChild(), n + 1, sb);
		for (int i = 0; i < n; i++)
			sb.append("\t");
		if (n >= 0)
			sb.append(btree.getData() + "\n");
		printBinTree(btree.getLChild(), n + 1, sb);
	}

	 /**
	  * 求叶结点的个数
	  * @return 叶结点的个数
	  */
	public int sizeLeaf() {
		searchLeaf(this.root);
		return leafSize;
	}
	/**
	 * 叶结点的个数
	 * @param rt
	 */
	private void searchLeaf(BinTreeNode rt) {
		if (null == rt)
			return;
		if (rt.isLeaf())
			leafSize++;
		else {
			searchLeaf(rt.getLChild());
			searchLeaf(rt.getRChild());
		}
	}

}

测试

package datastructure.tree.btree;

import java.util.Iterator;

public class BTreeTest2 {
	// 测试功能
	// 结果:所有功能都能实现,正确
	public static void main(String args[]) {
		//构造二叉树
		BinTreeNode roots = new BinTreeNode();
		BinTreeNode node = new BinTreeNode();
		roots.setData('A');
		roots.setLChild(new BinTreeNode('B'));
		roots.setRChild(new BinTreeNode('C'));
		node = roots.getLChild();
		node.setLChild(new BinTreeNode('D'));
		node.setRChild(new BinTreeNode('E'));
		node = roots.getRChild();
		node.setLChild(new BinTreeNode('F'));
		BinaryTreeOrder order = new BinaryTreeOrder(roots);
		//------遍历--------
		Iterator<BinTreeNode> iter1 = order.preOrder();
		System.out.println("前序遍历:");
		printIterator(iter1);
		
		Iterator<BinTreeNode> iter2 = order.inOrder();
		System.out.println("中序遍历:");
		printIterator(iter2);
		
		Iterator<BinTreeNode> iter3 = order.postOrder();
		System.out.println("后序遍历:");
		printIterator(iter3);
		
		Iterator<BinTreeNode> iter4 = order.levelOrder();
		System.out.println("层次遍历:");
		printIterator(iter4);
				
		String str = order.printBinTree();
		System.out.println("打印二叉树:\n" + str);
		System.out.println("叶结点的个数:" + order.sizeLeaf()); 
		BinTreeNode nodeone = order.find('E'); 
		System.out.println("根结点的数据元素:" + nodeone.getData());
	}
	public static void printIterator(Iterator<BinTreeNode> iter) {
		while(iter.hasNext()) {
			System.out.print("\t" + iter.next().getData());
		}
		System.out.println();
	}
	
}

结果:

前序遍历:
A BD E C F
中序遍历:
D BE A F C
后序遍历:
D EB F C A
层次遍历:
A BC D E F
打印二叉树:
C
F
A
E
B
D


叶结点的个数:3
根结点的数据元素:E

本文转载自:http://blog.csdn.net/luoweifu/article/details/9089551

自由的角马
粉丝 1
博文 269
码字总数 0
作品 0
文山
私信 提问
二叉树链式存储结构(Binary Tree)

二叉树链式存储结构(Binary Tree) 所谓二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示着元素的逻辑关系。通常有下面两种形式。 (1)二叉链表存储 链表中每个结点由三个...

秋风醉了
2014/06/01
176
0
小蚂蚁学习数据结构(17)——树、二叉树性质、储存方式

树 是一类非线性数据结构,是以分支关系定义的层次结构。 特点: 至少有一个节点——根,只有根的树成为最小树 树中各子树是互不相交的集合 术语(略) 二叉树 特点: 每个节点最多有二颗子树...

嗜学如命的小蚂蚁
2016/01/17
72
0
树/二叉树(哈夫曼树/红黑树)笔记

1.树是一种常用数据结构,它是非线性结构。 2.树中任一普通节点可以有0或者多个子节点,但只能有一个父节点。 根节点没有父节点,叶子节点没有子节点。 3.二叉树: 1)每个节点最多只能有两个...

6pker
2015/08/14
518
0
若干数据结构 && 算法面试题【四】(更新ing)

这是我的第三个面试题汇总。 想看之前的内容请移步 http://zhweizhi.blog.51cto.com/10800691/1763237 若干数据结构 && 算法面试题【一】更新完毕 http://zhweizhi.blog.51cto.com/10800691/...

shangluyi
2016/07/08
0
0
Android技能树 — 树基础知识小结(一)

前言: 现在安卓面试,对于数据结构的问题也越来越多了,也经常看到别人发的面试题都是问什么红黑树,二叉树查找等,所以我们虽然不会马上就会各种难的面试题,但起码树的基础知识还是要会的...

青蛙要fly
2018/05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

总结

一、设计模式 简单工厂:一个简单而且比较杂的工厂,可以创建任何对象给你 复杂工厂:先创建一种基础类型的工厂接口,然后各自集成实现这个接口,但是每个工厂都是这个基础类的扩展分类,spr...

BobwithB
26分钟前
2
0
java内存模型

前言 Java作为一种面向对象的,跨平台语言,其对象、内存等一直是比较难的知识点。而且很多概念的名称看起来又那么相似,很多人会傻傻分不清楚。比如本文我们要讨论的JVM内存结构、Java内存模...

ls_cherish
29分钟前
2
0
友元函数强制转换

友元函数强制转换 p522

天王盖地虎626
昨天
5
0
js中实现页面跳转(返回前一页、后一页)

本文转载于:专业的前端网站➸js中实现页面跳转(返回前一页、后一页) 一:JS 重载页面,本地刷新,返回上一页 复制代码代码如下: <a href="javascript:history.go(-1)">返回上一页</a> <a h...

前端老手
昨天
5
0
JAVA 利用时间戳来判断TOKEN是否过期

import java.time.Instant;import java.time.LocalDateTime;import java.time.ZoneId;import java.time.ZoneOffset;import java.time.format.DateTimeFormatter;/** * @descri......

huangkejie
昨天
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部