企业网站建设应避免数据孤岛,建设个人网站的策划书,媒体资源网官网,天津单位网站建设前面讲到的顺序表、栈和队列都是一对一的线性结构#xff0c;这节讲一对多的线性结构——树。「一对多」就是指一个元素只能有一个前驱#xff0c;但可以有多个后继。
一、基本概念
树#xff08;tree#xff09;是n#xff08;n0#xff09;个结点的有穷集。n0时称…前面讲到的顺序表、栈和队列都是一对一的线性结构这节讲一对多的线性结构——树。「一对多」就是指一个元素只能有一个前驱但可以有多个后继。
一、基本概念
树tree是nn0个结点的有穷集。n0时称为空树。在任意一个非空树中1每个元素称为结点node2仅有一个特定的结点被称为根结点或树根root。3当n1时其余结点可分为mm≥0个互不相交的集合T1T2……Tm其中每一个集合Ti1im本身也是一棵树被称作根的子树subtree。
注意
n0时根节点是唯一的。m0时子树的个数没有限制但它们一定是互不相交的。
结点拥有的子树数被称为结点的度Degree。度为0的结点称为叶节点Leaf或终端结点度不为0的结点称为分支结点。除根结点外分支结点也被称为内部结点。结点的子树的根称为该结点的孩子Child该结点称为孩子的双亲或父结点。同一个双亲的孩子之间互称为兄弟。树的度是树中各个结点度的最大值。
结点的层次Level从根开始定义起根为第一层根的孩子为第二层。双亲在同一层的结点互为堂兄弟。树中结点的最大层次称为树的深度Depth或高度。如果将树中结点的各个子树看成从左到右是有次序的不能互换的则称该树为有序树否则称为无序树。森林是mm0棵互不相交的树的集合。
树的定义 二、树的存储结构
由于树中每个结点的孩子可以有多个所以简单的顺序存储结构无法满足树的实现要求。下面介绍三种常用的表示树的方法双亲表示法、孩子表示法和孩子兄弟表示法。
1、双亲表示法
由于树中每个结点都仅有一个双亲结点根节点没有我们可以使用指向双亲结点的指针来表示树中结点的关系。这种表示法有点类似于前面介绍的静态链表的表示方法。具体做法是以一组连续空间存储树的结点同时在每个结点中设一个「游标」指向其双亲结点在数组中的位置。代码如下
public class PTreeE {private static final int DEFAULT_CAPACITY 100;private int size;private Node[] nodes;private class Node() {E data;int parent;Node(E data, int parent) {this.data data;this.parent parent;}}public PTree() {nodes new PTree.Node[DEFAULT_CAPACITY];}
}由于根结点没有双亲结点我们约定根节点的parent域值为-1。树的双亲表示法如下所示 这样的存储结构我们可以根据结点的parent域在O(1)的时间找到其双亲结点但是只能通过遍历整棵树才能找到它的孩子结点。一种解决办法是在结点结构中增加其孩子结点的域但若结点的孩子结点很多结点结构将会变的很复杂。
2、孩子表示法
由于树中每个结点可能有多个孩子可以考虑用多重链表即每个结点有多个指针域每个指针指向一个孩子结点我们把这种方法叫多重链表表示法。它有两种设计方案
方案一指针域的个数等于树的度。其结点结构可以表示为
class Node() {E data;Node child1;Node child2;...Node childn;
}对于上一节中的树树的度为3其实现为 显然当树中各结点的度相差很大时这种方法对空间有很大的浪费。
方案二每个结点指针域的个数等于该结点的度取一个位置来存储结点指针的个数。其结点结构可以表示为
class Node() {E data;int degree;Node[] nodes;Node(int degree) {this.degree degree;nodes new Node[degree];}
}对于上一节中的树这种方法的实现为
这种方法克服了浪费空间的缺点但由于各结点结构不同在运算上会带来时间上的损耗。
为了减少空指针的浪费同时又使结点相同。我们可以将顺序存储结构和链式存储结构相结合。具体做法是把每个结点的孩子结点以单链表的形式链接起来若是叶子结点则此单链表为空。然后将所有链表存放进一个一维数组中。这种表示方法被称为孩子表示法。其结构为 代码表示
public class CTreeE {private static final int DEFAULT_CAPACITY 100;private int size;private Node[] nodes;private class Node() {E data;ChildNode firstChild;}//链表结点private class ChildNode() {int cur; //存放结点在nodes数组中的下标ChildNode next;}public CTree() {nodes new CTree.Node[DEFAULT_CAPACITY];}
}这种结构对于查找某个结点的孩子结点比较容易但若想要查找它的双亲或兄弟则需要遍历整棵树比较麻烦。可以将双亲表示法和孩子表示法相结合这种方法被称为双亲孩子表示法。其结构如下 其代码和孩子表示法的基本相同只需在Node结点中增加parent域即可。
3、孩子兄弟表示法
任意一棵树它的结点的第一个孩子如果存在则是唯一的它的右兄弟如果存在也是唯一的。因此我们可以使用两个分别指向该结点的第一个孩子和右兄弟的指针来表示一颗树。其结点结构为
class Node() {E data;Node firstChild;Node rightSib;
}其结构如下 这个方法可以方便的查找到某个结点的孩子只需先通过firstChild找到它的第一个孩子然后通过rightSib找到它的第二个孩子接着一直下去直到找到想要的孩子。若要查找某个结点的双亲和左兄弟使用这个方法则比较麻烦。
这个方法最大的好处是将一颗复杂的树变成了一颗二叉树。这样就可以使用二叉树的一些特性和算法了。
三、二叉树
1、基本概念
二叉树Binary Tree是每个节点最多有两个子树的树结构。通常子树被称作“左子树”left subtree和“右子树”right subtree。
二叉树的特点
二叉树不存在度大于2的结点。 二叉树的子树有左右之分次序不能颠倒。 如下图中树1和树2是同一棵树但它们是不同的二叉树。 1、斜树
所有的结点都只有左子树的二叉树叫左斜树。所有的结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。
斜树每一层只有一个结点结点的个数与二叉树的深度相同。其实斜树就是线性表结构。
2、满二叉树
在一棵二叉树中如果所有分支结点都存在左子树和右子树并且所有叶子都在同一层上这样的二叉树称为满二叉树。
满二叉树具有如下特点
叶子只能出现在最下一层非叶子结点的度一定是2同样深度的二叉树中满二叉树的结点个数最多叶子数最多。
3、完全二叉树
若设二叉树的高度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第h层有叶子结点并且叶子结点都是从左到右依次排布这就是完全二叉树。
完全二叉树的特点
叶子结点只能出现在最下两层最下层叶子在左部并且连续同样结点数的二叉树完全二叉树的深度最小
4、平衡二叉树
平衡二叉树又被称为AVL树区别于AVL算法它是一棵二叉排序树且具有以下性质它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树
2、二叉树的性质
在二叉树的第i层上至多有2^i-1个结点i1。
深度为k的二叉树至多有2^k-1个结点k1。
对任何一棵二叉树T如果其终端结点个数为n0度为2的结点数为n2则n0 n2 1。
具有n个结点的完全二叉树的深度为「log2n」 1「x」表示不大于x的最大整数。
如果对一棵有n个结点的完全二叉树的结点按层序编号从第一层到第「log2n」 1层每层从左到右对任一结点i1≤i≤n有
若i1则结点i是二叉树的根无双亲如i1则其双亲是结点「i/2」。 如2in则结点i无左孩子结点i为叶子结点否则其左孩子是结点2i。 若2i1n则结点i无右孩子否则其右孩子是结点2i1。
3、二叉树的实现
二叉树是一种特殊的树它的存储结构相对于前面谈到的一般树的存储结构要简单一些。
1、顺序存储
二叉树的顺序存储结构就是用一维数组来存储二叉树中的结点。不使用数组的第一个位置。结点的存储位置反映了它们之间的逻辑关系位置k的结点的双亲结点的位置为「k/2」它的两个孩子结点的位置分别为2k和2k1。 代码实现
public class ArrayBinaryTreeE {private static final int DEFAULT_DEPTH 5;private int size 0;private E[] datas;ArrayBinaryTree() {this(DEFAULT_DEPTH);}SuppressWarnings(unchecked)ArrayBinaryTree(int depth) {datas (E[]) new Object[(int)Math.pow(2, depth)];}public boolean isEmpty() { return size 0; }public int size(){ return size; }public E getRoot() { return datas[1]; }// 返回指定节点的父节点 public E getParent(int index) { checkIndex(index); if (index 1) { throw new RuntimeException(根节点不存在父节点); } return datas[index/2]; } //获取右子节点 public E getRight(int index){ checkIndex(index*2 1); return datas[index * 2 1]; } //获取左子节点 public E getLeft(int index){ checkIndex(index*2); return datas[index * 2]; } //返回指定数据的位置 public int indexOf(E data){ if(datanull){ throw new NullPointerException(); } else { for(int i0;idatas.length;i) { if(data.equals(datas[i])) { return i; } } } return -1; }//顺序添加元素public void add(E element) {checkIndex(size 1);datas[size 1] element;size;}//在指定位置添加元素public void add(E element, int parent, boolean isLeft) {if(datas[parent] null) { throw new RuntimeException(index[parent] is not Exist!); } if(element null) { throw new NullPointerException(); } if(isLeft) {checkIndex(2*parent);if(datas[parent*2] ! null) { throw new RuntimeException(index[parent*2] is Exist!); }datas[2*parent] element;}else {checkIndex(2*parent 1);if(datas[(parent1)*2]!null) { throw new RuntimeException(index[ parent*21 ] is Exist!); } datas[2*parent 1] element;}size;}//检查下标是否越界private void checkIndex(int index) { if(index 0 || index datas.length) { throw new IndexOutOfBoundsException(); } } public static void main(String[] args) {char[] data {A,B,C,D,E,F,G,H,I,J};ArrayBinaryTreeCharacter abt new ArrayBinaryTree();for(int i0; idata.length; i) {abt.add(data[i]);}System.out.print(abt.getParent(abt.indexOf(J)));}
}一棵深度为k的右斜树只有k个结点但却需要分配2k-1个顺序存储空间。所以顺序存储结构一般只用于完全二叉树。
2、链式存储
二叉树每个结点最多有两个孩子所以为它设计一个数据域和两个指针域即可。我们称这样的链表为二叉链表。其结构如下图 代码如下
import java.util.*;
public class LinkedBinaryTreeE { private ListNode nodeList null; private class Node { Node leftChild; Node rightChild; E data; Node(E data) { this.data data; } } public Node getRoot() {return nodeList.get(0);}public void createBinTree(E[] array) { nodeList new LinkedListNode(); for (int i 0; i array.length; i) { nodeList.add(new Node(array[i])); } // 对前lasti-1个父节点按照父节点与孩子节点的数字关系建立二叉树 for (int i 0; i array.length / 2 - 1; i) { nodeList.get(i).leftChild nodeList.get(i * 2 1); nodeList.get(i).rightChild nodeList.get(i * 2 2); } // 最后一个父节点:因为最后一个父节点可能没有右孩子所以单独拿出来处理 int lastParent array.length / 2 - 1; nodeList.get(lastParent).leftChild nodeList .get(lastParent * 2 1); // 右孩子,如果数组的长度为奇数才建立右孩子 if (array.length % 2 1) { nodeList.get(lastParent).rightChild nodeList.get(lastParent * 2 2); } } public static void main(String[] args) {Character[] data {A,B,C,D,E,F,G,H,I,J};LinkedBinaryTreeCharacter ldt new LinkedBinaryTree();ldt.createBinTree(data);}
}4、二叉树的遍历
二叉树的遍历traversing binary tree是指从根结点出发按照某种次序依次访问二叉树中所有结点使得每个结点被访问一次且仅被访问一次。
二叉树的遍历主要有四种前序遍历、中序遍历、后序遍历和层序遍历。
1、前序遍历
先访问根结点然后遍历左子树最后遍历右子树。
代码
//顺序存储
public void preOrderTraverse(int index) { if (datas[index] null) return; System.out.print(datas[index] ); preOrderTraverse(index*2); preOrderTraverse(index*21);
} //链式存储public void preOrderTraverse(Node node) { if (node null) return; System.out.print(node.data ); preOrderTraverse(node.leftChild); preOrderTraverse(node.rightChild);
} 2、中序遍历
先遍历左子树然后遍历根结点最后遍历右子树。
//链式存储public void inOrderTraverse(Node node) { if (node null) return; inOrderTraverse(node.leftChild);System.out.print(node.data ); inOrderTraverse(node.rightChild);
} 3、后序遍历
先遍历左子树然后遍历右子树最后遍历根结点。
//链式存储public void postOrderTraverse(Node node) { if (node null) return; postOrderTraverse(node.leftChild);postOrderTraverse(node.rightChild); System.out.print(node.data );
} 4、层序遍历
从上到下逐层遍历在同一层中按从左到右的顺序遍历。如上一节中的二叉树层序遍历的结果为ABCDEFGHIJ。
注意
已知前序遍历和中序遍历可以唯一确定一棵二叉树。已知后序遍历和中序遍历可以唯一确定一棵二叉树。已知前序遍历和后序遍历不能确定一棵二叉树。
如前序遍历是ABC后序遍历是CBA的二叉树有 四、线索二叉树
对于n个结点的二叉树在二叉链存储结构中有n1个空指针域利用这些空指针域存放在某种遍历次序下该结点的前驱结点和后继结点的指针这些指针被称为线索加上线索的二叉树称为线索二叉树。
结点结构如下 其中
lTag为0时lChild指向该结点的左孩子为1时指向该结点的前驱 rTag为0时rChild指向该结点的右孩子为1时指向该结点的后继。 线索二叉树的结构图为图中蓝色虚线为前驱红色虚线为后继
代码如下
public class ThreadedBinaryTreeE {private TBTreeNode root;private int size; // 大小 private TBTreeNode pre; // 线索化的时候保存前驱 class TBTreeNode {E element;boolean lTag; //false表示指向孩子结点true表示指向前驱或后继的线索boolean rTag;TBTreeNode lChild;TBTreeNode rChild;public TBTreeNode(E element) {this.element element;}}public ThreadedBinaryTree(E[] data) {this.pre null; this.size data.length; this.root createTBTree(data, 1);}//构建二叉树public TBTreeNode createTBTree(E[] data, int index) { if (index data.length){ return null; } TBTreeNode node new TBTreeNode(data[index - 1]); TBTreeNode left createTBTree(data, 2 * index); TBTreeNode right createTBTree(data, 2 * index 1); node.lChild left; node.rChild right; return node; } /** * 将二叉树线索化 */ public void inThreading(TBTreeNode node) { if (node ! null) { inThreading(node.lChild); // 线索化左孩子 if (node.lChild null) { // 左孩子为空 node.lTag true; // 将左孩子设置为线索 node.lChild pre; } if (pre ! null pre.rChild null) { // 右孩子为空 pre.rTag true; pre.rChild node; } pre node; inThreading(node.rChild); // 线索化右孩子 } } /** * 中序遍历线索二叉树 */ public void inOrderTraverseWithThread(TBTreeNode node) {while(node ! null) {while(!node.lTag) { //找到中序遍历的第一个结点node node.lChild;}System.out.print(node.element ); while(node.rTag node.rChild ! null) { //若rTag为true则打印后继结点node node.rChild;System.out.print(node.element ); }node node.rChild;}} /** * 中序遍历线索化后不能使用*/ public void inOrderTraverse(TBTreeNode node) { if(node null)return;inOrderTraverse(node.lChild); System.out.print(node.element ); inOrderTraverse(node.rChild); } public TBTreeNode getRoot() { return root;}public static void main(String[] args) {Character[] data {A,B,C,D,E,F,G,H,I,J};ThreadedBinaryTreeCharacter tbt new ThreadedBinaryTree(data);tbt.inOrderTraverse(tbt.getRoot());System.out.println();tbt.inThreading(tbt.getRoot());tbt.inOrderTraverseWithThread(tbt.getRoot());}
}线索二叉树充分利用了空指针域的空间提高了遍历二叉树的效率。
五、总结
到此树的知识基本总结完了这一节开头讲了树的一些基本概念重点介绍了树的三种不同的存储方法双亲表示法、孩子表示法和孩子兄弟表示法。由兄弟表示法引入了一种特殊的树二叉树并详细介绍了它的性质、不同结构的实现方法和遍历方法。最后介绍了线索二叉树的实现方法。
