数据结构之二叉树的递归建立和遍历(续)

谁借莪１个温暖的怀抱￠ 2022-08-21 14:56 44阅读 0赞

特此说明：上篇文章和这篇文章中的二叉树是链式二叉树的，不是顺序二叉树。

# 1、基本概述 #

A、层次遍历

摘自：[http://blog.sina.com.cn/s/blog\_5207b6c401009fq0.html][http_blog.sina.com.cn_s_blog_5207b6c401009fq0.html]

要采用的数据结构是队列。具体描述如下：

层次遍历：从上到下、从左到右依次访问结点。每次访问结点，就将该节点记录下来；若记录的所有结点都已经处理完毕，则结束遍历，否则重复下面的重装：

取出记录中第一个还没有访问的树的结点，若他有左子树，则访问左子树，并将其记录下来，否则，访问其右子树，并记录下来。

上面的算法中，记录结点就是入队操作，取出记录结点就是出队操作，这样一来，算法描述成下面的形式：

1）访问根节点，并将其根节点入队；

2）当队列不为空时，重复下列操作：

从队列出队一个结点；

若其有左子树，则访问左子树，并将其入队；

若其有右子树，则访问右子树，并将其入队；

B 、层次遍历

未使用队列完成层次遍历（我放到后面）

# 2、二叉树的深度计算 #

关键代码：

/// 二叉树---递归求得其深度
    int depth(BinTreeNode *T)
    {
    
        if (NULL == T)
        {
            return 0;
        }
        int leftDepth = depth(T->lchild);
        int rightDepth = depth(T->rchild);
        
        return leftDepth < rightDepth ? leftDepth + 1: rightDepth + 1;
    }

递归实现求得其深度。

# 3、二叉树的结点个数统计 #

关键代码

/// 二叉树统计结点个数
    int m_count(BinTreeNode *T)
    {
        if (NULL != T)
        {
            return m_count(T->lchild) + m_count(T->rchild) + 1;
        }
        return 0;
    }

递归完成对齐结点个数的统计。

# 4、层次遍历 #

注意：这里，不是使用队列完成层次遍历的。

/// 二叉树层次遍历输出
    void PrintNodeAtLeves(BinTreeNode *T, int level)
    {
        /// 空树或层级不合理
        if (NULL == T || level < 1)
        {
            cout << "空树或者层级不合理" << endl;
            return;
        }
        /// 若只有根节点
        if (1 == level)
        {
            cout << T->index << " ";
            return;
        }
        /// 左子树的level-1
        PrintNodeAtLeves(T->lchild, level - 1);
        
        /// 右子树的level-1
        PrintNodeAtLeves(T->rchild, level - 1);
    }
    
    /// 二叉树的层次遍历
    void Level(BinTreeNode *T)
    {
        if (NULL == T)
        {
            cout << "树T = NULL";
            return;
        }
        /// 获取树的深度
        int m_depth = depth(T);
        
        for (int i = 1; i <= m_depth; i++)
        {
            PrintNodeAtLeves(T, i);
            cout << endl;
        }
    }

## 5、层次遍历（未使用队列）完成源码 ##

#include <iostream>
    using namespace std;

struct BinTreeNode
    {
        int index;
        BinTreeNode *lchild;
        BinTreeNode *rchild;
    };

/// 构建二叉树
    BinTreeNode *create(BinTreeNode *T)
    {
        int input = NULL;
        cout << "请输入数据：";
        cin >> input;
        
        if (0 == input)
        {
            T = NULL;
            return T;
        }
        T = (BinTreeNode *)malloc(sizeof(BinTreeNode));
        if (NULL == T)
        {
            cout << "内存分配失败" << endl;
            exit(1);
        }
        T->index = input;
        T->lchild = create(T->lchild);
        T->rchild = create(T->rchild);
        
        return T;
    }

/// 二叉树统计结点个数
    int m_count(BinTreeNode *T)
    {
        if (NULL != T)
        {
            return m_count(T->lchild) + m_count(T->rchild) + 1;
        }
        return 0;
    }
    
    /// 二叉树---递归求得其深度
    int depth(BinTreeNode *T)
    {
    
        if (NULL == T)
        {
            return 0;
        }
        int leftDepth = depth(T->lchild);
        int rightDepth = depth(T->rchild);
        
        return leftDepth < rightDepth ? leftDepth + 1: rightDepth + 1;
    }
    
    /// 二叉树层次遍历输出
    void PrintNodeAtLeves(BinTreeNode *T, int level)
    {
        /// 空树或层级不合理
        if (NULL == T || level < 1)
        {
            cout << "空树或者层级不合理" << endl;
            return;
        }
        /// 若只有根节点
        if (1 == level)
        {
            cout << T->index << " ";
            return;
        }
        /// 左子树的level-1
        PrintNodeAtLeves(T->lchild, level - 1);
        
        /// 右子树的level-1
        PrintNodeAtLeves(T->rchild, level - 1);
    }
    
    /// 二叉树的层次遍历
    void Level(BinTreeNode *T)
    {
        if (NULL == T)
        {
            cout << "树T = NULL";
            return;
        }
        /// 获取树的深度
        int m_depth = depth(T);
        
        for (int i = 1; i <= m_depth; i++)
        {
            PrintNodeAtLeves(T, i);
            cout << endl;
        }
    }
    
    
    ///主函数
    int main(int argc, const char * argv[])
    {
        /// 二叉树
        BinTreeNode *T = NULL;
        
        T = CreateBinTree(T);
        
        cout << "结点个数" << m_count(T) << endl;
        cout << "树的深度为：" << depth(T) << endl;
        
        cout << "层次遍历" << endl;
        Level(T);
        cout << endl;
    }

#  6、运行结果： #

![20160506095326610][]

[http_blog.sina.com.cn_s_blog_5207b6c401009fq0.html]: http://blog.sina.com.cn/s/blog_5207b6c401009fq0.html
[20160506095326610]: /images/20220724/6453bf97c68941968270b8c8951ef7f2.png