文档章节

循环遍历二叉树

梦想游戏人
 梦想游戏人
发布于 2016/10/05 19:01
字数 353
阅读 486
收藏 13

前序遍历



struct Node
{
	Node*left;
	Node*right;
	int data;
	Node(){ func; }
};



Node* create(Node*p, int depth)
{
	if (p && depth)
	{
		p->left = new Node;
		p->right = new Node;
		p->data = depth;
		create(p->left, depth - 1);
		create(p->right, depth - 1);


	}
	if (!depth)
	{
		p->left = nullptr;
		p->right = nullptr;
		p->data = depth;

	}

	return p;

}



void print1(Node*p)
{
	if (p)
	{
		cout << p->data << " ";
		print1(p->left);
		print1(p->right);
	}
}

void print2(Node*head)//利用stack 模拟函数调用过程 来遍历
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);
			cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();

			if (pp->right && pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);
			cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();

			if (pp->right
				&& pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}

}



int main()
{

	Node* head = new Node;
	create(head, 2);

	head->data = 10;
	head->left->data = 6;
	head->right->data = 14;

	head->left->left->data = 4;
	head->left->right->data = 8;

	head->right->left->data = 12;
	head->right->right->data = 16;

	print1(head);//递归遍历
	cout << endl;
	print2(head);//循环遍历






	system("pause");
	return 0;
}

 

中序


void print2(Node*head)
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);
		//	cout << p->data << " ";
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
			cout << pp->data << " ";

			if (pp->right && pp != head  )
			{
				
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);
		
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
			cout << pp->data << " ";
			if (pp->right&& pp != head)
			{
				cout << pp->right->data << " ";
			}
			s.pop();
		}

	}

}

后序


void print2(Node*head)
{
	stack<Node* > s;

	Node*p = head;

	{
		while (p)
		{
			s.push(p);
	
			p = p->left;		
		}

		while (!s.empty())
		{
			Node*pp = s.top();	
			if (pp->right && pp != head  )
			{
				
				cout << pp->right->data << " ";
			}	
			if ( pp != head)
			cout << pp->data << " ";
			s.pop();
		}

	}


	{
		p = head->right;

		while (p)
		{
			s.push(p);
			p = p->left;
		}

		while (!s.empty())
		{
			Node*pp = s.top();
		
			if (pp->right&& pp != head)
			{
				cout << pp->right->data << " ";
			}	
			cout << pp->data << " ";
			s.pop();
		}

	}
	cout << head->data << " ";
}

 

© 著作权归作者所有

上一篇: 排行榜的实现
下一篇: 倒序打印链表
梦想游戏人
粉丝 38
博文 445
码字总数 127977
作品 0
成都
私信 提问
Tommy Yang/BinaryTree

二叉树(Binary Tree)定义: 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二...

Tommy Yang
2017/03/31
0
0
趣味算法思想 -- 递归与二叉查找树(BST)

前言 上篇文章中,我们已经了解了生成一棵BST的过程,遗留的问题是如何遍历里面的节点。这一篇文章,我们使用递归的方法来解决一下这个问题,顺便探讨与二叉树相关的算法递归问题。 递归函数...

大灰狼的小绵羊哥哥
03/02
0
0
12.遍历二叉树与二叉树的建立

一、遍历二叉树 1.定义 二叉树的遍历(travering binary tree)是指从根结点出发。依照某种次序依次訪问二叉树中的全部结点,使得每一个结点被訪问一次且仅被訪问一次。 2.前序遍历 (1)规则:若...

技术mix呢
2017/12/01
0
0
非递归遍历二叉树的四种策略-先序、中序、后序和层序

遍历二叉树的递归算法,是比较容易理解的,但是非递归的循环算法不是很容易一眼看穿。下面的五个算法是参考严蔚敏的《数据结构》和USTC的张昱老师的讲义后,写下来的,部分有改动。 先序遍历...

晨曦之光
2012/04/24
274
0
Leetcode 二叉树解题报告

1. Binary Tree Preorder Traversal Description Given a binary tree, return the preorder traversal of its nodes' values. Example: Input: [1,null,2,3] 1 2 / 3 Output: [1,2,3] Analy......

BookThief
2018/07/29
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Redis缓存穿透、缓存雪崩和缓存击穿

Redis缓存穿透、缓存雪崩 缓存雪崩,是指在某一个时间段,缓存集中过期失效。 产生雪崩的原因之一,比如在写本文的时候,马上就要到双十二零点,很快就会迎来一波抢购,这波商品时间比较集中...

architect刘源源
28分钟前
10
1
ArrayList源码分析

一、核心变量 // 序列化ID private static final long serialVersionUID = 8683452581122892189L; // 默认初始化容量 private static final int DEFAULT_CAPACITY = 10; ......

星爵22
37分钟前
3
0
++a a++的再次理解

public class Test { //// public static void main(String[] args) throws InterruptedException { // TODO Auto-generated method stub int a=1; int b=2; int c; int d; c=......

南桥北木
37分钟前
3
0
整合Spring和SpringMVC

1.Spring容器和SpringMVC容器的关系 Spring容器是一个父容器,SpringMVC容器是一个子容器,它继承自Spring容器。因此,在SpringMVC容器中,可以访问到Spring容器中定义的Bean,而在Spring容器...

薛小二
37分钟前
3
0
递归实现后序遍历二叉树

问题描述 从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树(以先序来建立)并对其进行后序遍历,然后将遍历结果打印输出。要求采用递归方法实现。 解题思路 递归实现 程序实现 ...

niithub
今天
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部