文档章节

三叉链表存储二叉树

JiaChang
 JiaChang
发布于 2016/08/03 16:12
字数 851
阅读 17
收藏 0

二叉树的三叉链式存储

三叉链式存储的思想是让每个节点不仅“记住”它的左,右两个节点,还要“记住”它的父节点,因此每个节点需要leftrightparent三个指针。

 

    三叉链表存储方式是对二叉链表的一种改进,通过为树节点添加一个parent引用,可以让每个节点都能非常方便地访问其父节点。

三叉链表存储二叉树的节点定义

//三叉链表存储二叉树的节点定义
	class Node{
		Object data;	//节点数据
		Node left;		//左孩子指针
		Node rigth;		//右孩子指针
		Node parent;	//父节点指针
		
		public Object getData() {
			return data;
		}
		
		
	}

为指定节点添加子节点

/***
	 * 为指定节点添加子节点
	 * @param parent 指定节点
	 * @param data	新节点的数据
	 * @param isLift 是否为左孩子
	 * @return 返回新添加的节点
	 */
	public Node add(Node parent, E data, boolean isLeft){
		if(parent==null){
			throw new RuntimeException("指定节点为null,无法添加子节点");
		}
		if(isLeft&&parent.left!=null){
			throw new RuntimeException("指定节点已经存在左孩子,无法添加子节点");
		}
		if(!isLeft&&parent.rigth!=null){
			throw new RuntimeException("指定节点已经存在右孩子,无法添加子节点");
		}
		
		Node newNode = new Node();
		newNode.data = data;
		newNode.parent = parent;
		if(isLeft){
			parent.left = newNode;
			
		}
		else {
			parent.rigth = newNode;
		}
		return newNode;
		
	}

返回指定节点的父节点数据

/***
	 * 返回指定节点的父节点数据
	 * @param node
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public E getParent(Node node){
		if(node==null){
			throw new RuntimeException("指定节点为null,无法访问其父节点");
		}
		return (E) node.parent.data;
	}

返回指定节点左孩子节点

/***
	 * 返回指定节点的左孩子节点数据
	 * @param node 指定节点
	 * @return 如果左孩子节点不存在则返回null,否则返回左孩子节点的数据
	 */
	@SuppressWarnings("unchecked")
	public E leftChild(Node node){
		if(node==null){
			throw new RuntimeException("指定节点为null,无法访问其左孩子节点");
		}
		return node.left.data==null?null: (E) node.left.data;		//如果没有左孩子节点则返回空,使用三目运算符判断一下不至于抛空指针异常
	}

返回指定节点右孩子节点

/***
	 * 返回指定节点的右孩子节点数据
	 * @param node 指定节点
	 * @return 如果右孩子节点不存在则返回null,否则返回右孩子节点的数据
	 */
	@SuppressWarnings("unchecked")
	public E rigthChild(Node node){
		if(node==null){
			throw new RuntimeException("指定节点为null,无法访问其右孩子节点");
		}
		return node.rigth.data==null?null: (E) node.rigth.data;		//如果没有右孩子节点则返回空,使用三目运算符判断一下不至于抛空指针异常
	}

返回树的深度

/***
	 * 计算二叉树的深度(后序遍历)
	 * @param root 根节点
	 * @return 树的深度
	 */
	public int deep(Node root){
		if(root==null) return 0;	//如果是空树,深度为0,递归结束
		else {
			int m = deep(root.left);	//递归计算左子树的深度记为m
			int n = deep(root.rigth);	//递归计算右子树的深度记为n
			return m>n? m+1:n+1;	//二叉树的深度为 m 与 n的较大者加1
		}
	}

返回节点个数

/***
	 * 统计二叉树中节点的个数(递归)
	 * @param root 根节点
	 * @return 节点个数
	 */
	public int nodeCount(Node root){
		if(root==null) return 0;	//如果是空树,则节点个数为0,递归结束
		else return nodeCount(root.left)+nodeCount(root.rigth)+1;	//否则节点个数为左子树的节点个数+右子树的节点个数+1
	}

源代码(直接克隆或则下载即可):

https://github.com/JiaChangFormCHN/tree-learn.git

© 著作权归作者所有

上一篇: 排序二叉树
JiaChang
粉丝 3
博文 35
码字总数 21583
作品 0
海口
程序员
私信 提问
二叉树链式存储结构(Binary Tree)

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

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

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

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

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

6pker
2015/08/14
0
0
二叉树知识点总结

树的相关术语: 结点的度:一个结点的子树的数量。 树的度:该树中结点的最大度数。 叶结点和分支结点:度为0的结点和度不为0的结点。 树的深度:树中结点的最大层数。 有序树和无序树:树中...

lindianlide
2014/09/01
0
0
Android技能树 — 树基础知识小结(一)

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

青蛙要fly
2018/05/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Webpack打包优化:使用外链与拆包模式

一、发现问题 这是一个基于 vue-cli 的管理后台项目,由于依赖较多,打包结果如下 二、查找原因 为什么 vendor 体积这么大? 引用的库太多时,vendor的体积会很大,借助 Webpack 的分析工具,...

AI考拉
22分钟前
0
0
MSSQL-最佳实践-Always Encrypted

author: 风移 摘要 在SQL Server安全系列专题月报分享中,往期我们已经陆续分享了:如何使用对称密钥实现SQL Server列加密技术、使用非对称密钥实现SQL Server列加密、使用混合密钥实现SQL S...

阿里云云栖社区
24分钟前
1
0
ES 集群上,业务单点如何优化升级?

摘要: 原创出处 https://www.bysocket.com 「公众号:泥瓦匠BYSocket 」欢迎关注和转载,保留摘要,谢谢! ES 基础 ES 集群 ES 集群上业务优化 一、ES 基础 ES 的安装下载,网上一大片,我这...

泥瓦匠BYSocket
40分钟前
4
0
input accept属性限制文件上传格式

上传文件的类型;具体做法如下所示: 注意:accept属性可以限制上传格式,其有兼容性如下 《1》上传.csv格式的 <input text="file" accept=".csv" /> 《2》上传.xls格式 <input text="file"......

Jack088
47分钟前
1
0
使用scp命令在多个Linux系统间进行文件复制

一,什么是scp scp是linux系统下基于ssh登陆进行安全的远程文件拷贝命令。scp命令可以在linux服务器之间复制文件和目录.scp使用ssh安全协议传输数据,具有和ssh一样的验证机制,从而安全的远...

老孟的Linux私房菜
58分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部