• 用递归先序算法建立二叉树。要求通过键盘输入二叉树的先序遍历顺序从而建立一棵二叉树。利用实现一棵二叉树的中序非递归遍历。要求显示遍历次序。
• package tree; public class InorderTree ... * 不带的二叉树中序非递归遍历 * 1. Initialize current as root 2. While current is not NULL If current does not have left child a) Print current’s data
package tree;

public class InorderTree {

/**
* 不带栈的二叉树中序非递归遍历
* 1. Initialize current as root
2. While current is not NULL
If current does not have left child
a) Print current’s data
b) Go to the right, i.e., current = current->right
Else
a) Make current as right child of the rightmost node in current's left subtree
b) Go to this left child, i.e., current = current->left
* @param args
*/
public static void printinorderTree(TreeNode root){
TreeNode current = root;
while(current!=null){
if(current.left==null){
System.out.print(current.value+" ");
current = current.right;
}else{
TreeNode node = current.left;
while(node.right!=null&&node.right!=current){
node = node.right;
}
if(node.right==null){
node.right = current;
current = current.left;
}else{
System.out.print(current.value+" ");
node.right = null;
current = current.right;
}
}
}
}
public static void main(String[] args) {

TreeNode root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.left.right = new TreeNode(5);
printinorderTree(root);

}

}

展开全文
• #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> typedef struct treeNode { int data; struct treeNode* rChild; struct treeNode* lChild;...typedef stru...
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
typedef struct treeNode
{
int data;
struct treeNode* rChild;
struct treeNode* lChild;
}tree, *BinTree;

typedef struct
{
tree Tree[30];
int top;
}stack;

int creatTree(BinTree& pNode)
{
int ch;
scanf("%d", &ch);
if (ch == 0)
{
pNode = NULL;
}
else
{
pNode = (BinTree)malloc(sizeof(tree));
pNode->data = ch;
creatTree(pNode->lChild);
creatTree(pNode->rChild);
return 0;
}
}

void initStack(stack& s)
{
s.top = 0;
}

void push(stack& p, BinTree pNode)
{
p.Tree[p.top] = *pNode;
p.top++;
}

BinTree pop(stack& p)
{
BinTree temp = &p.Tree[p.top];
p.top--;
return temp;
}

bool isEmpty(stack p)
{
if (p.top == 0)
{
return true;
}
else
{
return false;
}
}

void inOrderTravelTree(BinTree p1,stack s)
{
initStack(s);
while (p1 || !isEmpty(s))
{
while (p1 != NULL)
{
push(s, p1);
p1 = p1->lChild;
}
if (!isEmpty(s))
{
printf("%d", pop(s)->data);
p1 = pop(s)->rChild;
}
}
}

int main()
{
stack s;
return 0;
}



展开全文
• 二叉树中序非递归遍历与递归遍历 二叉树非递归遍历用到了，可能很多同学都知道算法原理，而真的去实现这一原理可能没有那么简单，所以同学们可以多下功夫，实践出真知。 #include<stdio.h> #include<...
二叉树中序非递归遍历与递归遍历
二叉树非递归遍历用到了栈，可能很多同学都知道算法原理，而真的去实现这一原理可能没有那么简单，所以同学们可以多下功夫，实践出真知。
#include<stdio.h>
#include<stdlib.h>

typedef struct Tree {
int data;
Tree *lchild;
Tree *rchild;

}Tree;

Tree* create_binary_tree(Tree* T) {

int t;

scanf_s("%d", &t);
//T = (Tree*)malloc(sizeof(Tree));
if (t!= -1) {

T->data = t;
T->lchild = (Tree*)malloc(sizeof(Tree));
T->lchild=create_binary_tree(T->lchild);
T->rchild = (Tree*)malloc(sizeof(Tree));
T->rchild=create_binary_tree(T->rchild);

}
else { T = NULL; }
return T;

}

void middle_order(Tree* T) {
if (T) {
middle_order(T->lchild);
printf("%d ", T->data);

middle_order(T->rchild);
}
}

typedef struct stack {
Tree * a[50];
int top=0;

}stack;
void instack(stack & s,Tree * data) {
s.a[s.top] = data;
s.top++;
}
int empty(stack &s) {
if (s.top == 0) {
return 1;
}
else return 0;
}
Tree* exstack(stack &s) {
if (!empty(s))
s.top--;
return s.a[s.top];
}

void middle_f(Tree* T) {
Tree* t = T;
stack s;
//instack(s,t);
//printf("%d", s.top);
//printf("%d", empty(s));
while (!empty(s))
if (t) {
instack(s, t);
t = t->lchild;
}
else {
t = exstack(s);
printf("%d ", t->data);
t = t->rchild;
}
}

int main() {
Tree* T = NULL;
T = (Tree*)malloc(sizeof(Tree));
T=create_binary_tree(T);
//printf("%d ", T);
/*printf("%d ", T->lchild);
printf("%d ", T->rchild);*/
middle_order(T);
middle_f(T);
return 0;

}




展开全文
• 中序非递归算法 首先我们初始化一个，让根指针进栈。因为是中序遍历，所以我们首先要找到树的最左边结点，代码标记1完成的就是这个任务。那么代码标记1循环停止的条件不满足时，这个时候GetTop(S,p)得到的指针p是...
中序非递归算法
首先我们初始化一个栈，让根指针进栈。因为是中序遍历，所以我们首先要找到树的最左边结点，代码标记1完成的就是这个任务。那么代码标记1循环停止的条件不满足时，这个时候GetTop(S,p)得到的指针p是空的，因为到达最左边了，p->lchild是空，故我们需要把这个进栈的空指针给Pop掉，这是代码标记2的作用。
   下面是关键一步了，我们需要访问当前栈顶结点了。Pop(S,p)删除栈顶结点并赋给p，然后Visit函数代表我们要对这个结点进行的 操作，这是代码标记4的作用。至于代码标记5就很明显了，将右结点进栈，重新进行这个操作，即：先找最左边结点。。。。

我们再用一个实例来捋一遍：

根据咱们的代码，第一遍循环：首先会找到B结点，执行visit，然后C进栈，此时栈里有A，C两个结点，第二遍循环：然后找到C结点，C出栈执行visit，然后右结点为空，进栈，第三遍循环：然后由于这个栈顶元素是空的，Pop掉，此时栈不空，还剩A，出栈，执行visit，D进栈，然后第四遍循环：D出栈，E进栈，E的左结点为空，进栈，然后出栈，E再出栈，执行visit，然后E的右空结点进栈，第五次循环：空结点出栈然后为空，pop掉之后，再出栈D，执行visit，然后F进栈，第六次循环：F的空结点进栈，被pop掉，F出栈，然后执行visit，F的空结点进栈，第七次循环：然后因为两次栈不为空，循环结束。

方法一：
//中序遍历
void InOrderWithoutRecursion1(BTNode* root)
{
//空树
if (root == NULL)
return;
//树非空
BTNode* p = root;
stack<btnode*> s;
while (!s.empty() || p)
{
//一直遍历到左子树最下边，边遍历边保存根节点到栈中
while (p)
{
s.push(p);
p = p->lchild;
}
//当p为空时，说明已经到达左子树最下边，这时需要出栈了
if (!s.empty())
{
p = s.top();
s.pop();
cout << setw(4) << p->data;
//进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
p = p->rchild;
}
}
}</btnode*>

方法二：
//中序遍历
void InOrderWithoutRecursion2(BTNode* root)
{
//空树
if (root == NULL)
return;
//树非空
BTNode* p = root;
stack<btnode*> s;
while (!s.empty() || p)
{
if (p)
{
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
s.pop();
cout << setw(4) << p->data;
p = p->rchild;
}
}
}</btnode*>

方法三：
public void InOrderWithoutRecursion(TreeNode T){

Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p;
while(T!=null||!stack.empty()){

while(T!=null){             //将结点压进栈中
stack.push(T);
T = T.lchild;
}

if(!stack.empty()){         //将栈中的结点弹出
p = stack.peek();
stack.pop();
System.out.println(p.data);
T = p.rchild;
}
}

}



展开全文
• 那麽我们今天的中序非递归又是怎末做到的呢？ 首先，我们先看看中序遍历的规律，分析思路才能更方便写代码 如上图所示的二叉树，我们都知道中序遍历是：左子树----根节点----右子树。遍历结果为：3 2 1 5 4 6 ...
• 不借助非递归中序遍历算法) 三叉链表类型定义： typedef struct TriTNode { TElemType data; struct TriTNode *parent, *lchild, *rchild; } TriTNode, *TriTree; 思路为：1 先向左走到尽头，访问了最左结点 2 ...
• 前序、中序、后序的非递归遍历中，要数后序最为麻烦，如果只在中保留指向结点的指针，那是不够的，必须有一些额外的信息存放在中。 方法有很多，这里只举一种，先定义结点的数据结构 typedef struct{Node * p;...
• 创建2.创建一个指针p，辅助遍历3.左子树循环入栈，直到最后一个结点没有左孩子4.读栈顶，出栈5.p指向p的右孩子void InOrderUncursionTravere(BiTree T) { BiTNode *stack[Maxsize]; //定义一个 int top = -1; ...
• 二叉树的递归算法虽然简单，但是会导致时间复杂度比较高，下面给大家带来用实现的二叉树非递归算法首先定义好二叉树，和元素类型为二叉树的typedef struct BiTNode{ TElemType data; struct BiTNode *lchild, ...
• 一，二叉树的中序非递归遍历（借助顺序实现） 1.完整代码 #include<iostream> #include<malloc.h> using namespace std; #define TElemType int #define TRUE 1 #define FALSE 0 #define OK 1 #...
• void intraverse(tree t)//中序非递归遍历 { tree t1; stack *s; initstack(s); while(t||getTop1(s,t1)) { if(t) { push1(s,t); t=t->lch; } else { pop1(s,t); printf("%d ",t->data);...
• 二叉树中序非递归遍历算法： 先将左子树放进中，无左子树时出栈，从右子树开始，继续对右子树循环。 代码如下: void inOrder2(BinTree *root) //非递归中序遍历 2 { 3 stack<BinTree*> s; 4 ...
• 基本思路： 1. 开始根节点入栈 2. 循环执行如下操作：如果栈顶结点左孩子存在...3. 当空且遍历指针为空时算法结束 void inorderNonrecursion(BTNode *bt) { if (bt != NULL) { BTNode *Stack[maxsize]; ...
• #include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef char datatype; /*定义二叉树的数据结构*/ typedef struct BiTreeNode .../*定义一个用于非递归存储节点—的数据结构*/
• //若使用非递归且不用来进行中序遍历，则需要parent指针作为辅助 node1->parent = node2; node2->parent = node4; node3->parent = node4; node5->parent = node6; node6->parent = node8; node7->...
• 中序非递归遍历： 算法1：（1）从根结点开始，当前结点存在或者不为空进入循环  （2）当前结点进栈，进入其左子树，重复此操作，直到当前结点为空； （3）若不为空，则退，输出当前结点，进而访问退结点...
• 之前写过二叉树的递归遍历的三种情况，很简单的讲解，很简单的代码就能实现，因为二叉树的很多操作都基于二叉树这个自然的递归...的空间通常也只有几兆大小而已，总有一天会用完，所以就需要通过非递归的方式来解决这
• 需要使用，算法如下：1 若根节点为空，判断栈顶是否为空，非空出栈访问右子树。 为空则结束 向左走，如果左子树非空，则根节点入栈，访问左子树 如果左子树为空，打印，判断右子树2  右子树非空，访问右...
• void InOrder(pBTNode pT)//中序遍历 { if (pT) { InOrder(pT->pLchild); Visit(pT); InOrder(pT->pRchild); } } void PostOrder(pBTNode pT)//后序遍历 { if (pT) { PostOrder(pT->pLchild); ...
• 一、实验目的 ...3、采用非递归的编程方法，分别统计二叉树的节点个数、度为1、度为2和叶子节点的个数，以及数据值的最大值和最小值。 4、（选作内容）试编写按层次顺序遍历二叉树的算法。参考算法思想：
• cout元素按照中序非递归输出为"; InOrderTraverse_non(T); cout; break; case 5: cout元素按照后序递归输出为"; PostOrderTraverse(T); cout; break; case 6: cout二叉树的深度为"; d=Depth( ...
• //void InOrder_NoUsingStack(Tree T)//三叉链表非递归栈中序遍历 //这个函数代码思想是看别人的，自己写不出来 #include<iostream> using namespace std; #define TElemType double typedef struct TNode {...
• 利用的方法来遍历 先访问将根结点和左子树根结点压栈，然后不断访问左子树，直到NULL，再访问左子树下的右子树，遇到NULL，就出栈。大类的右子树和左子树差不多思路如下图： 代码#include #include typedef ...
• 由于c语言没有c++的STL库，我们无法借助c++的stack库实现二叉树的非递归遍历，但是，我们完全可以自己打造一个c语言版的stack库。本篇博文就是借助我们之前在的链式 存储这篇博文实现的程序。当然，你也可以把它...
• 给定一个二叉树，返回它的中序遍历。...非递归算法：利用实现递归到非递归的转换 递归的本质：先调用的函数压栈，一层一层递归调用其实就是栈顶元素（函数）不断出栈的过程 1.非递归解法 # Defini...
• 为了只用O(h)的空间，我们采用非递归迭代策略。 思路： 能往左走就往左走，边走边入栈，直到不能走，弹出里元素往右走，重复之前操作。 /** * Definition for a binary tree node. * struct TreeNode { * ...
• 一、二叉树的遍历 二叉树的遍历分为先序遍历，... 递归方式比较简单和常见，非递归采用来实现 二、代码：  二叉树的定义：  /** * @author 作者 : xcy * @version 创建时间：2016年11月20日 下午8:21:03 *

...