二叉树的三种遍历（递归，栈）

雨点打透心脏的1/2处 2023-07-08 12:24 14阅读 0赞

## 二叉树的先序遍历 ##

数据访问顺序：根结点------->左孩子------->又孩子

#### 使用递归 ####

使用了分治法：将一个大树向下一层层的分为多个小子树

/**
      * 先序遍历，使用递归，输出树中所有结点
      * @param rootNode 根结点
      */
     public static void preOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
      	if(moveNode != null) {
       		System.out.print(moveNode.getData()+" ");
       		preOrder(moveNode.getLeChild());
       		preOrder(moveNode.getRiChild());
      	}
     }

#### 使用栈 ####

利用栈的特性：对每个小子树的根结点进行存储，使得访问左子树后，右子树的追踪不会丢失  
数据在入栈时进行访问

/**
      * 使用栈来进行先序遍历
      * @param rootNode  根结点
      */
     public static void stackPreOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
      	//构造长度为10的栈
      	TreeNode[] stack = new TreeNode[10];
      	int i = 0;
      	//栈不为空且还有数据
      	while(moveNode != null || i != 0) {
       		while(moveNode != null) {
       			 //遍历左子树入栈
       		 	stack[i++] = moveNode;
       		 	System.out.print(moveNode.getData()+" ");
       		 	moveNode = moveNode.getLeChild();
       		}
       		while((moveNode = stack[--i].getRiChild()) == null) {
        			if(i == 0) {
         				//当栈空，还没有右子树，遍历结束
         				return;
        			}
       		}
      	}  
     }

PS：在这里我使用循环嵌套，可能美观性有点不太好，但易于理解

## 二叉树的中序遍历 ##

数据访问顺序：左孩子------->根结点------->右孩子

#### 使用递归 ####

大致和先序遍历相同

/**
      * 中序遍历，使用递归
      * @param rootNode 根结点
      */
     public static void inOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
      	if(moveNode != null) {
       		inOrder(moveNode.getLeChild());
       		System.out.print(moveNode.getData()+" ");
       		inOrder(moveNode.getRiChild());
     	}
     }

#### 使用栈 ####

数据的输出位置发生变化，即在出栈位置进行访问

/**
      * 使用栈完成中序遍历
      * @param rootNode   根结点
      */
     public static void stackInOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
     	TreeNode[] stack = new TreeNode[10];
     	int i = 0;
      	//栈不为空，且还有数据
      	while(moveNode != null || i != 0) {
       		while(moveNode != null) {
        			//遍历左子树入栈
        			stack[i++] = moveNode;
        			moveNode = moveNode.getLeChild();
       		}
       
       		//循环出栈，找出右子树未空的结点
       		while((moveNode = stack[--i].getRiChild()) == null) {
        			//若无右子树，直接输出当前结点值
        			System.out.print(stack[i].getData()+" ");
        			if(i == 0) {
         				//当栈空，还没有右子树，遍历结束
         				return;
        			}
       		}
       	//输出有右子树的结点值
       	System.out.print(stack[i].getData()+" ");
      	}
     }

## 二叉树的后序遍历 ##

数据访问顺序：左孩子------->右孩子------->根结点

#### 使用递归 ####

大致和先序遍历相同

/**
      * 后序遍历，使用递归
      * @param rootNode 根结点
      */
     public static void postOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
      	if(moveNode != null) {
       		postOrder(moveNode.getLeChild());
       		postOrder(moveNode.getRiChild());
       		System.out.print(moveNode.getData()+" ");
      	}
     }

#### 使用栈 ####

由于后续遍历的特殊性，若子树根结点有右子树，则需先遍历子树的右子树，再输出子树根结点，此处需要对根结点进行二次访问（第一次得到右子树的入口，第二次访问数据）。若根结点直接出栈，会导致追踪丢失，因此设一个标记对子树根结点进行判断。  
判断内容：是否为第一次访问

/**
      * 借用栈完成后序遍历
      * @param rootNode  根结点
      */
     public static void stackPostOrder(TreeNode rootNode) {
      	TreeNode moveNode = rootNode;
     	 //构造长度为10的栈
      	TreeNode[] stack = new TreeNode[20];
      	//设置标记数组，和栈同步操作,0为入栈，1为遇到一次
      	int[] mark = new int[20];
      
      	int i = 0;
     	int j = 0;
      	//将根归栈 
     	 //栈不为空时
      	while(moveNode != null || i != 0) {
       		if(moveNode != null) {
        			stack[i++] = moveNode;
        			mark[j++] = 0;
        			moveNode = moveNode.getLeChild();
      	 	}else {
        			//无右子树，直接输出
        			if(stack[i-1].getRiChild() == null) { 
         				System.out.print(stack[--i].getData()+" ");
        		 		j--;
        		 		moveNode = null;
       			}else if(stack[i-1].getRiChild() != null && mark[j-1] != 1) {
         				//若即将出栈结点有右子树且标记为0时，则不出栈只取值
         				moveNode = stack[i-1].getRiChild();
         				mark[i-1] = 1; //修改标记
        			}else if(stack[i-1].getRiChild() != null && mark[j-1] == 1) {
         				//在遍历完右子树之后，出栈，直接输出
         				System.out.println(stack[--i]+" ");
        				 j--;
         				moveNode = null;
        			}
       		}
     	 }
     }

PS：此处只使用了一个主循环，之前的遍历也可统一为一个主循环

### 测试 ###

测试树：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]

测试调用：

System.out.print("使用递归的先序遍历：");
      preOrder(rootNode);
      System.out.print("\r\n"+"使用递归的中序遍历：");
      inOrder(rootNode);
      System.out.print("\r\n"+"使用递归的后序遍历：");
      postOrder(rootNode);
      System.out.print("\r\n"+"使用栈的先序遍历：");
      stackPreOrder(rootNode);
      System.out.print("\r\n"+"使用栈的中序遍历：");
      stackInOrder(rootNode); 
      System.out.print("\r\n"+"使用栈的后序遍历：");
      postOrder(rootNode);

测试结果：  
![在这里插入图片描述][20200226184625932.png]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200226184635942.jpg?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[20200226184625932.png]: https://img-blog.csdnimg.cn/20200226184625932.png