二叉树的建立、销毁、各种遍历(递归、非递归)

简介:

二叉树的基本操作,都使用递归:

复制代码
//二叉树   
class Node  
{  
public:  
    char data;  
    Node *left;  
    Node *right;  
    Node():data(' '),left(NULL),right(NULL){}  
    Node(char ch):data(ch),left(NULL),right(NULL){}  
};  
  
  
//广义表建立二叉树,输入:A(B(D,E(G,)),C(,F))*   
void CreateBinTree(Node* & Root,char *str)  
{  
    stack<Node*> s;  
    Root=NULL;  
    Node* p=NULL,*t=NULL;  
    int k,i=0;  
    while(str[i])  
    {  
        switch(str[i])  
        {  
            case '(': s.push(p); k=1; break;  
            case ')': t=s.top(); s.pop(); break;  
            case ',': k=2; break;  
            default:  
            p=new Node(str[i]);  
            if(Root==NULL) Root=p;  
            else if(k==1)  
            {  
                t=s.top(); t->left=p;  
            }  
            else  
            {  
                t=s.top(); t->right=p;  
            }  
        }  
        ++i;  
    }  
}  
  
//递归先序遍历   
void preOrderTraverse(Node *p)  
{  
   if(p != NULL)  
   {  
       cout<<p->data;  
       preOrderTraverse(p->left);  
       preOrderTraverse(p->right);  
   }  
}  
  
//求节点个数   
int Size(Node* root)  
{  
    if(root == NULL) return 0;  
    return 1 + Size(root->left) + Size(root->right);  
}  
  
//求树的高度   
int TreeDepth(Node* t)  
{  
    int hl,hr,h;  
    if(t != NULL)  
    {  
        hl = TreeDepth(t->left);  
        hr = TreeDepth(t->right);  
        h = hl>hr? hl:hr;  
        return h+1;  
    }  
    return 0;  
}  
  
//销毁二叉树   
void freeTree(Node*& p)  
{  
    if(p->left != NULL)  
        freeTree(p->left);  
    if(p->right != NULL)  
        freeTree(p->right);  
    delete(p);  
}  
复制代码

二叉树的各种遍历:

复制代码
//输出第level层的所有节点(从左到右),成功返回1   
int PrintNodeAtLevel(Node* root,int level)  
{  
    if(!root || level<0)  return 0;  
    if(level==0)  
    {  
        cout<<root->data<<" ";  
        return 1;  
    }  
    return PrintNodeAtLevel(root->left,level-1)+PrintNodeAtLevel(root->right,level-1);  
}  
  
//层次遍历二叉树,使用树的高度   
void PrintNodeByLevel(Node* root,int depth)  
{  
    for(int level=0; level<depth; level++)  
    {  
        PrintNodeAtLevel(root,level);  
        cout<<endl;  
    }  
}  
//层次遍历二叉树,不使用树的高度   
void PrintNodeByLevel(Node* root)  
{  
    for(int level=0; ;level++)  
    {  
        if(!PrintNodeAtLevel(root,level)) break;  
        cout<<endl;  
    }  
}  
  
/*层次遍历树算法: 
        (1)初始化队列为空 
        (2)若二叉树为空,直接返回 
        (3)将根节点指针放到队列中 
        (4)若队列非空,则重复以下操作: 
          1.队头元素出队并访问该元素 
          2.若该节点左孩子非空,则左孩子节点指针入队 
          3.若该节点右孩子非空,则右孩子节点指针入队 
*/  
void layerOrder(Node* t)//层次遍历树   
{  
    queue<Node*> q;  
    if(t==NULL) return;  
    q.push(t);  
    while(!q.empty())  
    {  
        Node* p=q.front();  
        q.pop();  
        cout<<p->data<<" ";  
        if(p->left) q.push(p->left);  
        if(p->right) q.push(p->right);  
    }  
}  
  
//层次遍历二叉树   
void LevelOrder(Node* root)  
{  
    if(root==NULL) return;  
    vector<Node*> v;  
    v.push_back(root);  
    int cur=0;  
    int last=1;  
    while(cur<v.size())  
    {  
        last=v.size();  
        while(cur<last)  
        {  
            cout<<v[cur]->data<<" ";  
            if(v[cur]->left) v.push_back(v[cur]->left);  
            if(v[cur]->right) v.push_back(v[cur]->right);  
            cur++;  
        }  
        cout<<endl;  
    }  
}  
  
//非递归先序遍历树   
void preOrder(Node* root)  
{  
    stack<Node*> s;  
    Node* p=NULL;  
    if(root==NULL) return;  
    s.push(root);  
    while(!s.empty())  
    {  
        p=s.top(); s.pop();  
        cout<<p->data<<" ";  
        if(p->right) s.push(p->right);  
        if(p->left) s.push(p->left);  
    }  
}  
  
//非递归先序遍历树   
void preOrder(Node* t)  
{  
    stack<Node*> s;  
    Node* p=t;  
    while (p!=NULL || !s.empty())  
    {  
        while (p!=NULL)  //遍历左子树   
         {  
            cout<<p->data<<" ";  
            s.push(p);  
            p=p->left;  
        }  
        if (!s.empty()) //通过下一次循环中的内嵌while实现右子树遍历   
         {  
            p=s.top();  
            s.pop();  
            p=p->right;  
        }  
     }  
}  
  
/*非递归中序遍历树算法:从根节点开始,只要当前节点存在,或者栈不为空,则重复下面操作: 
  (1)如果当前节点存在,则进栈并走左子树。 
  (2)否则退栈并访问,然后走右子树。 
*/  
void inOrder(Node* t)  
{  
    stack<Node*> s;  
    Node* p=t;  
    while(p||!s.empty())  
    {  
        if(p)  
        {  
            s.push(p);  
            p=p->left;  
        }  
        else  
        {  
            p=s.top();s.pop();  
            cout<<p->data<<" ";  
            p=p->right;  
        }  
    }  
}  
  
/*非递归后序遍历树:后序遍历,先遍历到的结点最后访问 
用两个栈,一个栈用来遍历,另一个栈保存遍历到的结点,最后一起出栈,就是后序遍历结果 
*/  
void postOrder(Node* root)  
{  
    stack<Node*> sTraverse,sVisit;  
    Node* p=NULL;  
    if(root==NULL) return;  
    sTraverse.push(root);  
    while(!sTraverse.empty())  
    {  
        p=sTraverse.top(); sTraverse.pop();  
        sVisit.push(p);  
        if(p->left) sTraverse.push(p->left);  
        if(p->right) sTraverse.push(p->right);  
    }  
    while(!sVisit.empty())  
    {  
        p=sVisit.top(); sVisit.pop();  
        cout<<p->data<<" ";  
    }  
}  
  
/*非递归后序遍历树算法:从根节点开始,只要当前节点存在,或者栈不为空,则重复下面操作: 
  (1)从当前节点开始,进栈并走左子树,直到左子树为空。 
  (2)如果栈顶节点的右子树为空,或者栈顶节点的右孩子为刚访问过的节点, 
     则退栈并访问,然后置当前节点指针为空。 
  (3)否则走右子树。 
*/  
void postOrder(Node* t)  
{  
    Node *p,*q;  
    stack<Node*> s;  
    p=t;  
    q=NULL;  
    while(p!=NULL||!s.empty())  
    {  
        while(p!=NULL)  
        {  
            s.push(p); p=p->left;  
        }  
        if(!s.empty())  
        {  
            p=s.top();  
            if((p->right==NULL) || (p->right==q))  
            {  
                cout<<p->data<<" ";  
                q=p;  
                s.pop();  
                p=NULL;  
            }  
            else p=p->right;  
        }  
    }  
}  
  
/*根节点到r节点的路径: 
后序遍历时访问到r节点时,栈中的所有的节点均为r节点的祖先,这些祖先构成根节点到r节点的路径 
*/  
void nodePath(Node* root,Node* r)  
{  
    Node *p,*q;  
    stack<Node*> s;  
    p=root;  
    q=NULL;   //q保存刚访问过的节点   
    while(p!=NULL||!s.empty())  
    {  
        while(p!=NULL)  
        {  
            s.push(p); p=p->left;  
        }  
        if(!s.empty())  
        {  
            p=s.top();  
            if( (p->right==NULL) || (p->right==q) )  
            {  
                if(p==r)  
                {  
                    while(!s.empty())  
                    {  
                        Node* t=s.top();  
                        s.pop();  
                        cout<<t->value<<" ";  
                    }  
                    return;  
                }  
                else  
                {  
                    q=p;  
                    s.pop();  
                    p=NULL;  
                }  
            }  
            else p=p->right;  
        }  
    }  
}  
复制代码
    本文转自阿凡卢博客园博客,原文链接: http://www.cnblogs.com/luxiaoxun/archive/2012/08/04/2622775.html ,如需转载请自行联系原作者
相关文章
|
数据采集 大数据 数据安全/隐私保护
掌握网络抓取技术:利用RobotRules库的Perl下载器一览小红书的世界
本文探讨了使用Perl和RobotRules库在遵循robots.txt规则下抓取小红书数据的方法。通过分析小红书的robots.txt文件,配合亿牛云爬虫代理隐藏真实IP,以及实现多线程抓取,提高了数据采集效率。示例代码展示了如何创建一个尊重网站规则的数据下载器,并强调了代理IP稳定性和抓取频率控制的重要性。
318 7
掌握网络抓取技术:利用RobotRules库的Perl下载器一览小红书的世界
|
6月前
|
存储 移动开发 小程序
校园圈子系统小程序(圈子论坛、私信聊天、资料共享、二手交易、兼职,跑腿)开源码开发/微信公众号、小程序、H5多端账号同步/搭建多城市的综合社交生活平台
基于开源技术栈构建的校园圈子系统小程序,整合社交与生活服务功能,涵盖兴趣圈子、私信聊天、资料共享、二手交易、兼职跑腿等六大核心模块。通过多端账号同步(微信公众号/小程序/H5),实现数据实时交互,满足学生群体的多元化需求。项目精准锚定校园市场,以“社交+服务”双轮驱动,提供一站式解决方案,支持快速部署与多校区运营,同时具备广告、佣金、会员等多元变现能力,是打造校园生态的理想工具。
593 2
校园圈子系统小程序(圈子论坛、私信聊天、资料共享、二手交易、兼职,跑腿)开源码开发/微信公众号、小程序、H5多端账号同步/搭建多城市的综合社交生活平台
|
7月前
RT-DETR改进策略【损失函数篇】| 通过辅助边界框计算IoU提升检测效果(Inner_GIoU、Inner_DIoU、Inner_CIoU、Inner_EIoU、Inner_SIoU)
RT-DETR改进策略【损失函数篇】| 通过辅助边界框计算IoU提升检测效果(Inner_GIoU、Inner_DIoU、Inner_CIoU、Inner_EIoU、Inner_SIoU)
364 0
RT-DETR改进策略【损失函数篇】| 通过辅助边界框计算IoU提升检测效果(Inner_GIoU、Inner_DIoU、Inner_CIoU、Inner_EIoU、Inner_SIoU)
|
存储 算法 编译器
【数据结构】C语言实现链式二叉树(附完整运行代码)
【数据结构】C语言实现链式二叉树(附完整运行代码)
265 1
JAVA并发编程ReentrantLock核心原理剖析
本文介绍了Java并发编程中ReentrantLock的重要性和优势,详细解析了其原理及源码实现。ReentrantLock作为一种可重入锁,弥补了synchronized的不足,如支持公平锁与非公平锁、响应中断等。文章通过源码分析,展示了ReentrantLock如何基于AQS实现公平锁和非公平锁,并解释了两者的具体实现过程。
|
SQL Cloud Native 架构师
深入浅出Presto:大数据查询引擎的原理与应用
【4月更文挑战第7天】Presto是高性能的分布式SQL查询引擎,专为大规模数据交互式分析设计。它采用分离式架构,内存计算和动态规划优化查询,支持跨源查询、交互式查询和ANSI SQL兼容性。应用于大数据分析、实时数据湖查询和云原生部署。Presto的灵活性和效率使其在大数据处理领域备受推崇,适合分析师、数据科学家和IT架构师使用。未来将在博客中分享更多实践和案例。
1467 1
|
存储 NoSQL 大数据
【MongoDB】GridFS机制
【4月更文挑战第2天】【MongoDB】GridFS机制
|
安全 Shell 网络安全
Git学习---Git快速入门、Git基础使用、Git进阶使用、Git服务器使用(IDEA集成GitHub、Gitee、GitLab)、GitHub Desktop客户端
Git学习---Git快速入门、Git基础使用、Git进阶使用、Git服务器使用(IDEA集成GitHub、Gitee、GitLab)、GitHub Desktop客户端
338 0
|
机器学习/深度学习 人工智能 监控
【AI 现况分析】AI 算法偏见和歧视分析
【1月更文挑战第27天】【AI 现况分析】AI 算法偏见和歧视分析
|
JavaScript API
vue element plus Calendar 日历
vue element plus Calendar 日历
279 0