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

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-09-06 16:18:40

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

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

以下是对先序遍历二叉树的递归实现与非递归实现进行了详细的分析介绍,需要的朋友可以过来参考下   1.先序遍历二叉树  递归实现思想:若二叉树为空,返回.否则 1)遍历根节点: 2)先序遍历左子树: 3)先序遍历右子树: 代码: 复制代码 代码如下: template<typename elemType> void PreOrder(nodeType<elemType> *root)  {      if(root==NULL)          return ;      visi

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

问题描述 二叉树的非递归操作.. 如何用栈实现二叉树的非递归操作,越详细越好,谢谢各位啦.一定要详细哦 解决方案 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 语言

复制代码 代码如下: <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++将二叉树转为双向链表及判断两个链表是否相交_C 语言

把二叉查找树转变成排序的双向链表例如: 转换成双向链表 4=6=8=10=12=14=16 struct BSTreeNode { int m_nValue; // value of node BSTreeNode *m_pLeft; // left child of node BSTreeNode *m_pRight; // right child of node }; 首先阐述下二叉排序树: 它首先要是一棵二元树,在这基础上它或者是一棵空树:或者是具有下列性质的二元树: (1)若左子树不空,

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

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

概率的问题:使用递归与多次试验模拟的分析_C 语言

多次枚举: 实例1 口袋中有5只红球,4只白球.随机从口袋中取出3个球,取出1个红球2个白球的概率 复制代码 代码如下: <SPAN style="FONT-SIZE: 18px"> srand( (unsigned)time( NULL ) ); int n = 0; for(int i=0; i<100000; i++) {  char x[] = {1, 1, 1, 1, 1, 2, 2, 2, 2};//5个红球用5个1表示 4个白球用4个2表示  int a

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

树的定义和基本术语 树(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