本文共 4420 字,大约阅读时间需要 14 分钟。
基于数组实现的结构允许我们通过下标或秩,在常数的时间内找到目标对象,并读取或更新其内容。然而,一旦需要对这类结构进行修改,那么无论是插入还是删除,都需要耗费线性的时间O(n)。
反过来,基于链表实现的结构允许我们借助引用或位置对象,在常数的时间内插入或删除元素O(1);但是为了找出居于特定次序的元素,我们不得不花费线性的时间对整个结构进行遍历查找。
树:可以结合两者的优点.
树中的元素也称作节点( Node);
在树结构中,在每个节点中除数据项外,还设有三个引用,分别指向该节点的父亲、长子和最大弟弟节点(若不存在,则为null)。
树抽象类型要支持以下的基本方法:
操作方法 | 功能描述 |
---|---|
getElement(): | 返回存放于当前节点处的对象输入:无输出:对象 |
setElement(e): | 将对象 e 存入当前节点,并返回其中此前所存的内容输入:一个对象输出:对象 |
getParent(): | 返回当前节点的父节点输入:无输出:树节点 |
getFirstChild(): | 返回当前节点的长子输入:无输出:树节点 |
getNextSibling(): | 返回当前节点的最大弟弟输入:无输出:树节点 |
不同问题要求更新操作不同后续给出更新操作的实现;
/** 树ADT接口*/public interface Tree { //返回当前节点中存放的对象 public Object getElem(); //将对象obj存入当前节点,并返回此前的内容 public Object setElem(Object obj); //返回当前节点的父节点 public TreeLinkedList getParent(); //返回当前节点的长子 public TreeLinkedList getFirstChild(); //返回当前节点的最大弟弟 public TreeLinkedList getNextSibling(); //返回当前节点后代元素的数目,即以当前节点为根的子树的规模 public int getSize(); //返回当前节点的高度 public int getHeight(); //返回当前节点的深度 public int getDepth();}
/** 基于链表实现树结构*/public class TreeLinkedList implements Tree { private Object element;//树根节点 private TreeLinkedList parent, firstChild, nextSibling;//父亲、长子及最大的弟弟 //(单节点树)构造方法 public TreeLinkedList() { this(null, null, null, null); } //构造方法 public TreeLinkedList(Object e, TreeLinkedList p, TreeLinkedList c, TreeLinkedList s) { element = e; parent = p; firstChild = c; nextSibling = s; } /*---------- Tree接口中各方法的实现 ----------*/ //返回当前节点中存放的对象 public Object getElem() { return element; } //将对象obj存入当前节点,并返回此前的内容 public Object setElem(Object obj) { Object bak = element; element = obj; return bak; } //返回当前节点的父节点;对于根节点,返回null public TreeLinkedList getParent() { return parent; } //返回当前节点的长子;若没有孩子,则返回null public TreeLinkedList getFirstChild() { return firstChild; } //返回当前节点的最大弟弟;若没有弟弟,则返回null public TreeLinkedList getNextSibling() { return nextSibling; } //返回当前节点后代元素的数目,即以当前节点为根的子树的规模 public int getSize() { int size = 1;//当前节点也是自己的后代 TreeLinkedList subtree = firstChild;//从长子开 while (null != subtree) { //依次 size += subtree.getSize();//累加 subtree = subtree.getNextSibling();//所有孩子的后代数目 } return size;//即可得到当前节点的后代总数 } //返回当前节点的高度 public int getHeight() { int height = -1; TreeLinkedList subtree = firstChild;//从长子开始 while (null != subtree) { //依次 height = Math.max(height, subtree.getHeight());//在所有孩子中取最大高度 subtree = subtree.getNextSibling(); } return height+1;//即可得到当前节点的高度 } //返回当前节点的深度 public int getDepth() { int depth = 0; TreeLinkedList p = parent;//从父亲开始 while (null != p) { //依次 depth++; p = p.getParent();//访问各个真祖先 } return depth;//真祖先的数目,即为当前节点的深度 }}
来源于:Java数据结构,邓俊辉