二叉树深度优先 求二叉树最大深度

深度优先遍历:对每一个可能的分支路径深入到不能再深入为止,而且每个结点只能访问一次。要特别注意的是,二叉树的深度优先遍历比较特殊,可以细分为先序遍历、中序遍历、后序遍历。

二叉树的遍历(traversing binary tree)是指从根节点触发,按照某种次序依次访问二叉树中的所有结点,使得每个结点都被访问一次且仅被访问一次。

二叉树最大深度:

如果二叉树为空,则深度为0 
如果不为空,分别求左子树的深度和右子树的深度,取最大的再加1。

var maxDepth = function(root) {
    if (!root) {
        return 0
    }
    return (1+Math.max(maxDepth(root.left), maxDepth(root.right)))
};

 

1 先(前)序遍历

若二叉树为空,则空操作返回;否则

(1)访问根节点;

(2)先序遍历左子树;

(3)先序遍历右子树。

图片 1

void PreOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 先序递归遍历二叉树T */
   if(T)
   {
     Visit(T); /* 先访问根结点 */
     PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
     PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
   }
 }

2 中序遍历

若二叉树为空,则空操作返回;否则

(1)中序遍历左子树;

(2)访问根节点;

(3)中序遍历右子树。

图片 2

void InOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 中序递归遍历二叉树T */
   if(T)
   {
     InOrderTraverse(T->lchild,Visit); /* 中序遍历左子树 */
     Visit(T); /* 再访问根节点 */
     InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */
   }
 }

3. 后序遍历

若二叉树为空,则空操作返回;否则

(1)后序遍历左子树;

(2)后序遍历右子树;

(3)访问根节点。

图片 3

void PostOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 后序递归遍历二叉树T */
   if(T)
   {
     PostOrderTraverse(T->lchild,Visit); /* 后序遍历左子树 */
     PostOrderTraverse(T->rchild,Visit); /* 后序遍历右子树 */
     Visit(T); /* 最后访问根节点 */
   }
 }

4. 层序遍历

本文由金沙官网线上发布于Web前端,转载请注明出处:二叉树深度优先 求二叉树最大深度

您可能还会对下面的文章感兴趣: