package BiTree_5;
/**
* @author MoonMonster
* @date 2015-9-21 下午09:46:48
*/
//节点
public class Node {
Node leftChild;
Node rightChild;
Object element;
public Node(Object obj){
this.element = obj;
this.leftChild = null;
this.rightChild = null;
}
public Node(){
this.leftChild = null;
this.rightChild = null;
}
}
package BiTree_5;
import java.util.Scanner;
import java.util.Stack;
/**
* @author MoonMonster
* @date 2015-9-22 下午06:28:19
*/
public class Tree {
// 根节点
Node root;
public Tree() {
root = null;
}
// 层序创建树
public void builderTree() {
Node[] tree = new Node[100];
Scanner sc = new Scanner(System.in);
String str = "";
int index = 0;
while (true) {
Node temp = null;
str = sc.next();
if (str.equals("quit")) {
break;
}
if (root == null) {
root = new Node(str);
} else if (root.equals("null")) {
temp = null;
} else {
temp = new Node(str);
}
if (index == 0) {
tree[index] = root;
} else {
tree[index] = temp;
if (index % 2 == 0) {
tree[index / 2 - 1].rightChild = temp;
} else {
tree[index / 2].leftChild = temp;
}
}
index++;
}
}
// 前序递归输出
public void print(Node temp) {
if (temp != null) {
System.out.print(temp.element + " ");
print(temp.leftChild);
print(temp.rightChild);
}
}
// 数叶节点数量
public int countLeaves(Node temp) {
int count = 0;
if (temp != null) {
if (temp.leftChild == null && temp.rightChild == null) {
count++;
}
count += countLeaves(temp.leftChild);
count += countLeaves(temp.rightChild);
}
return count;
}
// 数节点数目
public int countNode(Node temp) {
int count = 0;
if (temp != null) {
count++;
count += countNode(temp.leftChild);
count += countNode(temp.rightChild);
}
return count;
}
// 非递归前序遍历--1
public void preTraverse(Node temp) {
Stack<Node> stack = new Stack<Node>();
if(temp != null){
stack.push(temp);
while(!stack.empty()){
temp = stack.pop();
System.out.print(temp.element);
if(temp.rightChild != null){
stack.push(temp.rightChild);
}
if(temp.leftChild != null){
stack.push(temp.leftChild);
}
}
}
System.out.println();
}
//非递归前序遍历--2
public void preTraverse_2(Node temp){
Stack<Node> stack = new Stack<Node>();
if(temp == null){
System.out.println("空树");
return ;
}
while(temp != null || !stack.empty()){
while(temp != null){
System.out.print(temp.element);
stack.push(temp);
temp = temp.leftChild;
}
temp = stack.pop();
temp = temp.rightChild;
}
}
//中序非递归遍历
public void inTraverse(Node temp){
Stack<Node> stack = new Stack<Node>();
if(temp == null){
System.out.println("空树。");
return ;
}
while(temp!=null || !stack.empty()){
while(temp != null){
stack.push(temp);
temp = temp.leftChild;
}
temp = stack.pop();
System.out.print(temp.element);
temp = temp.rightChild;
}
}
//判断树中是否存在某个元素
public boolean indexOf(Node temp,Object obj){
boolean result = false;
if(temp != null){
if(temp.element.equals(obj)){
result = true;
return result;
}
result = indexOf(temp.leftChild,obj);
if(result == true){
return result;
}
result = indexOf(temp.rightChild,obj);
}
return result;
}
//判断树中有多少个指定数据
public int countObject(Node temp, Object obj){
int count = 0;
if(temp != null){
if(temp.element.equals(obj)){
count ++;
}
count += countObject(temp.leftChild,obj);
count += countObject(temp.rightChild,obj);
}
return count;
}
}
package BiTree_5;
/**
* @author MoonMonster
* @date 2015-9-22 下午06:43:08
*/
public class TreeTest {
public static void main(String[] args) {
Tree tree = new Tree();
tree.builderTree();
// System.out.println(tree.root.element);
// tree.preTraverse(tree.root);
// System.out.println(tree.countLeaves(tree.root));
// System.out.println(tree.countNode(tree.root));
// tree.preTraverse_2(tree.root);
// tree.inTraverse(tree.root);
// System.out.println(tree.indexOf(tree.root, "A"));
// System.out.println(tree.countObject(tree.root, "A"));
}
}
当初写这个时还没养成写注释的习惯,不过代码都不难理解,稍微看下都可以看懂。
分享到:
相关推荐
/* 设栈元素为二叉树的指针类型 */ typedef struct { QElemType *base; int front; /* 头指针,若队列不空,指向队列头元素 */ int rear; /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */ } SqQueue; ...
建立一棵二叉树,试编程实现二叉树的如下基本操作: 1. 按先序序列构造一棵二叉链表表示的二叉树T; 2. 对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出结点的遍历序列; 3. 求二叉树的深度/结点数目...
[一段可以运行的代码]二叉树的层序创建和后续遍历。 代码一共涉及涉及二叉树、队列、堆栈。二叉树和堆栈采用链表实现,队列采用数组实现。 二叉树本身用链表表示,链表每个节点有3个字段,其中2个是左右指针。 ...
1.建立二叉树 2.树形输出 3.广义表形输出 4.判断是否为空树 5.求树的深度 6.插入孩子结点 7.删除孩子结点 8.取出根结点 9.取双亲结点 10.取左孩子结点 11.取右孩子结点 12.取左兄弟 13.取右兄弟 14.先序遍历 15.中序...
1 已知二叉树以二叉链表作为存储结构,写一个算法按层序遍历它,通过程序在终端屏幕上打印出它的层序序列。 2 先建立二叉树的二叉链表存储结构,再遍历它。 3 利用队列完成算法。
二叉树的基本操作,包括创建、查找结点数、双亲结点数、查找祖先、双亲、左右孩子、层序遍历
C++创建二叉树及操作包括前序遍历后序遍历层序遍历 深度 叶子节点
要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列;分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数;
适合毕业设计的同学用,数据结构 二叉树遍历,层序、中序遍历,课程设计做的,绝对能帮大家
利用先序序列建立二叉树,数据以字符的形式传入;在建立的二叉树上完成遍历(递归遍历、非递归遍历、层序遍历)操作。
要求能够输入树的各个结点,并能够输出用不同方法遍历的遍历序列; 分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先序遍历序列的函数
二)二叉树的一些基本操作 (1)返回二叉树的根; (2)返回树中某个结点的左孩子,若无则返回“空”; (3)返回树中某个结点的双亲,如果是根结点,则返回“空”; 三) 在(二)的基础上,求二叉树的深度+结点数 (1)求...
二叉树的基本功能: 1、二叉树的建立 2、前序遍历二叉树 3、中序遍历二叉树 4、后序遍历二叉树 5、按层序遍历二叉树 6、求二叉树的深度 7、求指定结点到根的路径 8、二叉树的销毁 9、其他:自定义操作
1.二叉树的基本操作实现【问题描述】建立一棵二叉树,用递归方法实现二叉树的如下基本操作:(1)按先序序列构造一棵二叉链表表示的二叉树T;(2)对这棵二叉树进行遍历:先序、中序、后序以及层次遍历,分别输出...
第一部分:栈的构建、销毁、进栈和出栈等一些基本操作; 第二部分:队列的构建、销毁、入队和出队等一些基本操作; 第三部分:最主要的一部分包括了二叉树的各种操作:先序模块,中序模块,后序模块,层序模块;它们...
该程序在创建二叉树后又层序遍历二叉树,对于二叉树解释的比较详尽。 3.该程序的目的是在创建树的结构体后,查找树的最小节点以及树的后续节点。 4.该资料包含了三个小程序,1.二叉树的创建。2.决策树的创建。该程序...
建立二叉树,层序、先序、中序、后序遍历二叉树。...基本操作: (1)输入树的各个结点,并能够输出用不同方法遍历的遍历序列; (2)分别建立建立二叉树存储结构的的输入函数、输出层序遍历序列的函数、输出先
主要介绍了Python 二叉树的层序建立与三种遍历实现详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
建立二叉树,并对其进行操作,基本功能要求: 1、建立一棵二叉树; 2、对该二叉树进行前序、中序、后序、层序遍历; 3、统计二叉树中叶结点、非叶节点的个数; 4、以二叉树为参数,交换每个结点的左子女和右子女...
编程实现二叉树的建立,先序、中序、后序、层序遍历(非递归方法),二叉树的高度、交换左右子树,统计叶子节点的数目,判断是否为完全二叉树,用括号的形式输出树等功能。 [基本要求] 程序输出菜单界面,菜单包含8...