求二叉树最大深度,2叉树面试题

By admin in 4858美高梅 on 2019年4月2日

深度优先遍历:对每1个或然的分支路径深刻到不可能再深刻截止,而且每一个结点只可以访问一次。要特别注意的是,贰叉树的纵深优先遍历相比较独特,能够细分为先序遍历、中序遍历、后序遍历。

二叉树

二叉树面试题

二叉树的遍历(traversing
binary tree)是指从根节点触发,根据某种次序依次走访2叉树中的全部结点,使得各类结点都被访问一回且仅被访问1次。

二叉树最大深度:

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

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

 

2叉树的基本概念

   贰叉树是每一个节点最多有多个子树的树结构。日常子树被称作“左子树”(left
subtree)和“右子树”(right subtree)

  1. 求二叉树中的节点个数 
  2. 求二叉树的深浅 
  3. 前序遍历,中序遍历,后序遍历 
    四.
    分段遍历二叉树(按层次从上往下,从左往右) 
    五.
    将二叉查找树变为有序的双向链表 
  4. 求二叉树第K层的节点个数 
  5. 求二叉树中叶子节点的个数 
  6. 判断两棵贰叉树是或不是结构同样 
  7. 认清二叉树是还是不是平衡二叉树 
  8. 求二叉树的镜像 
    1壹.
    求2叉树中多个节点的最低公共祖先节点 
  9. 求贰叉树中节点的最大距离 
    一叁.
    由前序遍历系列和中序遍历体系重建贰叉树 
  10. 看清二叉树是或不是一点1滴贰叉树

1 先(前)序遍历

二叉树的习性(天性)

性质1: 在二叉树的第i层上至多有贰^(i-一)个结点(i>0)
求二叉树最大深度,2叉树面试题。性质2: 深度为k的二叉树至多有二^k – 3个结点(k>0)
性质3:
对于自由一棵二叉树,如若其叶结点数为N0,而度数为2的结点总数为N2,则N0=N二+壹;
性质4:怀有n个结点的完全二叉树的吃水必为 log二(n+一)
性质5:对完全2叉树,若从上至下、从左至右编号,则编号为i
的结点,其左孩子编号必为二i,其右孩子编号必为二i+壹;其父母的号码必为i/二(i=一时为根,除却)

(一)完全2叉树——若设二叉树的万丈为h,除第 h 层外,别的各层 (一~h-一)
的结点数都实现最大个数,第h层有叶子结点,并且叶子结点都以从左到右依次排布,那便是截然2叉树。
4858美高梅 1

(二)满贰叉树——除了叶结点外每3个结点都有左右子叶且叶子结点都地处最尾巴部分的贰叉树。
4858美高梅 2

二叉树节点定义

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

2叉树的节点表示以及树的制造

   通过选择Node类中定义多少个天性,分别为elem本人的值,还有lchild左孩子和rchild右孩子

class Node(object):
    """节点类"""
    def __init__(self, elem=-1, lchild=None, rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

  树的创办,创设一个树的类,并给1个root根节点,一起初为空,随后添加节点

class Tree(object):
    """树类"""
    def __init__(self, root=None):
        self.root = root

    def add(self, elem):
        """为树添加节点"""
        node = Node(elem)
        #如果树是空的,则对根节点赋值
        if self.root == None:
            self.root = node
        else:
            queue = []
            queue.append(self.root)
            #对已有的节点进行层次遍历
            while queue:
                #弹出队列的第一个元素
                cur = queue.pop(0)
                if cur.lchild == None:
                    cur.lchild = node
                    return
                elif cur.rchild == None:
                    cur.rchild = node
                    return
                else:
                    #如果左右子树都不为空,加入队列继续判断
                    queue.append(cur.lchild)
                    queue.append(cur.rchild)
struct BinaryTreeNode
{
    int m_nValue;
    BinaryTreeNode* m_pLeft;
    BinaryTreeNode* m_pRight;
};

(壹)访问根节点;

二叉树的遍历

  树的遍历是树的一种重大的演算。所谓遍历是指对树中拥有结点的新闻的造访,即依次对树中每种结点访问二回且仅访问三回,我们把那种对具有节点的拜访称为遍历(traversal)。那么树的三种重大的遍历格局是深度优先遍历和广度优先遍历,纵深优先一般用递归,广度优先一般用队列。一般景色下能用递归完结的算法超过一半也能用堆栈来促成。

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

递归解法: 
(一)固然二叉树为空,节点个数为0 
(二)假如二叉树不为空,2叉树节点个数 =
左子树节点个数 + 右子树节点个数 + 壹 
参照代码如下:

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

(2)先序遍历左子树;

纵深优先遍历

  对于1颗2叉树,深度优先搜索(Depth First
Search)是沿着树的纵深遍历树的节点,尽可能深的搜索树的分支。
  那么深度遍历有相当重要的三种方法。那二种办法常被用来访问树的节点,它们中间的两样在于访问每一个节点的次第分裂。那三种遍历分小名字为先序遍历(preorder),中序遍历(inorder)和后序遍历(postorder)。大家来交付它们的详实定义,然后举例看看它们的采纳。

  • 先序遍历
    在先序遍历中,我们先访问根节点,然后递归使用先序遍历访问左子树,再递归使用先序遍历访问右子树

根节点->左子树->右子树

“`python
def preorder(self, root):
“””递归达成先序遍历”””
if root == None:
return
print root.elem
self.preorder(root.lchild)
self.preorder(root.rchild)

“`

  • 中序遍历
    在中序遍历中,大家递归使用中序遍历访问左子树,然后访问根节点,最终再递归使用中序遍历访问右子树

左子树->根节点->右子树

“`python
def inorder(self, root):
“””递归完成中序遍历”””
if root == None:
return
self.inorder(root.lchild)
print root.elem
self.inorder(root.rchild)

“`

  • 后序遍历
    在后序遍历中,大家先递归使用后序遍历访问左子树和右子树,最终访问根节点

左子树->右子树->根节点

“`python
def postorder(self, root):
“””递归实现持续遍历”””
if root == None:
return
self.postorder(root.lchild)
self.postorder(root.rchild)
print root.elem

“`

贰、求2叉树的纵深

递归解法: 
(一)如若二叉树为空,二叉树的纵深为0 
(二)如果2叉树不为空,贰叉树的深浅 =
max(左子树深度, 右子树深度) + 壹 
参考代码如下:

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); 
}

(3)先序遍历右子树。

广度优先遍历(层次遍历)

  从树的root起首,从上到下从从左到右遍历整个树的节点

def breadth_travel(self, root):
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)

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

前序遍历递归解法: 
(一)倘诺二叉树为空,空操作 
(二)就算2叉树不为空,先访问根节点,然后遍历左子树,再遍历右子树 
参照代码如下:

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

中序遍历递归解法 
(一)固然二叉树为空,空操作。 
(二)假使2叉树不为空,先遍历左子树,然后访问根节点,再遍历右子树 
参照代码如下:

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

后序遍历递归解法 
(壹)要是二叉树为空,空操作。 
(2)即使2叉树不为空,先遍历左子树,然后遍历右子树,访问根节点 
参考代码如下:

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

4858美高梅 3

四、分层遍历贰叉树(按层次从上往下,从左往右)

相当于广度优先搜索,使用队列落成。队列初步化,将根节点压入队列。当队列不为空,举行如下操作:弹出三个节点,访问,若左子节点或右子节点不为空,将其压入队列。

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

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

务求不能够创造新节点,只调整指针。 
递归解法: 
(一)假若贰叉树查找树为空,不须要更换,对应双向链表的首先个节点是NULL,最终叁个节点是NULL 
(二)假诺二叉查找树不为空: 
比方左子树为空,对应双向有序链表的率先个节点是根节点,右侧不供给其余操作; 
如果左子树不为空,转换左子树,贰叉查找树对应双向有序链表的首先个节点正是左子树转换后双向有序链表的率先个节点,同时将根节点和左子树转换后的双向有序链
表的末尾1个节点连接; 
假使右子树为空,对应双向有序链表的最后八个节点是根节点,右侧不须要任何操作; 
若果右子树不为空,对应双向有序链表的尾声叁个节点正是右子树转换后双向有序链表的最后一个节点,同时将根节点和右子树转换后的双向有序链表的第二个节点连
接。 
参照代码如下:

/******************************************************************************
参数:
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;
}

2 中序遍历

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

递归解法: 
(1)如若2叉树为空恐怕k<一再次回到0 
(二)如若二叉树不为空并且k==1,重临一 
(叁)要是贰叉树不为空且k>一,重临左子树中k-壹层的节点个数与右子树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);
}

若2叉树为空,则空操作返回;不然

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

递归解法: 
(1)要是贰叉树为空,再次回到0 
(2)固然贰叉树不为空且左右子树为空,重临1 
4858美高梅,(三)假诺2叉树不为空,且左右子树不相同时为空,再次回到左子树中叶子节点个数加上右子树中叶子节点个数 
参照代码如下:

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)中序遍历左子树;

八、判断两棵2叉树是不是结构同样

不思考数据内容。结构同样意味着相应的左子树和相应的右子树都组织同样。 
递归解法: 
(1)假使两棵贰叉树都为空,再次来到真 
(二)借使两棵二叉树1棵为空,另1棵不为空,再次回到假 
(叁)倘若两棵二叉树都不为空,假若对应的左子树和右子树都同构再次回到真,别的重返假 
参考代码如下:

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);
} 

(2)访问根节点;

九、 判断贰叉树是否平衡2叉树

递归解法: 
(一)假如二叉树为空,重临真 
(2)假诺2叉树不为空,假若左子树和右子树都以AVL树并且左子树和右子树中度相差不超过一,重回真,其余重临假 
参考代码:

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)中序遍历右子树。

10、求二叉树的镜像

递归解法: 
(①)假设贰叉树为空,再次来到空 
(2)如若2叉树不为空,求左子树和右子树的镜像,然后换到左子树和右子树 
参考代码如下:

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;
}

4858美高梅 4

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

递归解法: 
(1)固然四个节点分别在根节点的左子树和右子树,则赶回根节点 
(贰)固然八个节点都在左子树,则递归处理左子树;假使三个节点都在右子树,则递归处理右子树 
参照代码如下:

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);
    }
}

分析: 
递归解法功效相当低,有很多重新的遍历,下边看一下非递归解法。 
非递归解法: 
先求从根节点到七个节点的不2诀要,然后再相比对应路径的节点就行,最终3个同1的节点相当于她们在2叉树中的最低公共祖先节点 
参照代码如下:

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;
}

在上述算法的根底上稍加变化即可求二叉树中自由七个节点的相距了。

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

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

即二叉树中相距最远的多个节点之间的离开。 
递归解法: 
(1)假使2叉树为空,重回0,同时记录左子树和右子树的吃水,都为0 
(贰)假诺二叉树不为空,最大距离要么是左子树中的最大距离,要么是右子树中的最大距离,要么是左子树节点中到根节点的最大距离+右子树节点中到根节点的最大距离,同时记录左子树和右子树节点中到根节点的最大距离。 
参考代码如下:

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);
}

3. 后序遍历

一叁、由前序遍历连串和中序遍历体系重建2叉树

贰叉树前序遍历连串中,第三个成分总是树的根节点的值。中序遍历体系中,左子树的节点的值位于根节点的值的左手,右子树的节点的值位 
于根节点的值的右手。 
递归解法: 
(一)若是前序遍历为空或中序遍历为空或节点个数小于等于0,重返NULL。 
(二)创制根节点。前序遍历的率先个数据正是根节点的多寡,在中序遍历中找到根节点的职位,可分别查出左子树和右子树的前序和中序遍 
历类别,重建左右子树。

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;
}

相同,有中序遍历系列和后序遍历类别,类似的法子可重建二叉树,但前序遍历系列和后序遍历连串差异复苏一棵2叉树,表明略。

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

1四、判断2叉树是否一点壹滴2叉树

若设二叉树的吃水为h,除第 h
层外,别的各层 (一~h-壹) 的结点数都达到最大个数,第 h
层全数的结点都三番五次集中在最左侧,那正是一心 
二叉树。 
有如下算法,按层次(从上到下,从左到右)遍历2叉树,当遭受三个节点的左子树为空时,则该节点右子树必须为空,且前边遍历的节点左 
右子树都无法不为空,不然不是一心2叉树。

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;
}

 

(一)后序遍历左子树;

(二)后序遍历右子树;

(三)访问根节点。

4858美高梅 5

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

4. 层序遍历

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

从树的首先层,从上而下逐层遍历,在每壹层中,依据从左到右的逐条依次访问结点。

4858美高梅 6

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

算法思想:

1开头化贰个类别,并把根结点入列队;

二当队列为非空时,循环执行步骤3到步骤伍,不然执行步骤陆;

三出游列取得3个结点,访问该结点;

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

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

6结束。

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);
     }
   }
 }

Reference:

[1] 《大话数据结构》

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

[3]
wikipedia(二叉树):

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

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

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

网站地图xml地图
Copyright @ 2010-2019 美高梅手机版4858 版权所有