您的位置:时时app平台注册网站 > web前端 > 二叉树深度优先 求二叉树最大深度【彩世界网址

二叉树深度优先 求二叉树最大深度【彩世界网址

2019-11-03 04:38

纵深优先遍历:对每叁个大概的道岔路线深切到无法再深远截至,并且种种结点只可以访谈一遍。要非常注意的是,二叉树的深度优先遍历比较奇特,能够细分为先序遍历、中序遍历、后序遍历。

彩世界网址 1

14、决断二叉树是或不是一心二叉树

若设二叉树的深浅为h,除第 h 层外,其余各层 (1~h-1) 的结点数都达到最大个数,第 h 层全数的结点都三番三遍聚集在最左侧,那就是全然 
二叉树。 
宛如下算法,按档案的次序(从上到下,从左到右卡塔 尔(阿拉伯语:قطر‎遍历二叉树,当境遇叁个节点的左子树为空时,则该节点右子树必需为空,且后边遍历的节点左 
右子树都不得不为空,不然不是一丝一毫二叉树。

bool IsCompleteBinaryTree(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return false;
    queue<BinaryTreeNode *> q;
    q.push(pRoot);
    bool mustHaveNoChild = false;
    bool result = true;
    while(!q.empty())
    {
        BinaryTreeNode * pNode = q.front();
        q.pop();
        if(mustHaveNoChild) // 已经出现了有空子树的节点了,后面出现的必须为叶节点(左右子树都为空)
        {
            if(pNode->m_pLeft != NULL || pNode->m_pRight != NULL)
            {
                result = false;
                break;
            }
        }
        else
        {
            if(pNode->m_pLeft != NULL && pNode->m_pRight != NULL)
            {
                q.push(pNode->m_pLeft);
                q.push(pNode->m_pRight);
            }
            else if(pNode->m_pLeft != NULL && pNode->m_pRight == NULL)
            {
                mustHaveNoChild = true;
                q.push(pNode->m_pLeft);
            }
            else if(pNode->m_pLeft == NULL && pNode->m_pRight != NULL)
            {
                result = false;
                break;
            }
            else
            {
                mustHaveNoChild = true;
            }
        }
    }
    return result;
}

 

二叉树最大深度:

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

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

 

Reference:

7、求二叉树中叶子节点的个数

递归解法: 
(1卡塔尔假若二叉树为空,重回0 
(2卡塔 尔(阿拉伯语:قطر‎假使二叉树不为空且左右子树为空,再次回到1 
(3卡塔 尔(英语:State of Qatar)如若二叉树不为空,且左右子树区别一时候为空,再次回到左子树中叶子节点个数加上右子树中叶子节点个数 
参考代码如下:

int GetLeafNodeNum(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return 0;
    if(pRoot->m_pLeft == NULL && pRoot->m_pRight == NULL)
        return 1;
    int numLeft = GetLeafNodeNum(pRoot->m_pLeft); // 左子树中叶节点的个数
    int numRight = GetLeafNodeNum(pRoot->m_pRight); // 右子树中叶节点的个数
    return (numLeft   numRight);
}

 

1、求二叉树中的节点个数

递归解法: 
(1卡塔 尔(英语:State of Qatar)就算二叉树为空,节点个数为0 
(2卡塔 尔(阿拉伯语:قطر‎假若二叉树不为空,二叉树节点个数 = 左子树节点个数 右子树节点个数 1 
参考代码如下:

int GetNodeNum(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL) // 递归出口
        return 0;
    return GetNodeNum(pRoot->m_pLeft)   GetNodeNum(pRoot->m_pRight)   1;
}

(2卡塔 尔(英语:State of Qatar)访谈根节点;

二叉树面试题

4. 层序遍历

5、将二叉查找树变为有序的双向链表

务求不可能创建新节点,只调治指针。 
递归解法: 
(1卡塔 尔(英语:State of Qatar)即使二叉树查找树为空,无需转移,对应双向链表的第一个节点是NULL,最终叁个节点是NULL 
(2卡塔尔国借使二叉查找树不为空: 
如果左子树为空,对应双向有序链表的首先个节点是根节点,侧面无需其它操作; 
若果左子树不为空,调换左子树,二叉查找树对应双向有序链表的率先个节点便是左子树调换后双向有序链表的第三个节点,同不时间将根节点和左子树调换后的双向有序链 表的结尾二个节点连接; 
要是右子树为空,对应双向有序链表的末尾一个节点是根节点,左边无需任何操作; 
若果右子树不为空,对应双向有序链表的末段叁个节点就是右子树转变后双向有序链表的末尾叁个节点,相同的时候将根节点和右子树调换后的双向有序链表的率先个节点连 接。 
参照他事他说加以调查代码如下:

/******************************************************************************
参数:
pRoot: 二叉查找树根节点指针
pFirstNode: 转换后双向有序链表的第一个节点指针
pLastNode: 转换后双向有序链表的最后一个节点指针
******************************************************************************/
void Convert(BinaryTreeNode * pRoot, 
             BinaryTreeNode * & pFirstNode, BinaryTreeNode * & pLastNode)
{
    BinaryTreeNode *pFirstLeft, *pLastLeft, * pFirstRight, *pLastRight;
    if(pRoot == NULL) 
    {
        pFirstNode = NULL;
        pLastNode = NULL;
        return;
    }

    if(pRoot->m_pLeft == NULL)
    {
        // 如果左子树为空,对应双向有序链表的第一个节点是根节点
        pFirstNode = pRoot;
    }
    else
    {
        Convert(pRoot->m_pLeft, pFirstLeft, pLastLeft);
        // 二叉查找树对应双向有序链表的第一个节点就是左子树转换后双向有序链表的第一个节点
        pFirstNode = pFirstLeft;
        // 将根节点和左子树转换后的双向有序链表的最后一个节点连接
        pRoot->m_pLeft = pLastLeft;
        pLastLeft->m_pRight = pRoot;
    }

    if(pRoot->m_pRight == NULL)
    {
        // 对应双向有序链表的最后一个节点是根节点
        pLastNode = pRoot;
    }
    else
    {
        Convert(pRoot->m_pRight, pFirstRight, pLastRight);
        // 对应双向有序链表的最后一个节点就是右子树转换后双向有序链表的最后一个节点
        pLastNode = pLastRight;
        // 将根节点和右子树转换后的双向有序链表的第一个节点连接
        pRoot->m_pRight = pFirstRight;
        pFirstRight->m_pLeft = pRoot;
    }

    return;
}

[4] wikipedia(广度优先搜索):

2、求二叉树的深浅

递归解法: 
(1卡塔 尔(阿拉伯语:قطر‎如若二叉树为空,二叉树的深度为0 
(2卡塔尔若是二叉树不为空,二叉树的纵深 = max(左子树深度, 右子树深度) 1 
参照代码如下:

int GetDepth(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL) // 递归出口
        return 0;
    int depthLeft = GetDepth(pRoot->m_pLeft);
    int depthRight = GetDepth(pRoot->m_pRight);
    return depthLeft > depthRight ? (depthLeft   1) : (depthRight   1); 
}

5若该结点的右子树为非空,则将该结点的右子树入队列;

12、求二叉树中节点的最大间距

即二叉树中相距最远的八个节点之间的相距。 
递归解法: 
(1卡塔尔国假诺二叉树为空,重返0,同期记录左子树和右子树的纵深,都为0 
(2卡塔 尔(阿拉伯语:قطر‎纵然二叉树不为空,最大间隔要么是左子树中的最大间距,要么是右子树中的最大间隔,要么是左子树节点中到根节点的最大间隔 右子树节点中到根节点的最大间隔,同时记录左子树和右子树节点中到根节点的最大间距。 
参照代码如下:

int GetMaxDistance(BinaryTreeNode * pRoot, int & maxLeft, int & maxRight)
{
    // maxLeft, 左子树中的节点距离根节点的最远距离
    // maxRight, 右子树中的节点距离根节点的最远距离
    if(pRoot == NULL)
    {
        maxLeft = 0;
        maxRight = 0;
        return 0;
    }
    int maxLL, maxLR, maxRL, maxRR;
    int maxDistLeft, maxDistRight;
    if(pRoot->m_pLeft != NULL)
    {
        maxDistLeft = GetMaxDistance(pRoot->m_pLeft, maxLL, maxLR);
        maxLeft = max(maxLL, maxLR)   1;
    }
    else
    {
        maxDistLeft = 0;
        maxLeft = 0;
    }
    if(pRoot->m_pRight != NULL)
    {
        maxDistRight = GetMaxDistance(pRoot->m_pRight, maxRL, maxRR);
        maxRight = max(maxRL, maxRR)   1;
    }
    else
    {
        maxDistRight = 0;
        maxRight = 0;
    }
    return max(max(maxDistLeft, maxDistRight), maxLeft maxRight);
}

若二叉树为空,则空操作再次回到;不然

  1. 求二叉树中的节点个数 
  2. 求二叉树的深浅 
  3. 前序遍历,中序遍历,后序遍历 
    4. 支行遍历二叉树(按档期的顺序从上往下,从左往右卡塔 尔(英语:State of Qatar) 
    5. 将二叉查找树变为有序的双向链表 
  4. 求二叉树第K层的节点个数 
  5. 求二叉树中叶子节点的个数 
  6. 推断两棵二叉树是还是不是结构相符 
  7. 决断二叉树是还是不是平衡二叉树 
  8. 求二叉树的镜像 
    11. 求二叉树中四个节点的最低公共祖先节点 
  9. 求二叉树中节点的最大间距 
    13. 由前序遍历类别和中序遍历体系重新创立二叉树 
  10. 认清二叉树是还是不是完全二叉树

3出游列得到二个结点,访谈该结点;

8、剖断两棵二叉树是或不是结构同样

不酌量数据内容。结构相通意味着相应的左子树和呼应的右子树都组织雷同。 
递归解法: 
(1卡塔尔借使两棵二叉树都为空,重回真 
(2卡塔 尔(英语:State of Qatar)假诺两棵二叉树风姿洒脱棵为空,另意气风发棵不为空,重回假 
(3卡塔 尔(英语:State of Qatar)如若两棵二叉树都不为空,假设对应的左子树和右子树都同构再次来到真,其他重返假 
参照他事他说加以侦察代码如下:

bool StructureCmp(BinaryTreeNode * pRoot1, BinaryTreeNode * pRoot2)
{
    if(pRoot1 == NULL && pRoot2 == NULL) // 都为空,返回真
        return true;
    else if(pRoot1 == NULL || pRoot2 == NULL) // 有一个为空,一个不为空,返回假
        return false;
    bool resultLeft = StructureCmp(pRoot1->m_pLeft, pRoot2->m_pLeft); // 比较对应左子树 
    bool resultRight = StructureCmp(pRoot1->m_pRight, pRoot2->m_pRight); // 比较对应右子树
    return (resultLeft && resultRight);
} 

1 先(前)序遍历

4、分层遍历二叉树(按档次从上往下,从左往右卡塔 尔(阿拉伯语:قطر‎

相当于广度优先寻觅,使用队列实现。队列开始化,将根节点压入队列。当队列不为空,举行如下操作:弹出一个节点,访问,若左子节点或右子节点不为空,将其压入队列。

void LevelTraverse(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return;
    queue<BinaryTreeNode *> q;
    q.push(pRoot);
    while(!q.empty())
    {
        BinaryTreeNode * pNode = q.front();
        q.pop();
        Visit(pNode); // 访问节点
        if(pNode->m_pLeft != NULL)
            q.push(pNode->m_pLeft);
        if(pNode->m_pRight != NULL)
            q.push(pNode->m_pRight);
    }
    return;
}

[1] 《大话数据结构》

13、由前序遍历类别和中序遍历类别重新创设二叉树

二叉树前序遍历体系中,第二个要素总是树的根节点的值。中序遍历体系中,左子树的节点的值位于根节点的值的左侧,右子树的节点的值位 
于根节点的值的右边。 
递归解法: 
(1卡塔尔国借使前序遍历为空或中序遍历为空或节点个数小于等于0,重返NULL。 
(2卡塔尔创立根节点。前序遍历的首先个数据正是根节点的数量,在中序遍历中找到根节点的义务,可个别查出左子树和右子树的前序和中序遍 
历体系,重新建构左右子树。

BinaryTreeNode * RebuildBinaryTree(int* pPreOrder, int* pInOrder, int nodeNum)
{
    if(pPreOrder == NULL || pInOrder == NULL || nodeNum <= 0)
        return NULL;
    BinaryTreeNode * pRoot = new BinaryTreeNode;
    // 前序遍历的第一个数据就是根节点数据
    pRoot->m_nValue = pPreOrder[0];
    pRoot->m_pLeft = NULL;
    pRoot->m_pRight = NULL;
    // 查找根节点在中序遍历中的位置,中序遍历中,根节点左边为左子树,右边为右子树
    int rootPositionInOrder = -1;
    for(int i = 0; i < nodeNum; i  )
        if(pInOrder[i] == pRoot->m_nValue)
        {
            rootPositionInOrder = i;
            break;
        }
    if(rootPositionInOrder == -1)
    {
        throw std::exception("Invalid input.");
    }
    // 重建左子树
    int nodeNumLeft = rootPositionInOrder;
    int * pPreOrderLeft = pPreOrder   1;
    int * pInOrderLeft = pInOrder;
    pRoot->m_pLeft = RebuildBinaryTree(pPreOrderLeft, pInOrderLeft, nodeNumLeft);
    // 重建右子树
    int nodeNumRight = nodeNum - nodeNumLeft - 1;
    int * pPreOrderRight = pPreOrder   1   nodeNumLeft;
    int * pInOrderRight = pInOrder   nodeNumLeft   1;
    pRoot->m_pRight = RebuildBinaryTree(pPreOrderRight, pInOrderRight, nodeNumRight);
    return pRoot;
}

后生可畏律,有中序遍历类别和后序遍历体系,相仿的法门可重新建构二叉树,但前序遍历系列和后序遍历体系差异复苏豆蔻梢头棵二叉树,评释略。

从树的首先层,从上而下逐层遍历,在每意气风发层中,根据从左到右的相继依次访谈结点。

9、 决断二叉树是否平衡二叉树

递归解法: 
(1卡塔尔国假使二叉树为空,重返真 
(2卡塔尔若是二叉树不为空,假使左子树和右子树都是AVL树並且左子树和右子树中度相差不超过1,再次回到真,其余重临假 
参照代码:

bool IsAVL(BinaryTreeNode * pRoot, int & height)
{
    if(pRoot == NULL) // 空树,返回真
    {
        height = 0;
        return true;
    }
    int heightLeft;
    bool resultLeft = IsAVL(pRoot->m_pLeft, heightLeft);
    int heightRight;
    bool resultRight = IsAVL(pRoot->m_pRight, heightRight);
    if(resultLeft && resultRight && abs(heightLeft - heightRight) <= 1) // 左子树和右子树都是AVL,并且高度相差不大于1,返回真
    {
        height = max(heightLeft, heightRight)   1;
        return true;
    }
    else
    {
        height = max(heightLeft, heightRight)   1;
        return false;
    }
}

算法观念:

3、前序遍历,中序遍历,后序遍历

前序遍历递归解法: 
(1卡塔尔假使二叉树为空,空操作 
(2卡塔尔假若二叉树不为空,先会见根节点,然后遍历左子树,再遍历右子树 
仿效代码如下:

void PreOrderTraverse(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return;
    printf("%dn",pRoot->data); // 显示结点数据
    PreOrderTraverse(pRoot->m_pLeft); // 前序遍历左子树
    PreOrderTraverse(pRoot->m_pRight); // 前序遍历右子树
}

中序遍历递归解法 
(1卡塔尔假若二叉树为空,空操作。 
(2卡塔 尔(阿拉伯语:قطر‎假使二叉树不为空,先遍历左子树,然后访谈根节点,再遍历右子树 
参照代码如下:

void InOrderTraverse(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return;
    InOrderTraverse(pRoot->m_pLeft); // 中序遍历左子树
    printf("%dn",pRoot->data); // 显示结点数据
    InOrderTraverse(pRoot->m_pRight); // 中序遍历右子树
}

后序遍历递归解法 
(1卡塔 尔(阿拉伯语:قطر‎假设二叉树为空,空操作。 
(2卡塔尔国若是二叉树不为空,先遍历左子树,然后遍历右子树,访问根节点 
参照代码如下:

void InOrderTraverse(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL)
        return;
    InOrderTraverse(pRoot->m_pLeft); // 后序遍历左子树
    InOrderTraverse(pRoot->m_pRight); // 后序遍历右子树
    printf("%dn",pRoot->data); // 显示结点数据
}

(1卡塔 尔(英语:State of Qatar)中序遍历左子树;

10、求二叉树的镜像

递归解法: 
(1卡塔尔国假设二叉树为空,重临空 
(2卡塔 尔(英语:State of Qatar)借使二叉树不为空,求左子树和右子树的镜像,然后换到左子树和右子树 
参谋代码如下:

BinaryTreeNode * Mirror(BinaryTreeNode * pRoot)
{
    if(pRoot == NULL) // 返回NULL
        return NULL;
    BinaryTreeNode * pLeft = Mirror(pRoot->m_pLeft); // 求左子树镜像
    BinaryTreeNode * pRight = Mirror(pRoot->m_pRight); // 求右子树镜像
        // 交换左子树和右子树
    pRoot->m_pLeft = pRight;
    pRoot->m_pRight = pLeft;
    return pRoot;
}

彩世界网址 2

6、求二叉树第K层的节点个数

递归解法: 
(1卡塔 尔(阿拉伯语:قطر‎要是二叉树为空大概k<1重临0 
(2卡塔 尔(阿拉伯语:قطر‎假使二叉树不为空何况k==1,再次来到1 
(3卡塔尔借使二叉树不为空且k>1,重返左子树中k-1层的节点个数与右子树k-1层节点个数之和 
参照他事他说加以考察代码如下:

int GetNodeNumKthLevel(BinaryTreeNode * pRoot, int k)
{
    if(pRoot == NULL || k < 1)
        return 0;
    if(k == 1)
        return 1;
    int numLeft = GetNodeNumKthLevel(pRoot->m_pLeft, k-1); // 左子树中k-1层的节点个数
    int numRight = GetNodeNumKthLevel(pRoot->m_pRight, k-1); // 右子树中k-1层的节点个数
    return (numLeft   numRight);
}
void PreOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 先序递归遍历二叉树T */
   if(T)
   {
     Visit(T); /* 先访问根结点 */
     PreOrderTraverse(T->lchild,Visit); /* 再先序遍历左子树 */
     PreOrderTraverse(T->rchild,Visit); /* 最后先序遍历右子树 */
   }
 }

11、求二叉树中多少个节点的最低公共祖先节点

递归解法: 
(1卡塔 尔(阿拉伯语:قطر‎假设四个节点分别在根节点的左子树和右子树,则赶回根节点 
(2卡塔尔如若八个节点都在左子树,则递归管理左子树;纵然多少个节点都在右子树,则递归管理右子树 
参照代码如下:

bool FindNode(BinaryTreeNode * pRoot, BinaryTreeNode * pNode)
{
    if(pRoot == NULL || pNode == NULL)
        return false;

    if(pRoot == pNode)
        return true;

    bool found = FindNode(pRoot->m_pLeft, pNode);
    if(!found)
        found = FindNode(pRoot->m_pRight, pNode);

    return found;
}

BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, 
                                     BinaryTreeNode * pNode1, 
                                     BinaryTreeNode * pNode2)
{
    if(FindNode(pRoot->m_pLeft, pNode1))
    {
        if(FindNode(pRoot->m_pRight, pNode2))
            return pRoot;
        else
            return GetLastCommonParent(pRoot->m_pLeft, pNode1, pNode2);
    }
    else
    {
        if(FindNode(pRoot->m_pLeft, pNode2))
            return pRoot;
        else
            return GetLastCommonParent(pRoot->m_pRight, pNode1, pNode2);
    }
}

分析: 
递归解法功能异常的低,有无数重复的遍历,上边看一下非递归解法。 
非递归解法: 
先求从根节点到八个节点的不二等秘书诀,然后再相比对应路线的节点就能够,最终二个均等的节点也正是他们在二叉树中的最低公共祖先节点 
参照代码如下:

bool GetNodePath(BinaryTreeNode * pRoot, BinaryTreeNode * pNode, 
                 list<BinaryTreeNode *> & path)
{
    if(pRoot == pNode)
    {   
        path.push_back(pRoot);
        return true;
    }
    if(pRoot == NULL)
        return false;
    path.push_back(pRoot);
    bool found = false;
    found = GetNodePath(pRoot->m_pLeft, pNode, path);
    if(!found)
        found = GetNodePath(pRoot->m_pRight, pNode, path);
    if(!found)
        path.pop_back();
    return found;
}
BinaryTreeNode * GetLastCommonParent(BinaryTreeNode * pRoot, BinaryTreeNode * pNode1, BinaryTreeNode * pNode2)
{
    if(pRoot == NULL || pNode1 == NULL || pNode2 == NULL)
        return NULL;
    list<BinaryTreeNode*> path1;
    bool bResult1 = GetNodePath(pRoot, pNode1, path1);
    list<BinaryTreeNode*> path2;
    bool bResult2 = GetNodePath(pRoot, pNode2, path2);
    if(!bResult1 || !bResult2) 
        return NULL;
    BinaryTreeNode * pLast = NULL;
    list<BinaryTreeNode*>::const_iterator iter1 = path1.begin();
    list<BinaryTreeNode*>::const_iterator iter2 = path2.begin();
    while(iter1 != path1.end() && iter2 != path2.end())
    {
        if(*iter1 == *iter2)
            pLast = *iter1;
        else
            break;
        iter1  ;
        iter2  ;
    }
    return pLast;
}

在上述算法的根底上稍加变化就能够求二叉树中随便八个节点的间隔了。

彩世界网址 3

struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

二叉树节点定义

若二叉树为空,则空操作再次来到;不然

2 中序遍历

(1卡塔 尔(英语:State of Qatar)访问根节点;

void LevelOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 层序遍历二叉树T(利用队列) */
   LinkQueue q;
   QElemType a;
   if(T)
   {
     InitQueue(&q);
     EnQueue(&q,T);
     while(!QueueEmpty(q))
     {
       DeQueue(&q,&a);
       Visit(a);
       if(a->lchild!=NULL)
         EnQueue(&q,a->lchild);
       if(a->rchild!=NULL)
         EnQueue(&q,a->rchild);
     }
   }
 }
void InOrderTraverse(BiPTree T,void(*Visit)(BiPTree))
 { /* 中序递归遍历二叉树T */
   if(T)
   {
     InOrderTraverse(T->lchild,Visit); /* 中序遍历左子树 */
     Visit(T); /* 再访问根节点 */
     InOrderTraverse(T->rchild,Visit); /* 最后中序遍历右子树 */
   }
 }

(2卡塔 尔(英语:State of Qatar)后序遍历右子树;

6结束。

 

4若该结点的左子树为非空,则将该结点的左子树入队列;

(3卡塔尔国中序遍历右子树。

彩世界网址 4

2当队列为非空时,循环施行步骤3到步骤5,不然施行步骤6;

(3卡塔尔国先序遍历右子树。

1早先化八个行列,并把根结点入列队;

[3] wikipedia(二叉树):

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

若二叉树为空,则空操作重回;不然

[2] 《数据结构 严蔚敏》

(1卡塔 尔(英语:State of Qatar)后序遍历左子树;

[5] 博客园(二叉树的纵深优先遍历、广度优先遍历和非递归遍历)

3. 后序遍历

(2卡塔 尔(阿拉伯语:قطر‎先序遍历左子树;

二叉树的遍历(traversing binary tree卡塔尔国是指从根节点触发,依照某种次序依次拜会二叉树中的全体结点,使得各种结点都被访谈壹遍且仅被访问叁次。

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

(3卡塔 尔(阿拉伯语:قطر‎访谈根节点。

二叉树的层序遍历也正是二叉树的广度优先遍历。

本文由时时app平台注册网站发布于web前端,转载请注明出处:二叉树深度优先 求二叉树最大深度【彩世界网址

关键词: