二叉查找树的非递归操作

二叉查找树的非递归操作

大家好,又见面了,我是全栈君。

昨天同学去參加阿里巴巴面试,被问到二叉树的一些基本问题,分享一下:

1.怎样非递归dfs求得树的深度

2.怎样非递归bfs求得树的深度

*3.怎样非递归地中前后序遍历二叉查找树。

二叉树写过不下十次了。可是基本每次都是用递归来写。一时间问道还不能一下写出来。

问题二还是比較好写,一的话可能须要细致想想,可是假如是面试的话。可能我一时也说不出来。

老实说,我自己写得代码总得看来是满长的。可是局部核心的是相对照较好理解的。

/***********************************************************
	> OS     : Linux 3.13.0-24-generic (Mint-17)
	> Author : yaolong
	> Mail   : dengyaolong@yeah.net
	> Time   : 2014年09月18日 星期四 12时24分57秒
 **********************************************************/
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cstdlib>
using namespace std;
template<typename Comparable>
class BinarySearchTree
{
public:
    BinarySearchTree()
    {
        root = NULL;
    };
    void insert ( Comparable x ) //非递归插入
    {
        if ( root == NULL ) //由于不是传引用指针
        {
            root = new Node ( x );
        }
        else
        {
            insert ( x, root );
        }
    }
    bool contains ( Comparable x ) //递归查询
    {
        return contains ( x, root );
    }
    void travel_in() //非递归中序遍历
    {
        travel_in ( root );
    }
    void travel_dg_in() //递归中序遍历
    {
        travel_dg_in ( root );
    }
    void travel_pre() //非递归前序遍历
    {
        travel_pre ( root );
    }
    void travel_dg_pre() //递归前序遍历
    {
        travel_dg_pre ( root );
    }
    void travel_suf() //非递归后序遍历,略微难
    {
        travel_suf ( root );
    }
    void travel_dg_suf() //递归后序遍历
    {
        travel_dg_suf ( root );
    }
    int get_depth_dg() //递归搜索树的深度
    {
        return get_depth_dg ( root );
    }
    int get_depth_dfs() //非递归,深度搜索树的深度
    {
        return get_depth_dfs ( root );
    }
    int get_depth_bfs() //非递归。宽度搜索树得深度
    {
        return get_depth_bfs ( root );
    }


private:
    class Node
    {
    public:
        Comparable element;
        Node *left;
        Node *right;
        Node ( Comparable e , Node *l = NULL, Node *r = NULL ) : element ( e ), left ( l ), right ( r )
        {
        }
    };
    void insert ( Comparable x, Node *p )
    {
        while ( 1 )
        {
            if ( x > p->element ) //比当前节点元素大。插入到右边
            {
                if ( p->right == NULL )
                {
                    p->right = new Node ( x );
                    return;
                }
                p = p->right;
            }
            else if ( x < p->element )
            {
                if ( p->left == NULL )
                {
                    p->left = new Node ( x );
                    return;
                }
                p = p->left;
            }
            else
            {
                //nothing to do
                return;
            }
        }
    }
    bool contains ( Comparable x, Node *p )
    {
        while ( p != NULL )
        {
            if ( x > p->element )
            {
                p = p->right;
            }
            else if ( x < p->element )
            {
                p = p->left;
            }
            else
            {
                return 1;
            }
        }
        return 0;
    }
    void travel_pre ( Node *p ) //前序遍历
    {
        stack<Node *> stk;
        while ( p != NULL || !stk.empty() )
        {
            while ( p != NULL ) //先读。再往左。知道叶子
            {
                cout << p->element << " ";
                stk.push ( p );
                p = p->left;
            }
            if ( !stk.empty() ) //左路訪问完,退回訪问右路,即用右儿子进行继续递归,进行前序遍历
            {
                p = stk.top();
                stk.pop();
                p = p->right;
            }
        }
    }
    void travel_dg_pre ( Node *p )
    {
        if ( p == NULL )
        {
            return;
        }
        cout << p->element << " ";
        travel_dg_pre ( p->left );
        travel_dg_pre ( p->right );
    }
    void travel_in ( Node *p )
    {
        stack<Node *> stk;
        while ( p != NULL || !stk.empty() )
        {
            while ( p != NULL )
            {
                stk.push ( p );
                p = p->left;
            }
            if ( !stk.empty() )
            {
                p = stk.top();
                stk.pop();
                cout << p->element << " ";
                p = p->right;
            }
        }
    }
    void travel_dg_in ( Node *p )
    {
        if ( p == NULL )
        {
            return;
        }
        travel_dg_in ( p->left );
        cout << p->element << " ";
        travel_dg_in ( p->right );
    }
    void travel_suf ( Node *p )
    {
        stack<Node *> stk;
        Node *prev = NULL;
        while ( p != NULL || !stk.empty() )
        {
            while ( p != NULL )
            {
                stk.push ( p );
                p = p->left;
            }
            p = stk.top();
            if ( p->right == NULL || p->right == prev )
            {
                cout << p->element << " ";
                prev = p;
                stk.pop();
                p = NULL;
            }
            else
            {
                p = p->right;
            }
        }
    }
    void travel_dg_suf ( Node *p )
    {
        if ( p == NULL )
        {
            return;
        }
        travel_dg_suf ( p->left );
        travel_dg_suf ( p->right );
        cout << p->element << " ";
    }
    int get_depth_dfs ( Node *p )
    {
        int depth = 0, d = 0;
        stack<Node *> stk;
        stack<int> stk_depth;
        while ( p != NULL || !stk.empty() )
        {
            while ( p != NULL )
            {
                stk.push ( p );
                stk_depth.push ( d++ );
                p = p->left;
            }
            if ( !stk.empty() )
            {
                d = stk_depth.top();
                depth = max ( d, depth );
                p = stk.top();
                stk.pop();
                stk_depth.pop();
                p = p->right;
                d++;
            }
        }
        return depth;
    }
    int get_depth_bfs ( Node *p )
    {
        queue<Node *> q;
        queue<int> q_d;
        int d = 0;
        int depth = 0;
        q.push ( p );
        q_d.push ( d );
        while ( !q.empty() )
        {
            p = q.front();
            d = q_d.front() ;
            ++d;
            q.pop();
            q_d.pop();
            if ( p->left != NULL )
            {
                q_d.push ( d ) ;
                q.push ( p->left );
                depth = max ( depth, d );
            }
            if ( p->right != NULL )
            {
                q_d.push ( d ) ;
                q.push ( p->right );
                depth = max ( depth, d );
            }
        }
        return depth;
    }
    int get_depth_dg ( Node *p )
    {
        int depth = 0;
        if ( p->left != NULL )
        {
            depth = max ( depth, get_depth_dg ( p->left ) + 1 );
        }
        if ( p->right != NULL )
        {
            depth = max ( depth, get_depth_dg ( p->right ) + 1 );
        }
        return depth;
    }
    Node *root;
};
int main()
{
    BinarySearchTree<int> t;
    for ( int i = 0; i < 100; i++ )
    {
        int tmp = random() % 100000;
        //cout<<tmp;
        t.insert ( tmp );
    }
    cout << "Insert OK" << endl;
    cout << t.contains ( 4 ) << endl;
    cout << t.contains ( 2 ) << endl;
    cout << "非递归递归前序遍历:\n";
    t.travel_pre();
    cout << "\n递归前序遍历\n";
    t.travel_dg_pre();
    cout << "\n递归中序遍历\n";
    t.travel_dg_in();
    cout << "\n非递归递归中序遍历:\n";
    t.travel_in();
    cout << "\n递归后序遍历\n";
    t.travel_dg_suf();
    cout << "\n非递归递归后序遍历:\n";
    t.travel_suf();
    cout << "\n递归求的树的高度\n";
    cout << t.get_depth_dg();
    cout << "\n非递归dfs求的树的高度\n";
    cout << t.get_depth_dfs();
    cout << "\n非递归bfs求的树的高度\n";
    cout << t.get_depth_bfs();
}

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115773.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • pycharm专业版下载安装教程_pycharm2021专业版安装教程

    pycharm专业版下载安装教程_pycharm2021专业版安装教程Pycharm官网地址(下载):https://link.zhihu.com/?target=https%3A//www.jetbrains.com/pycharm/download/other.html有各种不同版本的Pycharm供下载,本文选择Pycharm专业版下载,建议下载2020.1.5版本.安装教程下载完成之后,就按照步骤开始安装了,点击Next:我选择安装在F盘,因为C盘太占用空间了,会比较卡,点击Next:一定要选着添加到环境变量中,不然后面还要手动配置环境变量,比较麻烦,

  • 业务安全(逻辑漏洞)

    业务安全(逻辑漏洞)文章目录业务安全概述黑客攻击的目标业务安全测试流程测试准备业务调研业务建模业务流程梳理业务风险点的识别开展测试撰写报告业务数据安全商品支付金额篡改前端JS限制绕过验证请求重放测试业务上限测试商品订购数量篡改damiCMSV5.1为例密码找回安全验证码客户端回显测试验证码暴力破解Response状态值修改测试Session覆盖弱token设计缺陷测试密码找回流程绕过测试接口参数账号修改metinfoV4.0为例业务安全概述近年来,随着信息化技术的迅速发展和全球一体化进程的不断加快,计算机和网

  • 学习记录03(网页挂马)

    学习记录03(网页挂马)网页挂马将木马程序上传到网站,使用木马生成器生成一个网马,放到网页空间,在添加代码使木马在网页打开时运行常见的几种方式将木马伪装成页面元素,木马被浏览器自动加载到本地利用脚本运行的漏洞下载木马利用脚本运行的漏洞释放隐含在网页脚本中的木马将木马伪装成缺失的组件。或和缺失的组件绑在一起(flash播放插件等)通过脚本运行调用某些com组件,利用其漏洞下载木马在渲染页面内容的过程中…

  • linux内核 recvfrom,Linux系统调用– recv/recvfrom 函数详解

    linux内核 recvfrom,Linux系统调用– recv/recvfrom 函数详解Linux系统调用–recv/recvfrom函数详解功能描述:从套接字上接收一个消息。对于recvfrom,可同时应用于面向连接的和无连接的套接字。recv一般只用在面向连接的套接字,几乎等同于recvfrom,只要将recvfrom的第五个参数设置NULL。如果消息太大,无法完整存放在所提供的缓冲区,根据不同的套接字,多余的字节会丢弃。假如套接字上没有消息可以读取,除了套接字已被设置为非阻…

  • {style}/index_article.htm {style}表示什么意思啊

    {style}/index_article.htm {style}表示什么意思啊

  • 基于Apache的反向代理服务器

    基于Apache的反向代理服务器众所周知Apache是目前最优秀的HTTP服务器。实际上它不仅能当作服务器使用,也能够被用来架设代理服务器。本文就如何使用Apache架设HTTP代理服务器进行说明。本文将基于Win32版的Apache2.0.47进行说明。以前的Apache1.x版配置方法稍有不同,但这里不作说明。 首先是Apache的安装。从http://www.apache.org上下载Apache的安装

    2022年10月20日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号