java排序二叉树

1. 求数据结构（java版）实验树和二叉树题目答案

/**
* @param args
之前在大学的时候写的一个二叉树算法，运行应该没有问题，就看适不适合你的项目了 */
public static void main(String[] args) {

BiTree e = new BiTree(5);
BiTree g = new BiTree(7);
BiTree h = new BiTree(8);
BiTree l = new BiTree(12);
BiTree m = new BiTree(13);
BiTree n = new BiTree(14);
BiTree k = new BiTree(11, n, null);
BiTree j = new BiTree(10, l, m);
BiTree i = new BiTree(9, j, k);
BiTree d = new BiTree(4, null, g);
BiTree f = new BiTree(6, h, i);
BiTree b = new BiTree(2, d, e);
BiTree c = new BiTree(3, f, null);
BiTree tree = new BiTree(1, b, c);
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));

System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
System.out.println("--------------------------------------");
tree.exChange();
System.out.println("交换每个节点的左右孩子节点后......");
System.out.println("递归前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("非递归前序遍历二叉树结果: ");
tree.iterativePreOrder(tree);
System.out.println();
System.out.println("递归中序遍历二叉树的结果为:");
tree.inOrder(tree);
System.out.println();
System.out.println("非递归中序遍历二叉树的结果为:");
tree.iterativeInOrder(tree);
System.out.println();
System.out.println("递归后序遍历二叉树的结果为:");
tree.postOrder(tree);
System.out.println();
System.out.println("非递归后序遍历二叉树的结果为:");
tree.iterativePostOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();

System.out.println("递归求二叉树中所有结点的和为:"+getSumByRecursion(tree));
System.out.println("非递归求二叉树中所有结点的和为:"+getSumByNoRecursion(tree));

System.out.println("二叉树中,每个节点所在的层数为:");
for (int p = 1; p <= 14; p++)
System.out.println(p + "所在的层为:" + tree.level(p));
System.out.println("二叉树的高度为:" + height(tree));
System.out.println("二叉树中节点总数为:" + nodes(tree));
System.out.println("二叉树中叶子节点总数为:" + leaf(tree));
System.out.println("二叉树中父节点总数为:" + fatherNodes(tree));
System.out.println("二叉树中只拥有一个孩子的父节点数:" + oneChildFather(tree));
System.out.println("二叉树中只拥有左孩子的父节点总数:" + leftChildFather(tree));
System.out.println("二叉树中只拥有右孩子的父节点总数:" + rightChildFather(tree));
System.out.println("二叉树中同时拥有两个孩子的父节点个数为:" + doubleChildFather(tree));
}
}

2. 如何用Java的方式设计一个后序线索二叉树的方法

在Java中，你可以定义一哪激弊个类来表示后序线索二叉树，其中包含有头节点、尾节点和当前节点指针。你可以使用递归或迭代方法遍历整棵树，并创建线索，即存储前驱和后继节点的指针。当访问到叶子节点时，需要将尾节点的指针指向它，尾节点铅隐的指李族针则指向头节点
// 定

3. java二叉树遍历问题

二叉树具有以下重要性质：
性质1 二叉树第i层上的结点数目最多为2i-1(i≥1)。
证明：用数学归纳法证明：
归纳基础：i=1时，有2i-1=20=1。因为第1层上只有一个根结点，所以命题成立。
归纳假设：假设对所有的j(1≤j<i)命题成立，即第j层上至多有2j-1个结点，证明j=i时命题亦成立。
归纳步骤：根据归纳假设，第i-1层上至多有2i-2个结点。由于二叉树的每个结点至多有两个孩子，故第i层上的结点数至多是第i-1层上的最大结点数的2倍。即j=i时，该层上至多有2×2i-2=2i-1个结点，故命题成立。

性质2 深度为k的二叉树至多有2k-1个结点(k≥1)。
证明：在具有相同深度的二叉树中，仅当每一层都含有最大结点数时，其树中结点数最多。因此利用性质1可得，深度为k的二叉树的结点数至多为：
20+21+…+2k-1=2k-1
故命题正确。

性质3 在任意-棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则no=n2+1。
证明：因为二叉树中所有结点的度数均不大于2，所以结点总数(记为n)应等于0度结点数、1度结点(记为n1)和2度结点数之和：
n=no+n1+n2 (式子1)
另一方面，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：
nl+2n2
树中只有根结点不是任何结点的孩子，故二叉树中的结点总数又可表示为：
n=n1+2n2+1 (式子2)
由式子1和式子2得到：
no=n2+1

满二叉树和完全二叉树是二叉树的两种特殊情形。
1、满二叉树(FullBinaryTree)
一棵深度为k且有2k-1个结点的二又树称为满二叉树。
满二叉树的特点：
（1） 每一层上的结点数都达到最大值。即对给定的高度，它是具有最多结点数的二叉树。
（2） 满二叉树中不存在度数为1的结点，每个分支结点均有两棵高度相同的子树，且树叶都在最下一层上。
图(a)是一个深度为4的满二叉树。

2、完全二叉树(Complete BinaryTree)
若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。
特点：
（1） 满二叉树是完全二叉树，完全二叉树不一定是满二叉树。
（2） 在满二叉树的最下一层上，从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。
（3） 在完全二叉树中，若某个结点没有左孩子，则它一定没有右孩子，即该结点必是叶结点。
如图(c)中，结点F没有左孩子而有右孩子L，故它不是一棵完全二叉树。
图(b)是一棵完全二叉树。

性质4 具有n个结点的完全二叉树的深度为

证明：设所求完全二叉树的深度为k。由完全二叉树定义可得：
深度为k得完全二叉树的前k-1层是深度为k-1的满二叉树，一共有2k-1-1个结点。
由于完全二叉树深度为k，故第k层上还有若干个结点，因此该完全二叉树的结点个数：
n>2k-1-1。
另一方面，由性质2可得：
n≤2k-1，
即：2k-1-l<n≤2k-1
由此可推出：2k-1≤n<2k，取对数后有：
k-1≤lgn<k
又因k-1和k是相邻的两个整数，故有
,
由此即得：

注意：
的证明

4. 二叉树的java实现与几种遍历

二叉树的定义

二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.

从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式

二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历

• 前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树

• 中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树

• 后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点

其中前，后，中指的是每次遍历时候的根节点被遍历的顺序

具体实现看下图：

5. Java数据结构二叉树深度递归调用算法求内部算法过程详解

二叉树
1
2 3
4 5 6 7
这个二叉树的深度是3，树的深度是最大结点所在的层，这里是3.

应该计算所有结点层数，选择最大的那个。

根据上面的二叉树代码，递归过程是：

f(1)=f(2)+1 > f(3) +1 ? f(2) + 1 : f(3) +1

f(2) 跟f(3)计算类似上面，要计算左右结点，然后取大者

所以计算顺序是f(4.left) = 0, f(4.right) = 0

f(4) = f(4.right) + 1 = 1

然后计算f(5.left) = 0,f(5.right) = 0

f(5) = f(5.right) + 1 =1

f(2) = f(5) + 1 =2

f(1.left) 计算完毕，计算f(1.right) f(3) 跟计算f(2)的过程一样。

得到f(3) = f(7) +1 = 2

f(1) = f(3) + 1 =3

if(depleft>depright){
returndepleft+1;
}else{
returndepright+1;
}

只有left大于right的时候采取left +1，相等是取right

6. 写一个java层次遍历二叉树,简单点就可以,我要的是代码,不是纯文字说明

public class BinaryNode {
Object element;
BinaryNode left;
BinaryNode right;

}

import java.util.*;

public class Queue {

protected LinkedList list;

// Postcondition: this Queue object has been initialized.
public Queue() {

list = new LinkedList();

} // default constructor

// Postcondition: the number of elements in this Queue object has been
// returned.
public int size() {

return list.size();

} // method size

// Postcondition: true has been returned if this Queue object has no
// elements. Otherwise, false has been returned.
public boolean isEmpty() {

return list.isEmpty();

} // method isEmpty

// Postconditon: A of element has been inserted at the back of this
// Queue object. The averageTime (n) is constant and
// worstTime (n) is O (n).
public void enqueue(Object element) {

list.addLast(element);

} // method enqueue

// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: The element that was at the front of this Queue object -
// just before this method was called -- has been removed
// from this Queue object and returned.
public Object dequeue() {

return list.removeFirst();

} // method dequeue

// Precondition: this Queue object is not empty. Otherwise,
// NoSuchElementException will be thrown.
// Postcondition: the element at index 0 in this Queue object has been
// returned.
public Object front() {

return list.getFirst();

} // method front

} // Queue class

import java.io.IOException;

public class BinaryTree {
BinaryNode root;

public BinaryTree() {
super();
// TODO 自动生成构造函数存根
root=this.createPre();
}

public BinaryNode createPre()
//按照先序遍历的输入方法，建立二叉树
{
BinaryNode t=null;
char ch;
try {
ch = (char)System.in.read();

if(ch==' ')
t=null;
else
{
t=new BinaryNode();
t.element=(Object)ch;
t.left=createPre();
t.right=createPre();
}
} catch (IOException e) {
// TODO 自动生成 catch 块
e.printStackTrace();
}
return t;
}

public void inOrder()
{
this.inOrder(root);
}

public void inOrder(BinaryNode t)
//中序遍历二叉树
{
if(t!=null)
{
inOrder(t.left);
System.out.print(t.element);
inOrder(t.right);
}
}

public void postOrder()
{
this.postOrder(root);
}

public void postOrder(BinaryNode t)
//后序遍历二叉树
{
if(t!=null)
{
postOrder(t.left);
System.out.print(t.element);
postOrder(t.right);
}
}

public void preOrder()
{
this.preOrder(root);
}
public void preOrder(BinaryNode t)
//前序遍历二叉树
{
if(t!=null)
{
System.out.print(t.element);
preOrder(t.left);
preOrder(t.right);
}
}

public void breadthFirst()
{
Queue treeQueue=new Queue();
BinaryNode p;
if(root!=null)
treeQueue.enqueue(root);
while(!treeQueue.isEmpty())
{
System.out.print(((BinaryNode)(treeQueue.front())).element);
p=(BinaryNode)treeQueue.dequeue();
if(p.left!=null)
treeQueue.enqueue(p.left);
if(p.right!=null)
treeQueue.enqueue(p.right);
}
}
}

public class BinaryTreeTest {

/**
* @param args
*/
public static void main(String[] args) {
// TODO 自动生成方法存根
BinaryTree tree = new BinaryTree();

System.out.println("先序遍历：");
tree.preOrder();
System.out.println();

System.out.println("中序遍历：");
tree.inOrder();
System.out.println();

System.out.println("后序遍历：");
tree.postOrder();
System.out.println();

System.out.println("层次遍历：");
tree.breadthFirst();
System.out.println();
}

}

7. 如果想成为一个程序员应该学习什么知识

声明：以后计算机也就没什么前景了 只能成为一个辅助工具
（1） 熟练掌握基本算法和数据结构，用C语言编制程序；
（2） 掌握数据结构、程序变速器和操作系统的基础知识；
（3） 了解软件工程、数据库、多媒体和网络的基础知识；
（4） 掌握数制、机内代码及其算术运算和逻辑运算的基础知识；
（5） 了解计算机的体系结构和主要部件的基础知识。
1.1按照软件设计说明书，能熟练使用下列程序语言编制程序
1.1.1C（美国标准）
1.2理解给定程序的功能，能发现程序中的错误并加以纠正
1.3具有良好的程序编制风格
1.4基本算法
1.4.1查找、更新、排序、合并及字符处理
1.4.2迭代、插值、数值积分、矩阵计算、议程求解和搜索求解
1.5程序编制方法
1.5.1分支、循环、子程序（过程和函数）、递归
1.5.2输入输出和文件的处理
模块2：基础知识（程序员级）
2.1软件基础知识
2.1.1数据结构基础
数组、记录、列表（list）、队列、栈（stack）、堆（heap）、树和二叉树的定义、存储和操作
2.1.2程序语言基础知识
·汇编、编译、解释系统的基础知识
·程序语言的数据类型
·程序语言的控制结构
2.1.3操作系统基础知识
·操作系统的类型和功能
·操作系统的层次结构和进程概念
·作业、处理机、存储、文件和设备等管理的基础知识
2.1.4软件工程基础知识
·软件生命周期各阶段的任务
·结构化分析和设计方法
·面向对象基本概念
·软件开发工具与环境基础知识
2.1.5数据库基础知识
·数据库模型
·数据库系统的结构
·SQL的使用初步
·常用数据库管理系统的知识
2.1.6多媒体基础知识
·多媒体基本概念
·常用图象文件
·简单图形（线段和圆）的计算机图示
2.2硬件基础知识
2.2.1数制及其转换
·二进制、十进制和十六进制等常用数制及其相互转换
2.2.2机内代码
·原码、补码、反码、移码
·定点数与浮点数的机内表示
·ASCII码及汉字编码等常用的编码
·奇偶校验码、海明码、循环冗余码（CRC）等常用校验方法
2.2.3算术运算和逻辑运算
·计算机中的二进制数运算方法
·逻辑代数的基本运算和逻辑表达式的化简
2.2.4计算机的体系结构和主要部件
·中央处理器CPU、存储器和输入/输出设备
·总线结构、指令流和数据流
2.2.5指令系统
·常用的寻址方式
·指令的格式、分类及功能
·指令的执行过程
2.3网络基础知识
2.3.1网络的功能、分类与组成
2.3.2网络协议与标准
2.3.3网络结构与通信
2.3.4网络的安全性
2.3.5Client-Server结构
2.3.6Internet和Intranet初步