首页 » C++ » 求解二叉树的深度

求解二叉树的深度

原文 http://blog.csdn.net/soygrow/article/details/79230229

2018-02-02 02:01:05阅读(203)

求解二叉树的深度可以采用递归和非递归的方式。递归实现的代码很是简单、易懂。而非递归实现代码较复杂。

递归求解二叉树深度

递归的结束条件有两个:1.该节点为NULL,返会0;2.当前节点的左右字数深度均求出,返会最大值
下面是递归实现的代码:

//递归求解二叉树的深度
int BTreeDepth(BTree *root)
{
    if (root == NULL)
        return 0;
    int left = 1 + BTreeDepth(root->lChild);
    int right = 1 + BTreeDepth(root->rChild);
    return left>right?left:right;
}

非递归求解二叉树深度

同样利用栈来实现求解二叉树的深度,栈最大时即为二叉树的深度。这里对二叉树节点的数据结构进行包装:
二叉树的结构体为:

struct BTree
{
    int data;
    BTree* lChild;
    BTree* rChild;
    BTree():data(0),lChild(NULL),rChild(NULL){};
};

对该结构体进行增加信息,增加两个变量分别表示该节点的左右孩子节点是否被访问过:

struct StackBTree
{
    BTree *bTree;
    int lFlag;//标记左孩子是否被访问过,0:未访问 1:已访问
    int rFlag;;//标记右孩子是否被访问
    StackBTree():lFlag(0),rFlag(0),bTree(NULL){};
};

利用该结构体求解二叉树深度的思路如下:

判断根节点是否为空,若为空则,返回0;若不为空,则将根节点入栈; while循环。若栈不为空,则进程while循环 取栈顶元素 一种情况:若该元素的左孩子非空,且左孩子未被访问过;
标记该节点的左孩子被访问过 将该节点的左孩子入栈 另一种情况:若该元素的左孩子被访问过或者左孩子为空、并且右孩子非空,且右孩子未被访问过;
标记该节点右孩子被访问过 将该节点的右孩子入栈 最后一种情况:
depth等于depth和栈大小中的最大值 栈顶元素出栈 转到第三步 返回depth,保存深度的变量

该方法主要是通过标记访问过的变量,利用栈的深度来计算二叉树的深度。具体代码如下所示:

#pragma once
#ifndef BTREE_H
#define BTREE_H
#include <iostream>
#include <stack>
using namespace std;
struct BTree
{
    int data;
    BTree* lChild;
    BTree* rChild;
    BTree():data(0),lChild(NULL),rChild(NULL){};
};
//构造二叉树
void InitBTree(BTree *root)
{
    root->data = 1;
    root->lChild = new BTree();
    root->lChild->data = 2;
    root->rChild = new BTree();
    root->rChild->data = 3;
    root->lChild->lChild = new BTree();
    root->lChild->lChild->data = 4;
    root->lChild->rChild = new BTree();
    root->lChild->rChild->data = 5;
    root->rChild->lChild = new BTree();
    root->rChild->lChild->data = 6;
    root->rChild->rChild = new BTree();
    root->rChild->rChild->data = 7;
    root->rChild->lChild->lChild = new BTree();
    root->rChild->lChild->lChild->data = 8;
    root->rChild->lChild->lChild->lChild = new BTree();
    root->rChild->lChild->lChild->lChild->data = 9;
}
//递归求解二叉树的深度
int BTreeDepth(BTree *root)
{
    if (root == NULL)
        return 0;
    int left = 1 + BTreeDepth(root->lChild);
    int right = 1 + BTreeDepth(root->rChild);
    return left>right?left:right;
}
struct StackBTree
{
    BTree *bTree;
    int lFlag;//标记左孩子是否被访问过,0:未访问 1:已访问
    int rFlag;;//标记右孩子是否被访问
    StackBTree():lFlag(0),rFlag(0),bTree(NULL){};
};
//非递归求解二叉树的深度--一基本思路按照栈的深度即为从根节点到某一孩子节点的距离
int PostOrderDepth(BTree* root)
{
    int depth = 0;//保存最大深度
    if (root ==NULL)
        return depth;
    //二叉树的深度即为所用栈的最大深度
    stack<StackBTree> s;
    StackBTree stackBTree;
    stackBTree.bTree = root;
    s.push(stackBTree);//根节点入栈
    //每次入栈时,得到最大栈深度
    depth = (depth>s.size()?depth:s.size());
    StackBTree* topBTree = NULL;
    while (s.size()>0)
    {
        //取栈顶元素
        topBTree = &(s.top());
        if (topBTree->bTree->lChild!=NULL && topBTree->lFlag==0)
        {
            StackBTree tmpBTree;
            tmpBTree.bTree = topBTree->bTree->lChild;
            topBTree->lFlag = 1;//标记根节点左孩子已访问
            s.push(tmpBTree);
        }
        else if ((topBTree->lFlag==1 || topBTree->bTree->lChild==NULL) && topBTree->bTree->rChild!=NULL && topBTree->rFlag==0)
        {
            //左孩子为空或者已经访问 && 右孩子不为空 && 该节点右孩子未被访问
            StackBTree tmpBTree;
            tmpBTree.bTree = topBTree->bTree->rChild;
            topBTree->rFlag = 1;//标记该节点右节点已访问
            s.push(tmpBTree);
        }
        else
        {
            //每次入栈结束时,得到最大栈深度
            depth = (depth>s.size()?depth:s.size());
            s.pop();
        }
    }
    return depth;
}
#endif
// BTreeDepth.cpp : 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include "btree.h"
int _tmain(int argc, _TCHAR* argv[])
{
    BTree root;
    InitBTree(&root);
    cout<<BTreeDepth(&root)<<endl;
    cout<<PostOrderDepth(&root)<<endl;
    return 0;
}

最新发布

CentOS专题

关于本站

5ibc.net旗下博客站精品博文小部分原创、大部分从互联网收集整理。尊重作者版权、传播精品博文,让更多编程爱好者知晓!

小提示

按 Ctrl+D 键,
把本文加入收藏夹