每天一点数据结构之二叉树非递归遍历

我不是女神ヾ 2022-08-22 03:59 78阅读 0赞

# 用js实现的二叉树非递归遍历 #

即使是做前端，发现自己的数据结构还是很薄弱，所以每天学习一点数据结构吧！今天学习了二叉树的非递归遍历。

一：先序遍历

主要思路：通过栈来解决，先序遍历是根左右的顺序，由根节点沿左子树一直遍历下去，在遍历过程中每遇到一个结点就将其内容输出并将该结点压入栈中。当没有左子树时就将这个结点弹出栈，并从这个结点的右子树继续向下遍历。

<pre name="code" class="javascript"><span style="font-size:18px;">//二叉树的非递归遍历
    function BinaryTreeNode(data, left, right) {
    	this.data = data;
    	this.left = left;
    	this.right = right;
    	return this;
    }
    
    function BinaryTree() {
    	this.root = null;
    }
    
    //二叉树先序遍历
    BinaryTree.prototype.preorder = function()
    {
    	var tree_array_data = [];   //存放遍历结果
    	var stack = [];             //初始化栈
    	var node = this.root;       //从根结点开始
    
    	while (node != null || stack.length)        //当node为空并且栈为空时结束遍历
    	{
    		if (node != null)
    		{
    			tree_array_data.push(node.data);    //输出该结点内容
    			stack.push(node);					//将该结点入栈
    			node = node.left;                   //继续沿左子树遍历
    		}
    		else
    		{
    			node = stack.pop();                 //出栈
    			node = node.right;                  //继续沿右子树遍历
    		}
    	}                     
    	return tree_array_data;
    }</span>

二.中序遍历

主要思路：还是用栈，和先序的思路差不多，左根右的顺序，只是输出内容的地方放在遍历完左子树之后，遍历右子树之前。

//二叉树中序遍历
    BinaryTree.prototype.indorder = function()
    {
    	var tree_array_data = [];
    	var stack = [];
    	var node = this.root;
    
    	while (node != null || stack.length)
    	{
    		if (node != null)
    		{
    			stack.push(node);    //将该结点压栈
    			node = node.left;    //沿左子树继续向下遍历
    		}
    		else
    		{
    			node = stack.pop();   //出栈
    			tree_array_data.push(node.data);    //输出该结点内容
    			node = node.right;                  //继续沿右子树遍历
    		}
    	/*	if(node == null && stack.length == 0)   //当遍历完成后判断并退出
    			break;*/
    	}
    	return tree_array_data;
    }

三.后序遍历

主要思路：还是用栈，与前两者不同的地方在于，需要一个标志位来存放当前结点右子树是否遍历，标志位为0代表只遍历了左子树，标志位为1代表左右子树都遍历了可以输出该结点内容了。

//二叉树后序遍历
    BinaryTree.prototype.postorder = function()
    {
    	var tree_array_data = [];
    	var stack = [];               //初始化栈
    	var flag = [];                //标志位，标志当前结点的右子树是否被遍历，0代表未遍历，1代表已遍历
    	var node = this.root;
    
    	while (node != null || stack.length)
    	{
    		if (node != null)
    		{
    			stack.push(node);           //当前结点入栈
    			flag[stack.length-1] = 0;   //当前结点标志位置0
    			node = node.left;           //继续遍历左子树
    		}
    		else
    		{
    			node = stack.pop();        //栈顶元素出栈
    			if (!flag[stack.length])   //判断当前结点右子树是否被遍历
    			{
    				stack.push(node);      //当前结点再次入栈，并遍历右子树
    				flag[stack.length-1] = 1;
    				node = node.right;
    			}  
    			else                       //当前结点的左右子树都已遍历
    			{
    				tree_array_data.push(node.data);   //输出当前结点信息
    				node = null;
    			}
    		}
    	}
    	return tree_array_data;
    
    }