Java二叉树递归算法，初学者入门收藏

Java算法：递归二叉树算法

二叉树的本质是递归结构，很多可以使用递归分治法完成的，推广了遍历算法。

在只给定指向树的一个指针的前提下，经常需要找到树的各种结构参数的值。

例1：树参数的计算，树的结点树和高度

private static int count(Node h){   
    if(h == null){   
        reutrn 0;   
    }   
    return count(h.l) + count(h.r) + 1;   
}   
int count(){   
    return count(root);   
}   
private static int height(Node h){   
    if(h == null){   
        return -1;   
    }   
    int u = height(h.l), v = height(h.r);   
    if(u > v){   
        return u + 1;   
    }else{   
        return v + 1;   
    }   
}   
int height(){   
    return height(root);   
}

例2：快速的输出树方法

static void printNode(Item x, int h){   
    for(int i = 0; i < h; i++){   
        System.out.println("   ");   
    }   
    System.out.println("[" + x + "]");   
}   
private static void showR(Node t, int h){   
    if(t == null){   
        printNode(null, h);   
        return;   
    }   
    showR(t.r, h + 1);   
    printNode(t.item, h);   
    showR(t.l, h + 1);   
}   
void show(){   
    showR(root, 0);   
}

例3：竞标赛树的构建（分支递归策略）

static class Node{   
    double val;   
    Node l;   
    Node r;   
    Node(double v, Node l, Node r){   
        this.val = v;   
        this.l = l;   
        this.r = r;   
    }   
}   
static Node max(double a[], int l, int r){   
    int m = (l + r)/2;   
    Node x = new Node(a[m], null, null);   
    if(l == r){   
        return x;   
    }   
    x.l = max(a, l, m);   
    x.r = max(a, m + 1, r);   
    double u = x.l.val, v = x.r.val;   
    if(u > v){   
        x.val = u;   
    }else{   
        x.val = v;   
    }   
    return x;   
}

在某些情况下，构建递归数据结构可能要比通过扫描数据找到最大值好。

使二叉树构建前缀表达式。

例4：解析树的构建

static Node parse(){   
    char t = a[i++];   
    Node x = new Node(t);   
    if((t == '+') || (t == '*')){   
        x.l = parse();   
        x.r = parse();   
    }   
    return x;   
}

以上就是极悦java培训机构的小编针对“Java二叉树递归算法，初学者入门收藏”的内容进行的回答，希望对大家有所帮助，如有疑问，请在线咨询，有专业老师随时为你服务。