《数据结构与算法分析》第四章--树 （1）

4.1 预备知识

定义：

　　树的递归定义：一棵树是一些节点的集合，这个集合若为空集；否则由一个根结点以及该节点的0个或者若干个非空子树组成，这些子树都与该根节点有边连接。

　　树叶：没有子节点的节点。

　　兄弟（Siblings）：有相同父亲节点的节点。

　　节点n1到nj的路径：一个节点 序列：n1，n2...，nj。

　　路径的长：路径上的边数。

　　节点ni的深度：根节点到ni的唯一路径的长。根节点深度为0。

　　节点ni的高度：该节点ni到叶子节点的最长路径。树的高：根节点的高度。

4.1.1 树的实现

左孩子右兄弟链表法：链表中增加两个附加元素一个记录其最左边的孩子，另一个记录其右边的兄弟。（树中子节点不分左右，这里为了存储方便）

//左孩子右兄弟节点表示
class TreeNode<E>
{
    E data;
    private TreeNode<E> firstChild;
    private TreeNode<E> nextSibling;
    public void set_firstChild(TreeNode<E> t){
        firstChild=t;
    }
    public TreeNode<E> get_firstChild(){
        return firstChild;
    }
    public void set_nextSiblling(TreeNode<E> t){
        nextSibling=t;
    }
    public TreeNode<E> get_nextSiblling(TreeNode<E> t){
        return nextSibling;
    }
    public TreeNode(TreeNode<E> firstChild,TreeNode<E> nextSibling){
        this.firstChild=firstChild;
        this.nextSibling=nextSibling;
    }
}

　　这里树上只给了节点的数据表示，没有给出树上的操作，这里我给该树ADT增加操作；

树ADT设计：

ADT Tree{
  数据对象Data：D是具有左孩子右兄弟和数据的相同类型数据元素集合；
  基本操作P：
      InitTree（TreeNode T）
            操作结果：构造空树T；
      CreateTree（TreeNode T，definition）
             初始条件：definition给出树T的定义；
             操作结果：按definition构造树
      TreeEmpty（）
             操作结果：返回是否为空；
      Add（TreeNode k，TreeNode x）
            初始条件：k是树中的一个节点；
            操作结果：x作为k的子节点被添加进去
      ShowPreOrder（）
           操作结果：输出树的结构；
      
}        

 树的遍历的简单应用：

　　先序遍历：采用递归的方法，在根节点对子树递归调用先序遍历方法；递归终止条件：输入节点为叶子节点，则打印并且停止；否则打印并递归向下；

class Tree<E>
{
    private static class TreeNode<E>
    {
        E data;
        TreeNode<E> firstchild;
        TreeNode<E> nextSibling;
        TreeNode(E d)
        {
            data=d;
            firstchild=null;
            nextSibling=null;
        }
    }
    private TreeNode<E> root=null;
    public TreeNode<E> getroot(){
        return root;
    }
    Tree()
    {
    }
    Tree(E root)
    {
        this.root=new TreeNode<E>(root);
    }
    public boolean treeEmpty()
    {
        return root==null;
    }
    public TreeNode<E> find(int d,int w)
    {
        if(d<0||w<0)
            throw new NullPointerException("d<0");
        if (d==0)
        {
            return root;
        }
        TreeNode<E> p=root;
        while(d!=0){
            p=p.firstchild;
            d--;
        }
        while(w!=0)
        {
            p=p.nextSibling;
            w--;
        }
        return p;
    }
    public boolean addChild(int d,int w,E x)
    {
        return addChild(find(d,w),new TreeNode<E>(x));
    }
    public boolean addChild(TreeNode<E> k,E x)
    {
        return addChild(k,new TreeNode<E>(x));
    }
    public boolean addChild(TreeNode<E> k,TreeNode<E> x)
    {
        if(k.firstchild==null)
        {
            k.firstchild=x;
            return true;
        }
        TreeNode<E> p=k.firstchild;
        while(p.nextSibling!=null)
        {
            p=p.nextSibling;
        }
        p.nextSibling = x;
        return true;
    }
    public void printPreOrder(int depth,TreeNode<E> r)
    {
        String nbsp="";
        for(int i=0;i<depth;i++){
            nbsp=nbsp+"   ";
        }
        System.out.println(nbsp+(String) r.data);
        TreeNode<E> q=r.firstchild;
        if(q!=null)
        {
            while(q.nextSibling!=null){
                printPreOrder(depth+1,q);
                q=q.nextSibling;
            }
            printPreOrder(depth+1,q);
        }
    }
}

效果图： 

后序遍历算法：算法思路：采用递归调用的方法，与先序遍历类似，只是打印放在递归调用后面；

    public void printPostOrder(int depth,TreeNode<E> r)
    {
        String nbsp="";
        for(int i=0;i<depth;i++){
            nbsp=nbsp+"   ";
        }
        TreeNode<E> q=r.firstchild;
        if(q!=null)
        {
            while(q.nextSibling!=null){
                printPostOrder(depth+1,q);
                q=q.nextSibling;
            }
            printPostOrder(depth+1,q);
        }
        System.out.println(nbsp+(String) r.data);
    }

运行效果图：