文档章节

循环遍历二叉树

Jansens
 Jansens
发布于 2016/10/25 15:14
字数 353
阅读 21
收藏 0

前序遍历 

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 << " ";
}

© 著作权归作者所有

Jansens
粉丝 9
博文 53
码字总数 128340
作品 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

没有更多内容

加载失败,请刷新页面

加载更多

新手转行学java难吗?新手学java需要注意的6个方面!

新手转行在成都学java到底难不难,对于这个问题,我们专门做过一个调查,超过1000名已经在职的java从业者,其中有80%的程序员觉得学java不难,20%的程序员觉得前期有点难,其中对于50%自学的...

Java领航员
55分钟前
3
0
动态规划-硬币问题分析

什么是动态规划 上次对动态规划已经有了个大概的分析。引用维基百科的话就是: dynamic programming is a method for solving a complex problem by breaking it down into a collection of...

AI考拉
今天
2
0
谈谈lucene的DocValues特性之SortedSetDocValuesField

SortedSetDocValuesField与SortedDocValuesField类似但它是一键多值的(注意:lucene的数据模型是支持一键多值的即key-values模型),lucene在实现时会判断是一键一值还是多值,如果单值就调...

FAT_mt
今天
1
0
生产者消费者模式

//尚学堂视频里,不是完整的 public class Movie { /** * 共同的资源 */ private String pic; //flay为true生产,false消费 private boolean flag=true; public synchronized void play(Str......

南桥北木
今天
1
0
使用阿里云镜像安装kubernetes

参考阿里云镜像 https://opsx.alibaba.com/mirror?lang=zh-CN 系统: CentOS / RHEL / Fedora cat <<EOF > /etc/yum.repos.d/kubernetes.repo[kubernetes]name=Kubernetesbaseurl=https......

北漂的我
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部