精华内容
下载资源
问答
  • 二叉树非递归

    2012-12-16 15:22:07
    二叉树非递归遍历。
  • 二叉树非递归实现

    千次阅读 2017-03-30 22:52:11
    二叉树非递归实现会比较难理解一点,不过只要理解了非递归的,那么递归的就非常好理解了。接下来进行图文详解。 C代码下载 C++代码下载 java代码下载 ( 备用地址下载)导航 1.创建二叉树 2.前序遍历二叉树 ...

    ==> 学习汇总(持续更新)
    ==> 从零搭建后端基础设施系列(一)-- 背景介绍


    二叉树非递归实现会比较难理解一点,不过只要理解了非递归的,那么递归的就非常好理解了。接下来进行图文详解。

    C代码下载
    C++代码下载
    java代码下载
    ( 备用地址下载)

    导航
    1.创建二叉树
    2.前序遍历二叉树
    3.中序遍历二叉树
    4.后序遍历二叉树
    5.层次遍历二叉树
    6.计算二叉树深度
    7.计算二叉树双分支节点数
    8.计算二叉树单分支节点数
    9.计算二叉树叶子节点数
    10.添加节点
    11.查找二叉树中的节点

    注:有一些重复的代码且多的就不重复贴出来了,需要的可以点上面的链接去下载。







    一、创建二叉树

    按照前序遍历来创建,给定一个串,其规则是空格代表空节点
    例如给定串:ABC D EF G ;
    创建步骤如下:

    1.C代码

    /*
    * function				创建二叉树(前序创建)
    * param		char* s     根据给定字符串创建	
    * return                返回二叉树的根节点
    */
    PBTree CreateBTree(char* s)
    {
    	if (!s || s[0] == '\0')  //如果s为空 则树也为空
    		return NULL;
    	Stack stack = CreateStack();  //创建一个栈
    	int i = 0;
    	// 1.先创建根节点
    	PBTree root = CreateNode(s[i++]);
    	PBTree btree = root;		//用一个临时的指针代替root,因为最后要返回root指针,所以它不能改变
    	Push(&stack,root);			//将根节点压入栈中
    	int len = _csize(s);
    	while (i < len)  
    	{
    		// 2.如果当前读到的字符不为空,并且当前节点的左孩子不存在,则创建它
    		if (s[i] != ' ' && btree->bLCExits == false)
    		{
    			btree->left = CreateNode(s[i]);	//创建左孩子
    			btree->bLCExits = true;			//左孩子存在
    			btree = btree->left;
    			Push(&stack, btree);  //入栈
    			++i;
    		}
    		// 3.如果当前读到的字符不为空,并且当前节点的右孩子不存在,则创建它
    		else if (s[i] != ' ' && btree->bRCExits == false)
    		{
    			btree->right = CreateNode(s[i]);//创建右孩子
    			btree->bRCExits = true;			//右孩子存在
    			btree = btree->right;
    			Push(&stack, btree);  //入栈
    			++i;
    		}
    		// 4.如果当前读到的字符为空,并且当前节点的左孩子不存在,则将当前节点的左孩子置为存在(空也算孩子)
    		else if (s[i] == ' ' && btree->bLCExits == false) //空节点
    			btree->bLCExits = true, ++i;  //左孩子存在
    		// 5.如果当前读到的字符为空,并且当前节点的右孩子不存在,则将当前节点的右孩子置为存在(空也算孩子)
    		else if (s[i] == ' ' && btree->bRCExits == false)
    			btree->bRCExits = true, ++i;  //右孩子存在		
    
    		// 6.回溯回去,当该节点的度为2的时候(就是左右孩子都存在的情况)
    		if (btree->bLCExits && btree->bRCExits)
    			Pop(&stack),btree = Top(&stack);
    	}
    	DestroyStack(&stack);  //最后销毁栈
    	return root;
    }
    

    2.C++代码

    /*
    * function				创建二叉树(前序创建)
    * param		char* s     根据给定串创建
    * return                无
    */
    template<typename T>
    void NonRecursionBTree<T>::Create(string s)
    {
    	if (s.empty())  //如果s为空 则树也为空
    		return ;
    	stack<Node*> st;	//创建一个栈
    	int i = 0;
    	// 1.先创建根节点
    	m_root = new Node(s[i++]);
    	Node* btree = m_root;		//用一个临时的指针代替root,因为最后要返回root指针,所以它不能改变
    	st.push(btree);				//将根节点压入栈中
    	int len = s.size();
    	while (i < len)
    	{
    		// 2.如果当前读到的字符不为空,并且当前节点的左孩子不存在,则创建它
    		if (s[i] != ' ' && btree->bLCExits == false)
    		{
    			btree->left = new Node(s[i]);	//创建左孩子
    			btree->bLCExits = true;			//左孩子存在
    			btree = btree->left;
    			st.push(btree);  //入栈
    			++i;
    		}
    		// 3.如果当前读到的字符不为空,并且当前节点的右孩子不存在,则创建它
    		else if (s[i] != ' ' && btree->bRCExits == false)
    		{
    			btree->right = new Node(s[i]);	//创建右孩子
    			btree->bRCExits = true;			//右孩子存在
    			btree = btree->right;
    			st.push(btree);  //入栈
    			++i;
    		}
    		// 4.如果当前读到的字符为空,并且当前节点的左孩子不存在,则将当前节点的左孩子置为存在(空也算孩子)
    		else if (s[i] == ' ' && btree->bLCExits == false) //空节点
    			btree->bLCExits = true, ++i;  //左孩子存在
    		// 5.如果当前读到的字符为空,并且当前节点的右孩子不存在,则将当前节点的右孩子置为存在(空也算孩子)
    		else if (s[i] == ' ' && btree->bRCExits == false)
    			btree->bRCExits = true, ++i;  //右孩子存在		
    
    		// 6.回溯回去,当该节点的度为2的时候(就是左右孩子都存在的情况)
    		if (btree->bLCExits && btree->bRCExits)
    			st.pop(), btree = st.top();
    	}
    	while (!st.empty())  //最后销毁栈
    		st.pop();
    }
    

    3.java代码

    /*
    	* function				创建二叉树(前序创建)
    	* param		String s    根据给定串创建
    	* return                无
    	*/
    	public void create(String s) {
    		if (s.isEmpty())  //如果s为空 则树也为空
    			return ;
    		Stack<Node> st = new Stack<Node>();	//创建一个栈
    		int i = 0;
    		// 1.先创建根节点
    		root = new Node(s.charAt(i++));
    		Node btree = root;		//用一个临时的指针代替root,因为最后要返回root指针,所以它不能改变
    		st.push(btree);				//将根节点压入栈中
    		int len = s.length();
    		while (i < len) {
    			// 2.如果当前读到的字符不为空,并且当前节点的左孩子不存在,则创建它
    			if (s.charAt(i) != ' ' && btree.bLCExits == false) {
    				btree.left = new Node(s.charAt(i));	//创建左孩子
    				btree.bLCExits = true;			//左孩子存在
    				btree = btree.left;
    				st.push(btree);  //入栈
    				++i;
    			}
    			// 3.如果当前读到的字符不为空,并且当前节点的右孩子不存在,则创建它
    			else if (s.charAt(i) != ' ' && btree.bRCExits == false) {
    				btree.right = new Node(s.charAt(i));	//创建右孩子
    				btree.bRCExits = true;			//右孩子存在
    				btree = btree.right;
    				st.push(btree);  //入栈
    				++i;
    			}
    			// 4.如果当前读到的字符为空,并且当前节点的左孩子不存在,则将当前节点的左孩子置为存在(空也算孩子)
    			else if (s.charAt(i) == ' ' && btree.bLCExits == false) {//空节点
    				btree.bLCExits = true;
    				++i;  //左孩子存在
    			}	
    			// 5.如果当前读到的字符为空,并且当前节点的右孩子不存在,则将当前节点的右孩子置为存在(空也算孩子)
    			else if (s.charAt(i) == ' ' && btree.bRCExits == false) {
    				btree.bRCExits = true;
    				++i;  //右孩子存在		
    			}
    				
    			// 6.回溯回去,当该节点的度为2的时候(就是左右孩子都存在的情况)
    			if (btree.bLCExits && btree.bRCExits) {
    				st.pop();
    				btree = st.peek();
    			}
    				
    		}
    		st.clear(); //最后销毁栈
    	}
    

    1).为什么要用两个标志位bLCExits和bRCExits?
    这样子比较容易找到回溯点,就是当左右两个孩子都存在了就回溯,不能根据是否为空来判断是否回溯。






    二、前序遍历二叉树
    参考出处,点击跳转

    遍历顺序是:根节点 -> 左节点 -> 右节点
    然后一个二叉树又可以分为很多子树,每一颗子树都会有根、左、右节点。

    /*
    * function				前序遍历
    * param		PBTree      root
    * return                无
    */
    void PreOrder(PBTree root)
    {
    	Stack stack = CreateStack();   //创建一个栈
    	PBTree btree = root;           //创建临时指针指向root
    	// 1. 若当前节点不为空,或者栈中元素不为空(相当于还没有遍历完所有节点)
    	while (btree || !StackIsEmpty(&stack))
    	{
    		// 2. 先遍历左子树,一直到左子树为空为止。
    		while (btree)
    		{
    			printf("%c", btree->data);
    			Push(&stack,btree);
    			btree = btree->left;
    		}
    
    		// 3.若栈中还有元素,则将当前btree赋值为它的右子树,然后再重复 1~2步骤
    		if (!StackIsEmpty(&stack))
    		{
    			btree = Top(&stack);
    			Pop(&stack);         
    			btree = btree->right;
    		}
    	}
    	printf("\n");
    }
    





    三、中序遍历二叉树
    遍历顺序是:左节点 -> 根节点 -> 右节点

    /*
    * function				中序遍历
    * param		PBTree      root
    * return                无
    */
    void InOrder(PBTree root)
    {
    	Stack stack = CreateStack();   //创建一个栈
    	PBTree btree = root;           //创建临时指针指向root
    	// 1. 若当前节点不为空,或者栈中元素不为空(相当于还没有遍历完所有节点)
    	while (btree || !StackIsEmpty(&stack))
    	{
    		// 2. 先遍历左子树,一直到左子树为空为止。
    		while (btree)
    		{	
    			Push(&stack, btree);
    			btree = btree->left;
    		}
    
    		// 3.若栈中还有元素,则将当前btree赋值为它的右子树,然后再重复 1~2步骤
    		if (!StackIsEmpty(&stack))
    		{
    			btree = Top(&stack);
    			printf("%c", btree->data);   //遍历完左子树后输出它们的根节点
    			Pop(&stack);
    			btree = btree->right;
    		}
    	}
    	printf("\n");
    }
    





    四、后序遍历二叉树
    遍历顺序:左节点 -> 右节点 -> 根节点

    /*
    * function				后序遍历
    * param		PBTree      root
    * return                无
    */
    void PostOrder(PBTree root)
    {
    	Stack stack = CreateStack();	//创建一个栈
    	PBTree cur;						//当前结点 
    	PBTree pre = NULL;				//前一次访问的结点 
    	Push(&stack,root);              //先将根节点入栈
    	while (!StackIsEmpty(&stack))
    	{
    		cur = Top(&stack);          //这里的cur就像是每颗子树的根节点,然后重复这些步骤
    		if ((!cur->left && !cur->right) ||
    			(pre && (pre == cur->left || pre == cur->right)))
    		{
    			printf("%c", cur->data);  //如果当前结点没有孩子结点或者孩子节点都已被访问过 
    			Pop(&stack);
    			pre = cur;
    		}
    		else
    		{
    			if (cur->right != NULL)      //这里先将右孩子入栈,这样出栈的时候,左孩子就先出栈
    				Push(&stack,cur->right);
    			if (cur->left != NULL)
    				Push(&stack,cur->left);
    		}
    	}
    	printf("\n");
    }
    





    五、层次遍历二叉树

    层次遍历就简单了,这个要用到队列
    步骤为:
    1.将根节点入队
    2.将当前节点置为队头节点 (cur = front)
    3.出队
    4.访问当前节点
    5.如果当前节点的左孩子不为空,左孩子入队
    6.如果当前节点的右孩子不为空,有孩子入队
    7.重复2~6步骤即可

    这个就相当于访问上一层的节点的时候,将下一层的结点依次入队以待访问

    /*
    * function				层次遍历
    * param		PBTree      root
    * return                无
    */
    void translevel(PBTree root)
    {
    	if (!root) return;
    	Queue queue = CreateQueue();		//创建一个队列
    	PBTree cur = root;					//当前节点
    	QPush(&queue, root);				//先将根节点加入队列中
    	while (!QueueIsEmpty(&queue))		//当队列中没有元素时,遍历完成 
    	{
    		cur = Front(&queue);			//获取当前队头元素
    		QPop(&queue);                   //遍历过后就出队
    		printf("%c", cur->data);		//先输出该子树的根节点
    		if (cur->left)					//如果左孩子不为空,则入队等待遍历
    			QPush(&queue, cur->left);   
    		if (cur->right)				    //如果右孩子不为空,则入队等待遍历
    			QPush(&queue, cur->right);
    	}
    	printf("\n");
    }
    





    六、计算二叉树深度
    利用层次遍历来求,遍历的最大层数即深度

    /*
    * function				计算二叉树深度
    * param		PBTree      root
    * return                无
    */
    int BTreeDepth(PBTree root)
    {
    	if (!root) return 0;
    	Queue queue = CreateQueue();		//创建一个队列
    	PBTree cur = root;					//当前节点
    	int iDepth = 0;
    	QPush(&queue, root);					//先将根节点加入队列中
    	while (!QueueIsEmpty(&queue))			//当队列中没有元素时,遍历完成 
    	{
    		++iDepth;							//外层循环控制层数
    		int curLevelNodes = queue.count;	//当前层数的节点数
    		int temp = 0;						//临时记录已经遍历的节点数
    
    		while (temp++ < curLevelNodes)		//当遍历完当前层数后,退出内层循环,继续遍历下一层
    		{
    			cur = Front(&queue);			//获取当前队头元素
    			QPop(&queue);                   //遍历过后就出队
    			if (cur->left)					//如果左孩子不为空,则入队等待遍历
    				QPush(&queue, cur->left);
    
    			if (cur->right)				    //如果右孩子不为空,则入队等待遍历
    				QPush(&queue, cur->right);
    		}
    	}
    	return iDepth;
    }
    





    七、计算二叉树双分支节点数
    利用前序遍历来求

    /*
    * function				计算二叉树双分支节点数
    * param		PBTree      root
    * return                无
    */
    int GetN2(PBTree root)
    {
    	Stack stack = CreateStack();   //创建一个栈
    	PBTree btree = root;           //创建临时指针指向root
    	int count = 0;
    	//利用前序遍历来访问所有的节点
    	while (btree || !StackIsEmpty(&stack))
    	{	
    		while (btree)
    		{
    			Push(&stack, btree);
    			btree = btree->left;
    		}
    		if (!StackIsEmpty(&stack))
    		{
    			btree = Top(&stack);
    			if (btree)                            //再这里能保证所有的节点都能被遍历到
    				if (btree->left && btree->right)  //当该节点有两个分支的时候+1
    					++count;
    			Pop(&stack);
    			btree = btree->right;
    		}
    	}
    	return count;
    }
    





    八、计算二叉树单分支节点数
    和计算双分支节点的方法一样,只需要把判断语句改一下即可

    if (btree)                            //再这里能保证所有的节点都能被遍历到
    				if ((btree->left && !btree->right) || (!btree->left && btree->right))  //当该节点仅且只有一个分支的时候+1
    					++count;
    





    九、计算二叉树叶子节点数
    这个就简单了,有一个公式: n0 = n2 + 1

    /*
    * function				计算二叉树终端节点数
    * param		PBTree      root
    * return                无
    */
    int GetN0(PBTree root)
    {
    	return GetN2(root) + 1; //计算公式n0 = n2 + 1;
    }
    
    





    十、添加节点
    可以用前序、中序、后序、层次遍历的方法来添加,前三个的缺点很明显,最后添加后可能会退化成一个长长的单链表。所以这里采用层次遍历的方法添加,一层层扫描,遇到空节点就添加在它那里。

    /*
    * function				添加节点值(添加的位置是不确定的)
    * param		PBTree      root
    * param		char	    ch
    * return                无
    */
    void AddValue(PBTree root, char ch)
    {
    	//采用层次遍历的办法,一层层扫描,若有空的地方,则添加到该地方
    	if (!root)
    	{
    		root = CreateNode(ch);
    		return;
    	}	
    	Queue queue = CreateQueue();		//创建一个队列
    	PBTree cur = root;					//当前节点
    	QPush(&queue, root);				//先将根节点加入队列中
    	while (!QueueIsEmpty(&queue))		//当队列中没有元素时,遍历完成 
    	{
    		cur = Front(&queue);			//获取当前队头元素
    		QPop(&queue);                   //遍历过后就出队
    		if (cur->left)					//如果左孩子不为空,则入队等待遍历
    			QPush(&queue, cur->left);
    		else                            //否则就添加值,然后退出
    		{
    			cur->left = CreateNode(ch);
    			break;
    		}
    		if (cur->right)				    //如果右孩子不为空,则入队等待遍历
    			QPush(&queue, cur->right);
    		else                            //否则就添加值,然后退出
    		{
    			cur->right = CreateNode(ch);//否则就添加值,然后退出
    			break;
    		}
    	}
    }
    

    十一、查找二叉树中的节点

    用层次遍历的方法查找

    /*
    * function				查找值
    * param		PBTree      root
    * param		char	    ch
    * return                成功返回true,否则返回false
    */
    bool Search(PBTree root, char ch)
    {
    	//利用层次遍历来查找
    	if (!root) return false;
    	Queue queue = CreateQueue();		//创建一个队列
    	PBTree cur = root;					//当前节点
    	QPush(&queue, root);				//先将根节点加入队列中
    	while (!QueueIsEmpty(&queue))		//当队列中没有元素时,遍历完成 
    	{
    		cur = Front(&queue);			//获取当前队头元素
    		if (cur->data == ch)
    			return true;
    		QPop(&queue);                   //遍历过后就出队
    		if (cur->left)					//如果左孩子不为空,则入队等待遍历
    			QPush(&queue, cur->left);
    		if (cur->right)				    //如果右孩子不为空,则入队等待遍历
    			QPush(&queue, cur->right);
    	}
    	return false;
    }
    
    展开全文
  • 数据结构 二叉树非递归算法
  • 包含一下方法: 1.通过一个数组来构造一颗...6.使用非递归 先序遍历一棵二叉树 7.使用非递归 中序遍历一棵二叉树 8.使用非递归 后序遍历一棵二叉树 PS:代码为C++代码 可以直接下载使用!!! PS2:每句代码都有详细注释
  • 主要介绍了C++实现二叉树非递归遍历方法实例总结,是算法设计中比较经典的一个遍历算法,需要的朋友可以参考下
  • 今天小编就为大家分享一篇用Python实现二叉树、二叉树非递归遍历及绘制的例子,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 二叉树非递归遍历C

    2013-09-18 15:14:41
    C语言实现二叉树非递归遍历,前序、中序、后序、层序遍历的具体实现
  • 二叉树 非递归遍历前序中序遍历 c语言
  • 二叉树非递归遍历

    2013-03-09 13:50:01
    二叉树非递归遍历,数据结构,C语言代码的实验报告
  • 后序遍历二叉树非递归算法的推导及形式化证明,难得的期刊论文资料,对研究二叉树的非递归性遍历有很大帮助
  • 经典的数据结构问题:二叉树非递归遍历算法实现 二叉树递归遍历算法实现
  • 一种二叉树非递归遍历算法的C语言实现.pdf
  • 数据结构 二叉树非递归遍历 附流程图 详细设计过程
  • 二叉树非递归实现源码(C、C++、JAVA)
  • 二叉树非递归实现,完整程序.从前辈那里看到的,自己写了写,感觉不错。
  • 这个是我自己写的关于二叉树非递归算法的遍历,其中二叉树是用的带三个指针的链表存贮实现的,大家可以参考一下
  • 二叉树 非递归前中后序遍历汇总 C语言 希望大家给予建议
  • 小小学习,C语言数据结构,中序遍历二叉树非递归算法
  • 二叉树非递归遍历C语言实现

    千次阅读 2013-09-18 15:05:03
    二叉树非递归遍历实现——C语言实现 二叉树非递归遍历:前、中、后序三种遍历需要用到栈,层序遍历需要用到队列。首先用c语言实现栈和队列,然后再实现二叉树的非递归遍历 编程环境:Visual Studio 2010 栈的实现...

    二叉树非递归遍历实现——C语言实现

    二叉树非递归遍历:前、中、后序三种遍历需要用到栈,层序遍历需要用到队列。首先用c语言实现栈和队列,然后再实现二叉树的非递归遍历

    详细解释参考:维基百科树的遍历http://en.wikipedia.org/wiki/Tree_traversal

    编程环境:Visual Studio 2010

    static void Visit(Position P)
    {
    	printf("%d ", P->Data);
    }
    
    void PreOrder(Tree T)//前序遍历
    {
    	Stack S;
    	Position P;
    
    	S = InitStack();//创建栈
    	P = T;
    	while(P || !StackEmpty(S))//StackEmpty栈是否为空
    	{
    		if(P)
    		{
    			Visit(P);
    			if(P->Right)
    				Push(P->Right, S);
    			P = P->Left;
    		}
    		else
    			P = Pop(S);
    	}
    	DestoryStack(S);//销毁栈
    }
    
    void InOrder(Tree T)//中序遍历
    {
    	Stack S;
    	Position P;
    
    	S = InitStack();//创建栈
    	P = T;
    	while(P || !StackEmpty(S))
    	{
    		if(P)
    		{
    			Push(P, S);
    			P = P->Left;
    		}
    		else
    		{
    			P = Pop(S);
    			Visit(P);
    			P = P->Right;
    		}
    	}
    	DestoryStack(S);//销毁栈
    }
    
    void PostOrder(Tree T)//后序遍历,根节点会被访问到两次,只有最后一次被访问到才出栈,即右子树遍历完成之后,根节点才可以出栈
    {
    	Position preNode, currNode;
    	Stack S;
    
    	S = InitStack();
    	preNode = NULL;
    	Push(T, S);
    
    	while(!StackEmpty(S))//判断栈是否为空
    	{
    		currNode = Peek(S);//获取栈顶元素
    		if(preNode == NULL || preNode->Left == currNode || preNode->Right == currNode)//如果当前节点是根节点或当前节点有左子树或右子树
    		{
    			if(currNode->Left)//如果有左子树则左子树入栈
    				Push(currNode->Left, S);
    			else if(currNode->Right)//如果当前节点只有右子树则右子树入栈
    				Push(currNode->Right, S);
    		}
    		else if(currNode->Left == preNode)//访问完左子树,返回到父亲点,然后判断是否还有右子树,然后右子树进栈
    		{
    			if(currNode->Right)
    				Push(currNode->Right, S);
    		}
    		else//如果没有左子树也没有右子树,或者左子树和右子树都遍历完成,则访问该节点,并将该节点出栈
    		{
    			Visit(currNode);
    			Pop(S);
    		}
    		preNode = currNode;
    	}
    	DestoryStack(S);//销毁栈
    }
    
    void LevelOrder(Tree T)//层序遍历
    {
    	Queue Q;
    	Position P;
    
    	if(T == NULL)
    		return;
    	Q = InitQueue();
    	Enqueue(T, Q);
    	while(!QueueEmpty(Q))//判断队列是否为空
    	{
    		P = Dequeue(Q);
    		Visit(P);
    		if(P->Left)
    			Enqueue(P->Left, Q);
    		if(P->Right)
    			Enqueue(P->Right, Q);
    	}
    	DestoryQueue(Q);//销毁队列
    }
    完整代码 http://download.csdn.net/detail/zitong00/6286797

    展开全文
  • JS二叉树非递归遍历

    2017-09-07 22:01:56
    二叉树的递归遍历很简单就可以实现,二叉树非递归遍历却想不出来?那你可以看看下面的例子。 一个二叉树的例子 var root = { val: 1, left: { val: 2, left: { val: 4, }, right:{ val:5 } }, right: { val: 3, ...

    二叉树的递归遍历很简单就可以实现,二叉树非递归遍历却想不出来?那你可以看看下面的例子。

    一个二叉树的例子

    var root = {
    val: 1,
    left: {

    val: 2,
    left: {
      val: 4,
    },
    right:{
      val:5
    }

    },
    right: {

    val: 3,
    left: {
      val: 6
    },
    right: {
      val: 7
    }

    }
    }
    先实现三种遍历的递归算法以作比较。

    先序遍历递归算法

    function DLR(root){

    if(root!=null){
        console.log(root.val);
        DLR(root.left);
        DLR(root.right);
    }

    }
    DLR(root)//1,2,4,5,3,6,7

    中序遍历递归算法

    function LDR(root){

    if(root!=null){
        LDR(root.left);//先遍历到最左边的节点,然后输出
        console.log(root.val);
        LDR(root.right);
    }

    }
    LDR(root)//4,2,5,1,6,3,7

    后序遍历

    function LRD(root){

    if(node!=null){
        LRD(root.left);
        LRD(root.right);
        console.log(root.val);
    }

    }
    LRD(root)//4,5,2,6,7,3,1


    看完上面的递归遍历,下面对比一下非递归的二叉树遍历。你会发现递归真心简单。

    非递归前序遍历

    function DLR(root){

    var arr=[],res=[];
    if(root!=null){
        arr.push(root);
    }
    while(arr.length!=0){
        var temp=arr.pop();
        res.push(temp.val);
        //这里先放右边再放左边是因为取出来的顺序相反
        if(temp.right!=null){
            arr.push(temp.right);
        }
        if(temp.left!=null){
            arr.push(temp.left);
        }
    }
    return res;

    }

    DLR(root)//1,2,4,5,3,6,7

    非递归中序遍历

    //先把左边的,全部放进arr再输出,处理右边的。
    function LDR(root){

    var arr=[],res=[];
    while(true){
        while(root!=null){
            arr.push(root);
            root=root.left;
        }
        //终止条件:最后树遍历完了自然就结束
        if(arr.length==0){
            break;
        }
        var temp=arr.pop();
        res.push(temp.val);
        root=temp.right;
    }
    return res;

    }
    LDR(root)//4,2,5,1,6,3,7

    后序遍历

    function LRD(root){

    var arr=[],res=[];
    arr.push(root);
    while(arr.length!=0){
        var p=arr.pop();
        res.push(p.val);
        if(p.left!=null){
            arr.push(p.left);
        }
        if(p.right!=null){
            arr.push(p.right);
        }
    }
    return res.reverse();

    }
    LRD(root)//4,5,2,6,7,3,1

    展开全文
  • C++版二叉树非递归遍历 1.二叉树前序遍历 /** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right...

    C++版二叉树非递归遍历

    一.二叉树前序遍历

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> preorderTraversal(TreeNode* root) {
            stack<TreeNode*>s;
            vector<int>s1;
            TreeNode* cur=root;
            TreeNode* top1;//记录栈定元素
           while(!s.empty()||cur)
           {
               while(cur)//如果左子树存在,用cur标记,把所有的左孩子入栈
               {
                   s1.push_back(cur->val);//把根结点的值放到vector<int>s1中
                   s.push(cur);//把根结点入栈
                   cur=cur->left;//寻找当前根结点的左孩子
               }
               top1=s.top();//拿到最后一个左孩子用top1标记
               s.pop();//因为最后一个左孩子在上一个循环内已经打印了,所以把栈顶元素直接出栈
               cur=top1->right;//进行找右孩子
           }
            return s1;
        }
    };
    

    二.二叉树中序遍历

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> inorderTraversal(TreeNode* root) {
            vector<int>ret;
            stack<TreeNode*> s;
            TreeNode* cur = root;
            TreeNode* topp;
            while(cur||!s.empty())
            {
                while(cur)
                {
                    s.push(cur);
                    cur=cur->left;
                }
                topp=s.top();
                s.pop();
                ret.push_back(topp->val);
                cur=topp->right;
            }
            return ret;
        }
    };
    

    三.二叉树后序遍历

    /**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        vector<int> postorderTraversal(TreeNode* root) {
            stack<TreeNode*>s;
    		vector<int>ret;
    		TreeNode* cur = root;
    		TreeNode* top1;//记录栈定元素
    		TreeNode* top2 = nullptr;//用来标记是否已经放到ret中
    		while (cur || !s.empty())
    		{
    			while (cur)//循环一直把左孩子入栈
    			{
    				s.push(cur);
    				cur = cur->left;
    			}
    			top1 = s.top();//当没有左孩子时,用top1取栈顶元素
    			if (top1->right == nullptr || top1->right == top2)//只有当该节点的右孩子为空或右孩子被top2标记,才能把当前根结点放到ret中
    			{
    				ret.push_back(top1->val);
    				s.pop();
    				top2 = top1;//用top2记录top1节点已经放到ret中
                    top1=nullptr;//没必要,但最好加上,防止内存泄漏问题
    			}
    			else
    			{
    				cur = top1->right;
    			}
    		}
    		return ret;
            
        }
    };
    
    展开全文
  • C语言实现通用栈结构 递归遍历二叉树 非递归遍历二叉树 (前,中,后序) exmaple.c为测试文件
  • 数据结构课程实验代码,采用非递归,通过自己建立二叉树,完成中序遍历
  • 二叉树非递归后序遍历算法(C语言)

    千次阅读 2020-07-23 16:17:55
    二叉树非递归后序遍历算法(C语言) 二叉树后序遍历的规律:左右根 后序非递归遍历中,访问根(子根)结点有两种情况 ①:遍历完左子树,需要遍历右子树,需要从栈中访问最顶上的根(子根)结点从而得到右子树的指针。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 78,004
精华内容 31,201
关键字:

二叉树非递归