首页 > 代码库 > 树&二叉树

树&二叉树

(哈弗曼树、哈弗曼编码、排序二叉树、平衡二叉树、红黑树、3种遍历(先序,后序,中序)、深度-广度优先遍历)

关键词、语句:

  1. 树的三种存储结构:父节点表示法、子节点表示法、链表存储
  2. 树代表一种非线性的数据结构
  3. 如果一组数组节点之间存在复杂的一对多关联时,程序就可以考虑使用树来保存这组数据了
  4. 一对多?例如,一个父节点可以包含多个子节点
  5. TreeMap即利用红黑树实现

树:一个集合(里面存在N个有父子关系的节点,N有限,即有限集合)

满足条件(请背诵下来):

    a.  当N=0的时候,节点集合为空,称为"空树"

    b.  在任意的非空树中,有且仅有一个根节点

    c.  N>1时,除了根节点,其余节点可以分为M个互有关联的子集合,称为根的子树(subtree)(递归)

 

注意:根节点没有父节点,叶子节点没有子节点。(除了根节点,所有的节点有唯一的父节点)

 

图解:

技术分享

术语:(熟记)
   节点:包含数据域和指针(引用)域
   节点的度:节点的子树个数
   树的度:所有节点度的最大值
   叶子节点:度为0的节点
   分支节点:度不为0的节点
   兄弟节点:具有相同的父节点的节点
   节点的层:更的层次为1,其余节点依次加1
   树的深度:节点的最大层次
   有序树:树中个子树节点从左到右是有序的,不能交换(区分左右)
   祖先节点:从根到该节点所经分支上的所有节点
   后代节点:以某一节点为跟的子树中任一节点
   森林:2棵或者2棵以上互不相交的树的集合,删去一个树的根就得到一个森林
 
树的常用操作:
   1. 初始化: 指定构造器创建空树,或者,以指定节点为根创建树
   2. 为指定节点添加子节点
   3. 判断是否为空树
   4. 返回根节点
   5. 返回指定节点(非根)的父节点
   6. 返回指定节点(非叶子)的所有子节点
   7. 返回指定节点(非叶子)的第i个子节点
   8. 返回该树的深度(从节点数组里面的节点开始找其父类)
   9. 返回指定节点的位置
 
 

树的实现(即表现父子节点的关系)

父节点表示法:每个子节点都记录它的父节点(有点像数据库中的无限级分类)----孩子记父亲(孩子只有一个父亲,1个记1个)

子节点表示法:每个非叶子节点通过一个链表来记录它所有的子节点------父亲记孩子(父亲可以有多个孩子,1个记多个)

详细说明:

1. 父节点表示法:

a. 为每个几点都多增加一个parent域,用来保存父节点的引用或者索引编号

技术分享

数组索引

data

parent

0A-1
1B0
2C0
3D1

代码实现:

import java.util.ArrayList;import java.util.List;public class TreeParent<E> {    public static class Node<T>    {        T data;        int parent; //记录父节点                public Node(){}        public Node(T data)        {            this.data =http://www.mamicode.com/ data;                }        public Node(T data,int parent)        {            this.data =http://www.mamicode.com/ data;            this.parent = parent;        }                public String toString()        {            return "TreeParent--Node[data="http://www.mamicode.com/+data+", parent="+parent+"]";        }    }    private final int DEFAULT_TREE_SIZE = 100;    private int treeSize = 0;  //存放节点的数组的容量(树的容量)    private int nodeNums;  //当前节点数量        private Node[] nodes; //记录所有的节点    public TreeParent(E data) //以指定根节点创建树    {        treeSize = DEFAULT_TREE_SIZE;        nodes = new Node[treeSize];        nodes[0] = new Node<E>(data,-1);        nodeNums++; //当前节点数量增加    }    public TreeParent(E data,int treeSize)//指定树的容量    {        this.treeSize = treeSize;        nodes = new Node[treeSize];        nodes[0] = new Node<E>(data,-1);        nodeNums++; //当前节点数量增加    }    public void addNode(E data,Node parent)     //为指定节点添加子节点,注意传入的是Node,并且Node是static的    {        //先要判断一下树是否已满,数组中不存在为null的元素                for (int i = 0 ; i < treeSize ; i++)        {            if (nodes[i] == null)//找到数组中第一个为null的元素,该元素保存新节点            {                //创建新节点,并用指定的数组元素保存它                nodes[i] = new Node(data , pos(parent));//请注意这里实例化静态内部类                nodeNums++;                return;            }        }        throw new RuntimeException("该树已满,无法添加新节点");    }    private int pos(Node parent) //返回指定节点的索引    {        for (int i = 0 ; i < treeSize ; i++)        {            //找到指定节点            if (nodes[i] == parent)            {                return i;            }        }        return -1;    }    public boolean empty()//判断树是否为空。    {        return nodes[0] == null;//根节点是否为null    }    public Node<E> root()//返回根节点    {        return nodes[0];//返回根节点    }    public Node<E> parent(Node node)//返回指定节点(非根节点)的父节点    {        //每个节点的parent记录了其父节点的位置        return nodes[node.parent];    }    public List<Node<E>> children(Node parent)//返回指定节点(非叶子节点)的所有子节点    {        List<Node<E>> list = new ArrayList<Node<E>>();        for (int i = 0 ; i < treeSize  ; i++)        {            //如果当前节点的父节点的位置等于parent节点的位置            if (nodes[i] != null &&                nodes[i].parent == pos(parent))            {                list.add(nodes[i]);            }        }        return list;    }    public int deep()//返回该树的深度--从节点数组中的每一个节点开始向上不断找父节点,不断加1    {                int max = 0;//用于记录节点的最大深度        for(int i = 0 ; i < treeSize && nodes[i] != null; i++)        {            int def = 1; //初始化本节点的深度            int m = nodes[i].parent;//m记录当前节点的父节点的位置            while(m != -1 && nodes[m] != null)//如果其父节点存在            {                m = nodes[m].parent;//向上继续搜索父节点                def++;            }            if(max < def)            {                max = def;            }        }        return max; //返回最大深度    }    /*    public static void main(String[] args) {        TreeParent<String> tp = new TreeParent<String>("root");        TreeParent.Node root = tp.root();        System.out.println(root);        tp.addNode("节点1" , root);        System.out.println("此树的深度:" + tp.deep());        tp.addNode("节点2" , root);        //获取根节点的所有子节点        List<TreeParent.Node<String>> nodes = tp.children(root);        System.out.println("根节点的第一个子节点:" + nodes.get(0));        //为根节点的第一个子节点新增一个子节点        tp.addNode("节点3" , nodes.get(0));        System.out.println("此树的深度:" + tp.deep());    }*/}

特别注意:

    1. 求深度的时候,是从子节点开始向上一步一步找。

          但是要遍历数组中每一个节点,在找以前出现过的节点时,可能已经找过后面的节点了,后面又找了一遍,重复。

     2. public static class Node<T> 这里出现了“静态内部类”,以及做了其实例化操作(添加节点的时候)

补充知识:static class 静态类的实例化    

http://www.2cto.com/kf/201304/206692.html

http://kenby.iteye.com/blog/1603803

我在本博客的另外一篇文章中对上述连接做了整理: 内部类大总结

 


未完待续//

树&二叉树