- 浏览: 604206 次
- 来自: ...
文章分类
最新评论
-
lgh1992314:
相同的元素呢
一种离散化方法 -
HelloSummerR:
圆心的位置是随机的,于是圆的部分会落到canvas外,那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio:
好久没见到sokuban了,这有个java版的,带源码,可以参 ...
求推箱子的最小步数(java) -
肖泽文:
太好了,谢谢你。。有中文注释!
HTML5 推箱子游戏过关演示动画 -
swm8023:
删除操作,将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
建立如图的二叉树并遍历:
运行:
前序遍历:H D B A C G F E
中序遍历:B A D C H G E F
后序遍历:A B C D E F G H
非递归前序遍历:H D B A C G F E
非递归中序遍历:B A D C H G E F
非递归后序遍历:A B C D E F G H
层次遍历
H D G B C F A E
叶子结点数
3
总结点数
8
树的高度
4
下载源码:
import java.util.*; public class BinaryTree { protected Node root; public BinaryTree(Node root) { this.root = root; } public Node getRoot() { return root; } /** 构造树 */ public static Node init() { Node a = new Node('A'); Node b = new Node('B', null, a); Node c = new Node('C'); Node d = new Node('D', b, c); Node e = new Node('E'); Node f = new Node('F', e, null); Node g = new Node('G', null, f); Node h = new Node('H', d, g); return h;// root } /** 访问节点 */ public static void visit(Node p) { System.out.print(p.getKey() + " "); } /** 递归实现前序遍历 */ static void preorder(Node p) { if (p != null) { visit(p); preorder(p.getLeft()); preorder(p.getRight()); } } /** 递归实现中序遍历 */ static void inorder(Node p) { if (p != null) { inorder(p.getLeft()); visit(p); inorder(p.getRight()); } } /** 递归实现后序遍历 */ static void postorder(Node p) { if (p != null) { postorder(p.getLeft()); postorder(p.getRight()); visit(p); } } /** 层次遍历*/ static void levelorder(Node p){ if(p==null) return; Queue<Node> queue=new LinkedList<Node>(); queue.offer(p); while(queue.size()>0){ Node temp=queue.poll(); visit(temp); if(temp.getLeft()!=null){ queue.offer(temp.getLeft()); } if(temp.getRight()!=null){ queue.offer(temp.getRight()); } } } /** 非递归实现前序遍历 */ static void iterativePreorder(Node p) { Stack<Node> stack = new Stack<Node>(); if (p != null) { stack.push(p); while (!stack.empty()) { p = stack.pop(); visit(p); if (p.getRight() != null) stack.push(p.getRight()); if (p.getLeft() != null) stack.push(p.getLeft()); } } } /** 非递归实现后序遍历 单栈法*/ static void iterativePostorder(Node p) { Stack<Node> stack = new Stack<Node>(); Node node = p, prev = p; while (node != null || stack.size() > 0) { while (node != null) { stack.push(node); node = node.getLeft(); } if (stack.size() > 0) { Node temp = stack.peek().getRight(); if (temp == null || temp == prev) { node = stack.pop(); visit(node); prev = node; node = null; } else { node = temp; } } } } /** 非递归实现中序遍历 */ static void iterativeInorder(Node p) { Stack<Node> stack = new Stack<Node>(); Node node = p; while (node != null || stack.size() > 0) { while (node != null) { stack.push(node); node = node.getLeft(); } if (stack.size() > 0) { node = stack.pop(); visit(node); node = node.getRight(); } } } // 求二叉树的高度 static int height(Node tree) { if (tree == null) return 0; else { int leftTreeHeight = height(tree.getLeft()); int rightTreeHeight = height(tree.getRight());; return leftTreeHeight > rightTreeHeight ? leftTreeHeight + 1: rightTreeHeight + 1; } } // 求二叉树的结点总数 static int nodes(Node tree) { if (tree == null) return 0; else { int left = nodes(tree.getLeft()); int right = nodes(tree.getRight()); return left + right + 1; } } // 求二叉树叶子节点的总数 static int leaf(Node tree) { if (tree == null) return 0; else { int left = leaf(tree.getLeft()); int right = leaf(tree.getRight()); if (tree.getLeft() == null && tree.getRight() == null) return left + right + 1; else return left + right; } } /** * @param args */ public static void main(String[] args) { BinaryTree tree = new BinaryTree(init()); System.out.print(" 前序遍历:"); preorder(tree.getRoot()); System.out.println(); System.out.print(" 中序遍历:"); inorder(tree.getRoot()); System.out.println(); System.out.print(" 后序遍历:"); postorder(tree.getRoot()); System.out.println(); System.out.println(); System.out.print(" 非递归前序遍历:"); iterativePreorder(tree.getRoot()); System.out.println(); System.out.print(" 非递归中序遍历:"); iterativeInorder(tree.getRoot()); System.out.println(); System.out.print(" 非递归后序遍历:"); iterativePostorder(tree.getRoot()); System.out.println(); System.out.println("层次遍历"); levelorder(tree.getRoot()); System.out.println(); System.out.println(); System.out.println("叶子结点数"); System.out.println(leaf(tree.getRoot())); System.out.println("总结点数"); System.out.println(nodes(tree.getRoot())); System.out.println("树的高度"); System.out.println(height(tree.getRoot())); } } public class Node { private char key; private Node left, right; public Node(char key) { this(key, null, null); } public Node(char key, Node left, Node right) { this.key = key; this.left = left; this.right = right; } public char getKey() { return key; } public void setKey(char key) { this.key = key; } public Node getLeft() { return left; } public void setLeft(Node left) { this.left = left; } public Node getRight() { return right; } public void setRight(Node right) { this.right = right; } }
运行:
前序遍历:H D B A C G F E
中序遍历:B A D C H G E F
后序遍历:A B C D E F G H
非递归前序遍历:H D B A C G F E
非递归中序遍历:B A D C H G E F
非递归后序遍历:A B C D E F G H
层次遍历
H D G B C F A E
叶子结点数
3
总结点数
8
树的高度
4
下载源码:
发表评论
-
求二叉树上任意两个节点的最近公共父节点
2013-01-09 10:24 2404北大百练题2756: 如上图所示,由正整数1, 2 ... -
JAVA判断二叉树是否是二叉平衡树
2013-01-07 18:59 1988import java.util.*; ... -
大顶堆应用:POJ2010
2012-12-23 20:59 1912POJ2010题意: 奶牛学校招生,c头奶牛报名,要选 ... -
二维树状数组学习之二:练习POJ 1195
2012-12-12 21:40 1400接前文:二维树状数组学习之一:彻底理解http://128kj ... -
二维树状数组学习之一:彻底理解
2012-12-12 20:54 2472当要频繁的对数组元素进行修改,同时又要频繁的查询数组内 ... -
图的深搜+树状数组练习 POJ 3321(JAVA)
2012-12-11 11:13 1843关于树状数组:参看:http://128kj.iteye.co ... -
树状数组练习:POJ 3067
2012-12-09 17:10 1845关于树状数组,参看:http://128kj.iteye.co ... -
树状数组练习:POJ 2481(JAVA)
2012-12-08 18:11 1823关于树状数组,请参考:http://128kj.iteye.c ... -
初步了解树状数组
2012-12-07 14:18 1791一、树状数组是干什么的? 平常我们会遇到一些对数组进 ... -
线段树求逆序数(离散化)POJ 2299
2012-12-06 08:25 2122POJ2299题意: 给出长度为n的序列,每次只能交换 ... -
利用线段树求逆序数(JAVA)
2012-12-04 22:46 2597设A[1…n]是一个包含n个不同数的数组。如果在i< ... -
线段树入门学习(三)懒操作(兼解POJ1823) JAVA
2012-12-02 15:37 2139继续上文"线段树入门学习(二)" ht ... -
线段树入门学习(二)(兼解POJ3468) JAVA
2012-11-30 16:55 2561继续上文http://128kj.iteye. ... -
线段树入门学习(兼解HDU1754)
2012-11-30 11:24 2728先看网上的介绍: 线段树也叫区间树,顾名思义,线段树是 ... -
AVL树及JAVA实现
2012-11-26 16:34 2307一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二 ... -
图解平衡二叉树
2012-11-26 11:34 2064形态匀称的二叉树 ... -
深度优先遍历字典树(统计单词出现的个数)
2012-11-23 22:18 2856例:给出一个字符文本,每行一个字符串,统计不同的字符串出现的百 ... -
学习使用字典树(JAVA)
2012-11-22 09:25 2148字典树 又称单词 ... -
彻底弄懂最大堆的四种操作(图解+程序)(JAVA)
2012-11-17 21:50 18735堆有最大堆和最小堆之分,最大堆就是每个节点的值都>= ... -
并查集入门精讲,实例2个(JAVA)
2012-10-30 14:47 4070一、什么是并查集 ...
相关推荐
将有双亲域的二叉链表进行中序遍历的递推式算法
### 数据结构:建立二叉树二叉链表存储结构实现有关操作 #### 一、实验题目及背景 本次实验的主要任务是通过建立二叉树的二叉链表存储结构来实现特定的操作。二叉树是一种重要的非线性数据结构,在计算机科学中有...
建立二叉树,实现二叉树的先序、中序、后序的递归遍历算法,输出遍历结果。 实现二叉树的先序、中序、后序和层次遍历的非递归算法,输出遍历结果。
按先序遍历的扩展序列建立二叉树的二叉链表存储结构,实现二叉树先序、中序、后序遍历的递归算法,实现二叉树中序遍历的非递归算法,实现二叉树层次遍历的非递归算法(要求使用顺序队列,调用顺序队列基本操作...
二叉树采用二叉链表结构表示。设计并实现如下算法:输入某棵二叉树的广义表形式,建立该二叉树,并按层次遍历该二叉树
数据结构C++二叉链表的先序遍历、中序遍历和后序遍历实现
二叉树的建立和遍历算法 数据结构课程设计用
在这个主题中,我们将深入探讨二叉树的三种主要遍历方法:前序遍历、中序遍历和后序遍历,以及它们在C++中的实现方式。 1. **前序遍历**:前序遍历的顺序是根节点 -> 左子树 -> 右子树。在C++中,递归实现可以如下...
### 数据结构知识点:先序创建二叉树及层次遍历 #### 一、知识点概述 在计算机科学领域,数据结构是研究如何组织和存储数据的关键技术之一。其中,二叉树作为一种基本的数据结构,在实际应用中有着广泛的应用场景...
首先,我们要了解二叉树的三种基本遍历方式:前序遍历、中序遍历和后序遍历。这些遍历方法主要通过递归和非递归两种方式实现。 1. **前序遍历**(根-左-右):首先访问根节点,然后递归地遍历左子树,最后遍历右子...
C++用非递归算法(用栈实现前序、中序、后序遍历;用队列实现层次遍历)实现二叉树的遍历。
本文主要探讨如何使用二叉链表来存储二叉树,并实现四种基本遍历方法:先序遍历、中序遍历、后序遍历和按层遍历。同时,我们还将讨论如何交换二叉树所有节点的左右子树。 首先,二叉链表是二叉树的一种存储方式,每...
在“二叉树的建立及递归遍历”这个主题中,我们将探讨如何创建二叉树以及如何通过递归方法来遍历它。创建二叉树通常涉及将数据结构化为树的形式,这可以通过使用链表或数组实现。在链表实现中,每个节点包含一个数据...
1按先序次序输入二叉树中结点的值(一个字符),`0`表示空树,生成二叉树的二叉链表存储结构。然后按中序和后序顺序遍历二叉树输出结果。
通常,我们首先通过递归来实现二叉树的遍历,但递归方法可能因深度过大导致栈溢出,因此掌握非递归版本的遍历算法显得尤为重要。 ### 中序遍历二叉树非递归算法详解 #### 1. 理解中序遍历的基本概念 中序遍历是一...
在“二叉树_取下级树”这个标签中,可能包含了一个获取二叉树子树的函数,用于构建遍历过程。 4. **内存操作**: - "内存_读整数内存"这个标签涉及到对内存的直接操作。在易语言中,可以使用内存操作函数来读取和...
在压缩包文件`SY0907214_张延超_作业3_二叉树遍历`中,可能包含了具体的二叉树结构和对应的遍历代码实现,你可以详细分析这些代码,理解它们如何根据上述规则进行遍历。通过这种方式,你不仅可以学习到二叉树的基本...
就是一个 简单的 二叉树的建立及前中后序遍历的 代码
2.用递归及非递归算法对二叉树实现先序遍历; 3.用递归及非递归算法对二叉树实现中序遍历; 4.用递归及非递归算法对二叉树实现后序遍历。 5.用递归遍历算法中的访问结点的操作修改为叶结点计数,统计度为0的;度为1...