数据结构关于二叉树遍历的一道题 在线等~

问题描述

数据结构关于二叉树遍历的一道题 在线等~

利用栈的基本操作写出先序遍历二叉树的非递归算法
要求进栈的元素最少，

并指出下列二叉树中需进栈的元素。

这是答案：

根据上述代码，

（1）左子树lchild不需要入栈吗?

（2）入栈顺序是什么？

（3）最后一行代码 if (top>0) bt=s[top--] 是什么意思？

（4）如果是中序或后序，入栈顺序又是什么？

谢谢大神们啦~~ O(∩_∩)O

解决方案

3
if (top>0) bt=s[top--]
出栈。取出top位置的元素，并且堆栈往后收缩一个。
4
中序需要将父节点入栈
后序不需要堆栈

解决方案二：

（1）不需要，因为它永远是最先访问，相当于入栈后立刻就弹出了。所以不需要
（2）需要将当前节点两个子节点入栈，每次出栈的时候再压入它的子节点。

时间： 2024-11-03 04:13:49

数据结构关于二叉树遍历的一道题 在线等~的相关文章

数据结构例程——二叉树遍历的非递归算法

本文是数据结构基础系列(6):树和二叉树中第11课时二叉树遍历非递归算法的例程. [二叉树遍历的非递归算法] 实现二叉树的先序.中序.后序遍历的非递归算法,并对用"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"创建的二叉树进行测试. 请利用二叉树算法库. ［参考解答］(btreee.h见算法库) #include <stdio.h> #include "btree.h" void PreOrder1(BTNode *b) {

数据结构例程——二叉树遍历的递归算法

本文是数据结构基础系列(6):树和二叉树中第10课时二叉树的遍历的例程. [二叉树遍历的递归算法] 实现二叉树的先序.中序.后序遍历的递归算法,并对用"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))"创建的二叉树进行测试. 请利用二叉树算法库. ［参考解答］(btreee.h见算法库) #include <stdio.h> #include "btree.h" void PreOrder(BTNode *b) //先序遍历的递

@数据结构大神：递归实现二叉树遍历，图示行为什么错?

问题描述 @数据结构大神:递归实现二叉树遍历,图示行为什么错? # include<stdio.h> # include<stdlib.h> # include<malloc.h> # define Max_Size 2 typedef struct Node{ int data; struct Node *Lchild; struct Node *Rchild; }BiTNode,*BiTree; int x,k=0,n=0; void CreateBiTree(Bi

二叉树 层序遍历-C++ 数据结构、二叉树、层序遍历问题

问题描述 C++ 数据结构.二叉树.层序遍历问题 代码结构如下: template class CirQueue... // 栈类: template struct BiNode{ // 节点类: T data; BiNode *lchild, * rchild; }; template class BiTree.... // 二叉树类: ? template void BiTree::leverOrder( ) { // 层序遍历: if( root == NULL ) { cout<<&q

@数据结构大神：递归实现二叉树遍历，46、477行为什么错?

问题描述 @数据结构大神:递归实现二叉树遍历,46.477行为什么错? # include<stdio.h> # include<stdlib.h> # include<malloc.h> # define Max_Size 2 typedef struct Node{ int data; struct Node *Lchild; struct Node *Rchild; }BiTNode,*BiTree; int x,k=0; void CreateBiTree(Bi

@数据结构大神：递归实现二叉树遍历，38行为什么错?

问题描述 @数据结构大神:递归实现二叉树遍历,38行为什么错? # include<stdio.h> # include<stdlib.h> # include<malloc.h> # define Max_Size 3 typedef struct Node{ int data; struct Node *Lchild; struct Node *Rchild; }BiTNode,*BiTree; int x,k=0; void CreateBiTree(BiTree

实现二叉树以及二叉树遍历数据结构

本文讲的是实现二叉树以及二叉树遍历数据结构, Swift 算法俱乐部 是一个致力于使用 Swift 来实现数据结构和算法的一个开源项目. 每个月,我和 Chris Pilcher 会在俱乐部网站上开建一个教程,来实现一个炫酷的数据结构或者算法.如果你想要去学习更多关于算法和数据结构的知识,请跟随我们的脚步吧. 在这个教程里面,你将学习到关于二叉树和二叉搜索树的知识.二叉树的实现首先是由 Matthijs Hollemans 实现的,而二叉搜索树是由 Nico Ameghino 实现的. 提示: 

数据结构例程——用二叉树遍历思想解决问题

本文是数据结构基础系列(6):树和二叉树中第10课时二叉树的遍历的例程. [利用二叉树遍历思想解决问题](请利用二叉树算法库) 假设二叉树采用二叉链存储结构存储,分别实现以下算法,并在程序中完成测试: (1)计算二叉树节点个数: (2)输出所有叶子节点: (3)求二叉树b的叶子节点个数 (4)设计一个算法Level(b,x,h),返回二叉链b中data值为x的节点的层数. (5)判断二叉树是否相似(关于二叉树t1和t2相似的判断:①t1和t2都是空的二叉树,相似:②t1和t2之一为空,另一不为空

举例讲解C语言程序中对二叉树数据结构的各种遍历方式_C 语言

二叉树遍历的基本思想 二叉树的遍历本质上其实就是入栈出栈的问题,递归算法简单且容易理解,但是效率始终是个问题.非递归算法可以清楚的知道每步实现的细节,但是乍一看不想递归算法那么好理解,各有各的好处吧.接下来根据下图讲讲树的遍历. 1.先序遍历:先序遍历是先输出根节点,再输出左子树,最后输出右子树.上图的先序遍历结果就是:ABCDEF  2.中序遍历:中序遍历是先输出左子树,再输出根节点,最后输出右子树.上图的中序遍历结果就是:CBDAEF 3.后序遍历:后序遍历是先输出左子树,再输出右子树,最后