数据结构笔记--树

Scroll Down

数据结构学习笔记---树

树的基本概念

树的基本术语

  1. 度:一个节点拥有子树的数量
  2. 高度/深度:约定根节点的高度为3,每增加一层高度加1
  3. 二叉树的直径:根到叶子节点的一条最长路径,路径长度是树的高度减1
  4. 森林:m棵互不相交树的集合

树的抽象数据类型

ADT Tree<T>
{
    boolean isEmpty()       //判断是否为空树
    int level(T key)        //判断key节点的层次
    int size()              //返回树的节点数
    int height()            //返回树的高度
    void preorder()         //树的前序遍历
    void postorder()        //树的后序遍历
    void levelorder()       //树的中序遍历
}

二叉树

顾名思义,每个节点都有两个孩子的树

二叉树的一些特殊性质

  1. 如果根结点的层次为1,第n层有2^(n-1)个结点
  2. 在高度为h二叉树中,最多有2^h-1个结点,此时为满二叉树
  3. 在一棵叶子结点数为n0的树中,2度结点数为n2,则n0=n2+1
  4. 一个具有n个结点的完全二叉树,高度为log2n+1
  5. 一棵有n个结点的完全二叉树,对于序号为i的结点有:
    1. i=0,i为根结点
    2. 2i+1为其左孩子
    3. 2i+2为其右孩子

二叉树的遍历

二叉树的前序遍历

顺序,根左右

public void preorder(BinaryNode<T> p)
{
    if(p==null)
        return;
    System.out.print(p.data);
    preorder(p.left);
    preorder(p.right);
}

二叉树的中根遍历序列

顺序,左根右

public void inorder(BinaryNode<T> p)
{
    if(p==null)
        return;
    preorder(p.left);
    System.out.print(p.data);
    preorder(p.right);
}

这里的打印顺序就是遍历的顺序,可以看出中根遍历到某个结点后,不会马上去读取该结点的值,而是去继续遍历其左孩子

二叉树的后序遍历

顺序,左右根

public void postorder(BinaryNode<T> p)
{
    if(p==null)
        return;
    preorder(p.left);
    preorder(p.right);
    System.out.print(p.data);
}

二叉树的构造

由一个标明空子树的先根序列构造

/**
 *  preList  标明空子树的前序遍历序列
 *  i 记录preList的位置
 *  p 当前结点的引用
 *  递归算法
 */
public int createTree(T[] preList, int i, BinaryNode<T> p)
{
     if (i>=preList.length)
            return i;
        if(i<preList.length&&preList[i]!=null)           //如果不为空,创建左结点
        {
            p.left = new BinaryNode<T>(preList[i]);
            i= createTree(preList, ++i, p.left);         //递归构造左子树
        }else
            i++;                                         //查看下一个点
        if(i<preList.length&&preList[i]!=null)           //第二次查看是否满足创建条件,如果满足,创建右结点
        {
            p.right = new BinaryNode<T>(preList[i]);     
            i = createTree(preList, ++i, p.right);       //递归构造右子树
        }
        else
            return ++i;
        return i;
}

由二叉树的两个遍历序列构造二叉树

只由一个遍历序列不能构造一个二叉树,构造二叉树需要子节点和父母结点的位置关系,而单一遍历序列中并不能得到。
两个遍历序列可以构造二叉树,前序
遍历和后续遍历除外

前序遍历序列和中序遍历序列

前序遍历和中序遍历可以唯一确定一棵二叉树
假设有这样一棵二叉树,其标明空结点的前序遍历序列为:

a, b, d, ^, g, ^, ^, ^, c, e, ^, ^, f, h, ^, ^ ,^

其前序遍历序列为:

prelist = [a, b, d, g, c, r, f, h]

其中序遍历序列为:

inlist = [d, g, b, a, e, c, h, f ]

我们可以发现,其根节点为prelist[0]inlist[3]
那么inlist[3]前面的结点,属于其左子树,后面的属于其右子树,preList[0]后面len个结点属于左子树,len后面的部分直到未属于右子树。

C477CBB7103D3B958D7133A3E6925200.png

因此我们把问题分解,我们可以让其左子树序列看作一个独立的问题,例如:
E8B7840384D4260EB1D56FA2FC4E4C0F.png
第二次我们可以通过寻找preorder[0]inorder中的位置来确定其左子树和右子树的位置,那么在本例中inorder中的binorder的末尾,所以其不存在右子树,但其左边都是其左子树,所以preorder的0索引后面两个节点是属于其左子树的,而这两个节点后面直到结尾是属于其右子树的。
在代码实际编写中,我们可以通过其左子树的长度来确定preorder中左子树的位置
再依次递归下去,便能建立二叉树

/**
 *  preList 前序遍历序列
 *  inlist  中序遍历序列
 *  s       先根序列的开始索引
 *  e       先根序列的结束索引
 *  start   中根序列的开始索引
 *  end     中根序列的结束索引加1
 */
    public BinaryNode<T> createTree(T[] preList, T[] inlist, int s, int e, int start, int end)
    {
        BinaryNode<T> p = null;
        if(start>end || s>e)        //递归的终止条件
            return null;
        T temp = preList[s];
        boolean flag = false;       
        int j = -1;
        //寻找结点
        for(j=start;j<inlist.length;j++)
            if(temp.equals(inlist[j])){
                flag=true;
                break;
            }
        if(!flag)       //没找到就返回
            return null;
        p = new BinaryNode(temp);
        int len = j - start;        //通过inorder算出左子树的长度
        //左子树,先根序列的开始为上一次开始的下一个,结束为上一个节点加上左子树的长度
        p.left = createTree(preList, inlist, s+1,s+len , start, j-1);
        //右子树的先根序列开始是左子树的结束加1,结束为末尾
        p.right = createTree(preList, inlist, s+len+1, e, j+1, end);
        return p;
    }
中序遍历序列和后续遍历序列

后续遍历序列的特点是:其根总是在其末尾
例如,后根遍历序列为:

postlist = [g, d, b, e, h, f, c, a]

中根遍历序列为:

inlist = [d, g, b, a, e, c, h, f ]

一样通过寻找postlist[postlist.length-1]inlist中的位置,来判断子树的位置。
DA0E599AE5404892D1F6B54E7EE074F1.png
在后根序列中,前n个为其左子树序列
我们可以这样判断其位置

/**
 *  postList 后序遍历序列
 *  inlist  中序遍历序列
 *  s       后根序列的开始索引
 *  e       后根序列的结束索引
 *  start   中根序列的开始索引
 *  end     中根序列的结束索引加1
 */
    public BinaryNode<T> create(T[] postList, T[] inlist, int s, int e, int start, int end)
    {
        BinaryNode<T> p = null;
        if(start>end || s>e)        //递归的终止条件
            return null;
        T temp = postList[e];
        boolean flag = false;
        int j = -1;
        //寻找结点
        for(j=start;j<inlist.length;j++)
            if(temp.equals(inlist[j])){
                flag=true;
                break;
            }
        if(!flag)       //没找到就返回
            return null;
        p = new BinaryNode(temp);
        int len = j - start;
        p.left = create(postList, inlist, s,s+len-1 , start, j-1);
        p.right = create(postList, inlist, s+len, e-1, j+1, end);
        return p;
    }