package tree.binarytree;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Random;
import java.util.Stack;
/**
* Created by Lanxiaowei
* Craated on 2016/12/12 17:14
* 采用二叉排序树的中序遍历实现对一个无序的数字序列进行排序
*/
public class TestBinarySortTree2 {
public static void main(String[] args) {
//测试100次
//test(100);
test2();
}
public static void test2() {
BinarySortTreeNode parentNode = new BinarySortTreeNode(5);
BinarySortTreeNode c3 = new BinarySortTreeNode(3);
BinarySortTreeNode c6 = new BinarySortTreeNode(6);
BinarySortTreeNode c1 = new BinarySortTreeNode(1);
BinarySortTreeNode c4 = new BinarySortTreeNode(4);
BinarySortTreeNode c8 = new BinarySortTreeNode(8);
BinarySortTreeNode c9 = new BinarySortTreeNode(9);
c8.left = c3;
c8.right = c6;
c9.left = c1;
c9.right = c4;
parentNode.left = c8;
parentNode.right = c9;
//中序遍历二叉树(非递归方式)
Queue<Integer> queue = parentNode.midOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
//前序遍历二叉树(非递归方式)
queue = parentNode.preOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
//后序遍历二叉树(非递归方式)
queue = parentNode.postOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
//后序遍历二叉树(非递归方式)-->另一种实现
queue = parentNode.postorderTraversal(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
System.out.println("/**********************华丽的分割线 end**************************/\n");
}
/**
* 测试方法
* @param times 测试的总次数
*/
public static void test(int times) {
if(times <= 0) {
throw new IllegalArgumentException("The number [times] MUST be greater than zero.");
}
while(times-- > 0) {
System.out.println("/**********************华丽的分割线 begin************************/");
int min = 1;
int max = 100;
//先随机生成一个随机数作为二叉树的父节点
int parentVal = random(min,max);
//打印生成的parent节点数值
System.out.println("Parent:" + parentVal);
//创建二叉树的父节点
BinarySortTreeNode parentNode = new BinarySortTreeNode(parentVal);
//假设我们的无序数字序列的长度n=10,这里我们随机生成无序数字序列里的每个数字,然后插入二叉树结构中
int n = 10;
//用于存储每个子节点的数值
int num = 0;
//这里之所以是n - 2,是因为我们已经生成了父节点,剩下我们只需要生成n - 1个子节点,
//而i是从零开始的,因此这里是n - 2
for(int i=0; i < n - 2; i++) {
//随机生成每个子节点的数值
num = random(min,max);
System.out.println("Child:" + num);
//创建每个子节点
BinarySortTreeNode child = new BinarySortTreeNode(num);
//往二叉排序树里插入子节点
parentNode.insert(parentNode,child);
}
//中序遍历二叉树(非递归方式)
Queue<Integer> queue = parentNode.midOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
//前序遍历二叉树(非递归方式)
queue = parentNode.preOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
//后序遍历二叉树(非递归方式)
queue = parentNode.postOrderWithoutRecursive(parentNode);
while (!queue.isEmpty()) {
int i = queue.poll();
System.out.print(i + " ");
}
System.out.println();
System.out.println("/**********************华丽的分割线 end**************************/\n");
}
}
/**
* 二叉排序树的每个节点
*/
public static class BinarySortTreeNode {
//左子节点
private BinarySortTreeNode left;
//右子节点
private BinarySortTreeNode right;
/**节点上的值*/
private int val;
public BinarySortTreeNode() {}
public BinarySortTreeNode(int val) {
this.val = val;
}
/**
* 往指定的父节点上插入一个子节点
* @param parentNode 父节点
* @param newNode 待插入的节点
* @return
*/
public boolean insert(BinarySortTreeNode parentNode, BinarySortTreeNode newNode) {
if(null == newNode) {
throw new IllegalArgumentException("The Node to be inserted MUST NOT be null.");
}
if(null == parentNode) {
parentNode = newNode;
return true;
}
//若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在右边
if(parentNode.val <= newNode.val) {
//如果父节点此刻的右树为空,那么就将待插入的newNode作为父节点右树的父节点
if(parentNode.right == null) {
parentNode.right = newNode;
return true;
} else {
//如果父节点的右树不为空,那么就插入到右树的父节点下
return insert(parentNode.right, newNode);
}
}
//若待插入的节点数值大于等于父节点,则待插入的newNode此时应该在左边
if(parentNode.val > newNode.val) {
//如果父节点此刻的左树为空,那么就将待插入的newNode作为父节点左树的父节点
if(parentNode.left == null) {
parentNode.left = newNode;
return true;
} else {
//如果父节点的左树不为空,那么就插入到左树的父节点下
return insert(parentNode.left, newNode);
}
}
return false;
}
/**
* 在指定的父节点为parentNode的二叉树下查找是否存在一个数字x
* @param parentNode 二叉树的父节点
* @param x 待查找的数字x
* @return
*/
public boolean search(BinarySortTreeNode parentNode, int x) {
//如果二叉树为null,直接return false
if(null == parentNode) {
return false;
}
//此时说明找到数字x了,直接return true
if(parentNode.val == x) {
return true;
}
//此时应该在右子树中查找
if(parentNode.val < x) {
return search(parentNode.right,x);
}
//此时应该在左子树中查找
if(parentNode.val > x) {
return search(parentNode.left,x);
}
return false;
}
/**
* 中序遍历(递归方式实现)
* @param parentNode
*/
public void midorder(BinarySortTreeNode parentNode){
if(null == parentNode) {
return;
}
midorder(parentNode.left);
System.out.print(parentNode.val + " ");
midorder(parentNode.right);
}
/**
* 二叉树前序遍历(非递归方式)
* @param parentNode
* @return
*/
public Queue<Integer> preOrderWithoutRecursive(BinarySortTreeNode parentNode) {
Stack<BinarySortTreeNode> stack = new Stack<BinarySortTreeNode>();
Queue<Integer> queue = new LinkedList<Integer>();
BinarySortTreeNode currentParent = parentNode;
//当前节点非空或者Stack非空时执行
while(currentParent != null || !stack.isEmpty()) {
//先放父节点
queue.add(currentParent.val);
stack.push(currentParent);
//然后遍历左子树
currentParent = currentParent.left;
while(currentParent == null && !stack.isEmpty()){
currentParent = stack.peek();
stack.pop();
//然后遍历右子树
currentParent = currentParent.right;
}
}
return queue;
}
/**
* 二叉树后序遍历(非递归方式)
* 这种后序遍历实现方式相比postorderTraversal实现而言,性能更高效
* 左子树 右子树 中间父节点
* @param parentNode
* @return
*/
public Queue<Integer> postOrderWithoutRecursive(BinarySortTreeNode parentNode) {
long start = System.nanoTime();
Queue<Integer> queue = new LinkedList<Integer>();
BinarySortTreeNode dummy = new BinarySortTreeNode(0);
dummy.left = parentNode;
BinarySortTreeNode cur = dummy;
BinarySortTreeNode pre = null;
while (cur != null) {
if (cur.left == null) {
cur = cur.right;
} else {
pre = cur.left;
while (pre.right != null && pre.right != cur) {
pre = pre.right;
}
if (pre.right == null) {
pre.right = cur;
cur = cur.left;
} else {
reverse(cur.left, pre);
BinarySortTreeNode temp = pre;
while (temp != cur.left) {
queue.add(temp.val);
temp = temp.right;
}
queue.add(temp.val);
reverse(pre, cur.left);
pre.right = null;
cur = cur.right;
}
}
}
long end = System.nanoTime();
System.out.println("postOrderWithoutRecursive take " + (end - start) + " ns");
return queue;
}
/**
* 二叉树后序遍历(非递归方式)
* @param root
* @return
*/
public Queue<Integer> postorderTraversal(BinarySortTreeNode root) {
long start = System.nanoTime();
Queue<Integer> result = new LinkedList<Integer>();
Stack<BinarySortTreeNode> stack = new Stack<BinarySortTreeNode>();
BinarySortTreeNode prev = null;
BinarySortTreeNode curr = root;
if (root == null) {
return result;
}
stack.push(root);
while (!stack.empty()) {
curr = stack.peek();
if (prev == null || prev.left == curr || prev.right == curr) {
if (curr.left != null) {
stack.push(curr.left);
} else if (curr.right != null) {
stack.push(curr.right);
}
}
//从左子树往上遍历
else if (curr.left == prev) {
if (curr.right != null) {
stack.push(curr.right);
}
}
//从右子树往上遍历
else {
result.add(curr.val);
stack.pop();
}
prev = curr;
}
long end = System.nanoTime();
System.out.println("postorderTraversal take " + (end - start) + " ns");
return result;
}
/**
* 二叉树的中序遍历(非递归方式)
* @param parentNode
* @return
*/
public Queue<Integer> midOrderWithoutRecursive(BinarySortTreeNode parentNode) {
Stack<BinarySortTreeNode> stack = new Stack<BinarySortTreeNode>();
Queue<Integer> queue = new LinkedList<Integer>();
BinarySortTreeNode currentParent = parentNode;
BinarySortTreeNode node = null;
while(currentParent != null || !stack.isEmpty()){
stack.push(currentParent);
//先遍历左子树
currentParent = currentParent.left;
//currentParent == null表明左子树已经遍历完,此时应该输出中间的父节点
while(currentParent == null && !stack.isEmpty()){
currentParent = stack.peek();
node = stack.pop();
//保存中间的父节点
queue.add(node.val);
//最后遍历右子树
currentParent = currentParent.right;
}
}
return queue;
}
public void reverse(BinarySortTreeNode start, BinarySortTreeNode end) {
if (start == end) {
return;
}
BinarySortTreeNode pre = start;
BinarySortTreeNode cur = start.right;
BinarySortTreeNode next;
while (pre != end) {
next = cur.right;
cur.right = pre;
pre = cur;
cur = next;
}
}
}
/**
* 生成[min,max)区间内的随机数
* @param min
* @param max
* @return
*/
public static int random(int min,int max) {
Random random = new Random();
return random.nextInt(max)%(max - min + 1) + min;
}
}
分享到：
相关推荐
标题"关于二叉树前序和后序的非递归遍历算法"指的是不使用递归函数来实现二叉树的前序和后序遍历。递归方法虽然直观，但在处理大型二叉树时可能会导致栈溢出，因此非递归方法是一个更优的选择。 **前序遍历**是...
### 二叉树先序、中序、后序遍历非递归算法 #### 前言 在计算机科学中，二叉树是一种常见的数据结构，它被广泛应用于各种算法和程序设计中。二叉树的遍历是理解并操作二叉树的基础，通常有三种主要的遍历方式：...
本文将深入探讨二叉树的前序、中序、后序遍历的递归和非递归算法。 1. **前序遍历**： - **递归算法**：首先访问根节点，然后递归地对左子树进行前序遍历，最后对右子树进行前序遍历。伪代码如下： ``` function...
数据结构二叉树链式结构的前序遍历，中序遍历，后序遍历用递归的方法，层级遍历采用队列结构
在二叉树中，遍历是访问每个节点的过程，有三种主要的遍历方式：前序遍历、中序遍历和后序遍历。本主题聚焦于后序遍历，它对于理解和操作二叉树至关重要。 后序遍历（Postorder Traversal）的顺序是：先访问左子树...
### 后序遍历非递归算法 后序遍历的顺序是：左子树→右子树→根节点。这是三种遍历中最复杂的一种，因为访问顺序与栈的特性不匹配。为了实现后序遍历的非递归版本，我们可以引入额外的数据结构，如`tagtype`枚举...
这里我们将重点讨论如何在已知二叉树的前序和中序遍历的情况下，通过非递归算法实现后序遍历。 **前序遍历**：根节点 -> 左子树 -> 右子树 **中序遍历**：左子树 -> 根节点 -> 右子树 **后序遍历**：左子树 -> 右子...
二叉树的遍历通常分为三种：前序遍历（根左右）、中序遍历（左根右）和后序遍历（左右根）。通常情况下，我们都是通过递归的方式来实现这些遍历方法，但是递归方式可能会导致大量的函数调用开销，甚至可能导致栈溢出...
常见的遍历方法包括：前序遍历、中序遍历和后序遍历。 #### 4.1 前序遍历 前序遍历的顺序是先访问根节点，然后递归地进行左子树的前序遍历，最后递归地进行右子树的前序遍历。实现代码如下： ```c void Preoder...
关于数据结构实验的二叉树问题
根据给定的文件信息，本文将详细介绍二叉树的...以上就是二叉树前序、中序、后序遍历的实现细节以及二叉树的打印方式。这些方法在数据结构和算法的学习中非常重要，能够帮助我们更好地理解和操作二叉树这种数据结构。
文件"非递归前序,中序,后序遍历二叉树(优化算法)"可能包含具体的代码实现和解释，而"www.pudn.com.txt"可能是提供资料的链接或相关讨论。学习和实践这些算法，能够提高对二叉树操作的理解和处理能力。
本程序实现了三种主要的二叉树遍历方法：先序遍历、中序遍历和后序遍历。以下是关于这些遍历方法的详细解释： 1. 先序遍历（Preorder Traversal）： - 访问根节点。 - 对左子树进行先序遍历。 - 对右子树进行...
本文主要讨论了二叉树的前序、中序、后序遍历的非递归（迭代）实现，并提供了一个统一的模板。在了解非递归实现之前，我们先回顾一下递归实现的思路。 递归实现非常直观，三种遍历的递归代码几乎相同，只是访问子...
本主题主要探讨的是在MFC（Microsoft Foundation Classes）环境中如何实现二叉树的前序、中序和后序遍历。 首先，让我们了解一下二叉树的三种遍历方法： 1. 前序遍历：前序遍历的顺序是“根-左-右”。即首先访问根...
二叉树前序，中序，后序，求深度的递归和非递归方法
### 后序遍历非递归算法 后序遍历的顺序为“左-右-根”。非递归实现较为复杂，因为需要在最后访问根节点。一种常见的方法是使用带有标志位的栈： ```c typedef enum {L, R} tagtype; typedef struct { Bitree *...
[问题描述] 建立二叉树，并输出二叉树的先序，中序和后序遍历序列，以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树，能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
二叉树的遍历主要有三种方式：前序遍历、中序遍历和后序遍历。 1. **前序遍历**： - 访问根节点； - 遍历左子树； - 遍历右子树。 这种遍历方式通常用于复制二叉树或构建一个新的与原二叉树结构相同的二叉树...
### 二叉树的前序、中序、后序遍历 #### 一、引言 在计算机科学中，二叉树是一种常见的数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。为了有效地处理和操作二叉树中的数据，通常...