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; } }
相关推荐
二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法,不得不下的资源
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
关于二叉树前序和后序的非递归遍历算法.rar
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
二叉树前序、中序、后序三种遍历的非递归算法(C语言)
已知二叉树的前序和中序遍历,打印后序遍历,采用二叉树的非递归算法,分享给大家~~
关于数据结构实验的二叉树问题
栈的应用——二叉树的前序、中序、后序非递归遍历算法
非递归前序,中序,后序遍历二叉树(优化算法)
二叉树前序,中序,后序,求深度的递归和非递归方法
[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。
自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
C++ 数据结构二叉树(前序/中序/后序递归、非递归遍历) 二叉树的性质: 二叉树是一棵特殊的树,二叉树每个节点最多有两个孩子结点,分别称为左孩子和右孩子。 例: 实例代码: #include #include #include ...
二叉树遍历算法 (递归的、非递归的中序、前序、后序遍历 和 层次遍历 以及 求二叉树的宽度和深度)
(1)建立的二叉树; 节点的结构体为: typedef struct ...(2)完成二叉树前序、中序、后序非递归遍历程序;从上至下,从左向右层次遍历;从上至下,从右向左层次遍历; (3)给出程序和每种遍历程序的结果。
递归实现先序遍历、中序遍历、后序遍历 堆栈实现先序遍历、中序遍历、后序遍历 队列实现层次遍历 # -*- coding=utf-8 -*- class Node(object): """节点类""" def __init__(self, element=-1, l_child=None, r_...
本文实例讲述了PHP基于非递归算法实现先序、中序及后序遍历二叉树操作。分享给大家供大家参考,具体如下: 概述: 二叉树遍历原理如下: 针对上图所示二叉树遍历: 1. 前序遍历:先遍历根结点,然后遍历左子树,...