先序遍历二叉树的递归实现与非递归实现深入解析

以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下
 

1、先序遍历二叉树  递归实现
思想:若二叉树为空,返回。否则
1)遍历根节点;
2)先序遍历左子树;
3)先序遍历右子树;

代码:

复制代码 代码如下:

template<typename elemType>
void PreOrder(nodeType<elemType> *root) 

    if(root==NULL) 
        return ; 
    visit(root->data); // visit the data
    PreOrder(root->lchild); //递归调用,先序遍历左子树 
    PreOrder(root->rchild); //递归调用,先序遍历右子树 


2、先序遍历二叉树 非递归实现
思想:二叉树的非递归先序遍历,先序遍历思想:先让根进栈,只要栈不为空,就可以做弹出操作, 每次弹出一个结点,记得把它的左右结点都进栈,记得右子树先进栈,这样可以保证右子树在栈中总处于左子树的下面。

前序遍历二叉树的非递归算法思想
建立栈 Stack;
t 指向根;
当 t 不空 或 Stack 不空时反复做:
      若 t 不空,访问t,t 入 栈;t 指向左子女;
      否则:出栈顶元素到 t 中;
      t 指向右子女;
结束

复制代码 代码如下:

void PreOrder_Nonrecursive(BinaryTree T)     //先序遍历的非递归   

    if(!T) return ;   
    stack<BinaryTree> s; 
    s.push(T); 
    while(!s.empty()) 
    { 
        BinaryTree temp = s.top(); 
        visit(temp->data); 
        s.pop(); 
        if(temp->rchild) 
            s.push(temp->rchild); 
        if(temp->lchild) 
            s.push(temp->lchild); 
    } 

时间: 2024-10-03 16:46:51

先序遍历二叉树的递归实现与非递归实现深入解析的相关文章

中序遍历二叉树-二叉树的非递归操作。。

问题描述 二叉树的非递归操作.. 如何用栈实现二叉树的非递归操作,越详细越好,谢谢各位啦.一定要详细哦 解决方案 void inOrder2(BinTree *root) //非递归中序遍历 { stack<BinTree*> s; BinTree *p=root; while(p!=NULL||!s.empty()) { while(p!=NULL) { s.push(p); p=p->lchild; } if(!s.empty()) { p=s.top(); cout<<

先序遍历二叉树的递归实现与非递归实现深入解析_C 语言

1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点:2)先序遍历左子树:3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visit(root->data); // visit the data    PreOrder(ro

中序遍历二叉树得到的序列是有序还是无序的?

问题描述 中序遍历二叉树得到的序列是有序还是无序的? 中序遍历二叉树得到的序列是有序还是无序的?中序遍历二叉树得到的序列是有序还是无序的? 解决方案 中序遍历首先遍历左子树,然后访问根结点,最后遍历右子树.在遍历左.右子树时,仍然先遍历左子树,再访问根结点,最后遍历右子树.排序二叉树的左边<中间<右边,所以是有序的.

递归形式与非递归形式的斐波那契数列的用法分析_C 语言

复制代码 代码如下: <SPAN style="FONT-SIZE: 32px">采用递归形式和非递归形式实现斐波那契数列</SPAN> 复制代码 代码如下: #include "stdafx.h"#include <iostream>using namespace std;//递归形式的斐波那契数列int fibonacciRecursion(int n){ if (n == 1 || n ==2) {  return 1; }

归并排序的递归实现与非递归实现代码_C 语言

归并排序归并排序是建立在归并操作上的一种有效的排序算法.该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.值得注意的是归并排序是一种稳定的排序方法.将已有序的子序列合并,得到完全有序的序列:即先使每个子序列有序,再使子序列段间有序.若将两个有序表合并成一个有序表,称为2-路归并.算法描述归并操作的工作原理如下:第一步:申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列第二步:设定两个指针,最初位置分别为两个已经排序序列的起始位置第三步:比较两个指针

二叉树的存储方式以及递归和非递归的三种遍历方式

树的定义和基本术语 树(Tree)是n(n>=0)个结点的有限集T,T为空时称为空树,否则它满足如下两个条件:   (1)有且仅有一个特定的称为根(Root)的结点:   (2)其余的结点可分为m(m>=0)个互不相交的子集T1,T2,T3-Tm,其中每个子集又是一棵树,并称其为子树(Subtree). 树形结构应用实例: 1.日常生活:家族谱.行政组织结构:书的目录 2.计算机:资源管理器的文件夹:     编译程序:用树表示源程序的语法结构:     数据库系统:用树组织信息:     分

C语言二叉树的非递归遍历实例分析_C 语言

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

二叉树的非递归先序,中序,后序遍历

#include<iostream> #include<cstring> #include<cstdio> #include<algorithm> #include<stack> using namespace std; struct Tree{ int x; Tree *lchild, *rchild; Tree(){ lchild = rchild = NULL; } }; typedef Tree* pT; void buildT(pT &

二叉树递归和非递归遍历

二叉树是一种非常重要的数据结构,很多其他数据机构都是基于二叉树的基础演变过来的.二叉树有前.中.后三种遍历方式,因为树的本身就是用递归定义的,因此采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用栈来模拟实现(递归也是用栈实现的).下面先简要介绍三种遍历方式的递归实现,再详细介绍三种遍历方式的非递归实现. 一.三种遍历方式的递归实现(比较简单,这里不详细讲解) 1.先序遍历--按照"根节点-左孩子-右孩子"的顺序进行访问. vo