package algorithm.tree;
import java.util.Stack;
class Node{
private int key;
private Node leftNode,rightNode;
public Node(int key,Node leftNode,Node rightNode){
this.key = key;
this.leftNode = leftNode;
this.rightNode = rightNode;
}
public int getKey() {
return key;
}
public void setKey(int key) {
this.key = key;
}
public Node getLeftNode() {
return leftNode;
}
public void setLeftNode(Node leftNode) {
this.leftNode = leftNode;
}
public Node getRightNode() {
return rightNode;
}
public void setRightNode(Node rightNode) {
this.rightNode = rightNode;
}
}
public class BinTree {
private Node rootNode;
public BinTree(Node rootNode){
this.rootNode = rootNode;
}
public Node getRootNode() {
return rootNode;
}
public static void visit(Node node) {
System.out.print(node.getKey()+" ");
}
/**
* 前序遍历
* @param rootNode
*/
public static void PreOrder(Node rootNode){
if(rootNode!=null){
visit(rootNode);
PreOrder(rootNode.getLeftNode());
PreOrder(rootNode.getRightNode());
}
}
/**
* 中序遍历
* @param rootNode
*/
public static void InOrder(Node rootNode){
if(rootNode!=null){
InOrder(rootNode.getLeftNode());
visit(rootNode);
InOrder(rootNode.getRightNode());
}
}
/**
* 非递归中序遍历
* @param rootNode
*/
public static void IterativeInOrder(Node rootNode){
Stack<Node> stack = new Stack<Node>();
Node n = rootNode;
while(n!=null || !stack.isEmpty()){
if(n!=null){
stack.push(n);
n = n.getLeftNode();
}else{
n = stack.pop();
visit(n);
n = n.getRightNode();
}
}
}
/**
* 后续遍历
* @param rootNode
*/
public static void PostOrder(Node rootNode){
if(rootNode!=null){
PostOrder(rootNode.getLeftNode());
PostOrder(rootNode.getRightNode());
visit(rootNode);
}
}
/**
* 递归二叉树查找
* @param node
* @param k
* @return
*/
public static Node TreeSearch(Node node,int k){
if(k==node.getKey())
return node;
if(k<node.getKey()){
return TreeSearch(node.getLeftNode(),k);
}else{
return TreeSearch(node.getRightNode(),k);
}
}
/**
* 非递归二叉树查找
* @param node
* @param k
* @return
*/
public static Node IterativeTreeSearch(Node node,int k){
while(k!=node.getKey()){
if(k<node.getKey()){
node = node.getLeftNode();
}else{
node = node.getRightNode();
}
}
return node;
}
/**
* 最小元素
* @param node
* @return
*/
public static Node TreeMinimum(Node node){
while(node.getLeftNode()!=null){
node = node.getLeftNode();
}
return node;
}
/**
* 最大元素
* @param node
* @return
*/
public static Node TreeMaximum(Node node){
while(node.getRightNode()!=null){
node = node.getRightNode();
}
return node;
}
public static void main(String[] args) {
Node g = new Node(4,null,null);
Node d = new Node(3,null,g);
Node b = new Node(6,d,null);
Node e = new Node(17,null,null);
Node f = new Node(20,null,null);
Node c = new Node(18,e,f);
Node rootNode = new Node(15,b,c);
BinTree binTree = new BinTree(rootNode);
System.out.println("递归中序遍历");
BinTree.InOrder(rootNode);
System.out.println();
System.out.println("非递归中序遍历");
BinTree.IterativeInOrder(rootNode);
System.out.println();
Node node1 = BinTree.TreeSearch(rootNode, 17);
System.out.println("递归查找"+node1.getKey());
Node node2 = BinTree.TreeSearch(rootNode, 6);
System.out.println("非递归查找"+node2.getKey());
Node minNode = BinTree.TreeMinimum(rootNode);
System.out.println("最小元素为:"+minNode.getKey());
Node maxNode = BinTree.TreeMaximum(rootNode);
System.out.println("最小元素为:"+maxNode.getKey());
}
}
分享到:
相关推荐
Java基础复习笔记10数据结构-排序二叉树。
Java基础复习笔记08数据结构-二叉树和二叉树的遍历。
数据结构复习笔记-树和二叉树推荐.pdf
数据结构课件复习资料,包括线性表,图,串,栈与队列,树与二叉树等,清华大学版教材适用
数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表,树和二叉树,图,查找,内排,外排,文件,动态存储分配。对于绝大多数的学校而言,“外排,文件,动态存储分配”三章基本上是不考...
数据结构复习重点归纳(清华严蔚敏教材) 经典的总数据结构复习重点归纳(清华严蔚敏教材) 一、数据结构的章节结构及重点构成 数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表...
第一章绪论、算法衡量指标、第二章线性表、顺序表、链表、第三章栈和队、栈、栈的应用举例、队列、循环队列、第四章串、串的模式匹配、第五章数组和广义表、稀疏矩阵的压缩存储方法:、广义表、第六章树和二叉树、...
一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 ...2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 。。。。
是本人博客部分内容的整合,《C++及数据结构复习笔记》的第一章到第15章的部分。由于只校对了一次,在所难免存在表达不合适的地方,还有可能存在错别字。 该复习文档是本人根据谭浩强老师的《C++程序设计》、邓俊辉...
18.下图中给出由7个顶点组成的无向图。从顶点1出发,对它进行深度优先遍历得到的序列是( ① ),而进行广度优先遍历得到的顶点序列是( ② )。【中科院软件所 1999 六、2-(1)(2分)】 ①.A.1354267 B.1347652 ...
这些程序都是本人在复习数据结构中自己写的,都是可以运行的,对学习数据结构绝对有好处
数据结构与算法 数据结构与C语言 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 第2章 线性表(共172页).ppt 数据结构与算法 数据结构与...
数据结构的全面复习资料,重点难点; 二叉树 排序 查找、顺序表, 带有代码和相关的算法。
数据结构学科的章节划分基本上为:概论,线性表,栈和队列,串,多维数组和广义表,树和二叉树, 图,查找,内排,外排,文件,动态存储分配。 对于绝大多数的学校而言,“ 外排,文件,动态存储分配”三章基本上是...
因为数据结构考试,然后自己总结的二叉树遍历代码。通俗易懂,自己写写就可以记住的代码,摒除掉了伪代码记忆的难点。
期末复习习题集 数据结构期末复习习题全文共60页,当前为第1页。 1. 数据结构在计算机内存中的表示指 A. 数据的存储结构 B. 数据结构 C. 数据的逻辑结构 D. 数据元素之间的关系 A 数据结构期末复习习题全文共60页,...
数据结构与算法 数据结构与C语言 data structure课程 第0章 C++复习(共49页).ppt 数据结构与算法 数据结构与C语言 data structure课程 第1章 绪论(共56页).ppt 数据结构与算法 数据结构与C语言 data structure...
│ 清华计算机考研数据结构复习提要.pdf │ 算法与数据结构试题及分析.doc │ 考研《数据结构》必须掌握的知识点与算法.doc │ 考研数据结构,各种算法的经解分析.doc │ 考研用算法.doc │ 计算机数据结构考研...