数据结构题目38：求二叉树的深度

题目：已知二叉树采用二叉链表存储结构，根结点所在链结点的地址为T，写一递归算法，求该二叉树的深度。

（一）递归算法
解题思路：若二叉树为空，则其深度为0；否则深度等于左子树与右子树最大深度值加1。

具体算法如下：

function BTDepth(BT) {
    let ldepth, rdepth
    if ( BT==null ) {
        return 0
    } else {
        ldepth = BTDepth(BT.lchild)
        rdepth = BTDepth(BT.rchild)
        if ( ldepth>rdepth ) {
            return ldepth+1
        } else {
            return rdepth+1
        }
    }
}

测试：
这里使用到建立二叉树方法createBT(strBT)

var strBT="A(B(D,E(G)),C(F(,H)))@"
var BT = createBT(strBT)
BTDepth(BT) 

（二）非递归算法
解题思路：遍历过程中依次记录各个结点所处的层次数以及当前已经访问过的结点所处的最大层次数。每当访问某个叶结点，将该叶结点所处的层次数与当前已获得的最大层次数进行比较，若前者大于后者，修改最大层次数为当前叶结点的层次数，否则最大层次数不做修改。遍历结束时，所记录的最大层次数即为该二叉树的深度。
下面利用中序遍历方法求二叉树的深度。设二叉树的深度由变量maxdepth给出，当前访问的结点所处的层次数由变量curdepth记录。算法中定义了两个顺序存储结构的堆栈stack1[0,..,M-1]与stack2[0,..,M-1]，它们共用一个栈顶指针top；栈中每个元素分别记录当前访问结点的存储地址以及该结点所处的层次数。

具体算法如下：

function depthBT(T) {
    var stack1=new Array(MaxSize), stack2=new Array(MaxSize), p=T
    var curdepth, maxdepth=0, top=-1
    if ( T!=null ) {
        curdepth = 1
        do {
            while ( p!=null ) {
                stack1[++top] = p
                stack2[top] = curdepth
                p = p.lchild
                curdepth++
            }
            p = stack1[top]
            curdepth = stack2[top--]
            if ( p.lchild==null && p.rchild==null ) {
                if ( curdepth>maxdepth ) {
                    maxdepth = curdepth
                }
            }
            p = p.rchild
            curdepth++
        } while ( !(p==null&&top==-1) );
    }
    return maxdepth
}