「二叉树与算法java」二叉树常用算法
本篇文章给大家谈谈二叉树与算法java，以及二叉树常用算法对应的知识点，希望对各位有所帮助，不要忘了收藏本站喔。
本文目录一览：
- 1、java构建二叉树算法
- 2、二叉树的java实现与几种遍历
- 3、用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
- 4、java实现二叉树的问题
- 5、Java数据结构二叉树深度递归调用算法求内部算法过程详解
java构建二叉树算法
//******************************************************************************************************//
//*****本程序包括简单的二叉树类的实现和前序,中序,后序,层次遍历二叉树算法,*******//
//******以及确定二叉树的高度,制定对象在树中的所处层次以及将树中的左右***********//
//******孩子节点对换位置,返回叶子节点个数删除叶子节点,并输出所删除的叶子节点**//
//*******************************CopyRight By phoenix*******************************************//
//************************************Jan 12,2008*************************************************//
//****************************************************************************************************//
public class BinTree {
public final static int MAX=40;
private Object data; //数据元数
private BinTree left,right; //指向左,右孩子结点的链
BinTree []elements = new BinTree[MAX];//层次遍历时保存各个节点
int front;//层次遍历时队首
int rear;//层次遍历时队尾
public BinTree()
{
}
public BinTree(Object data)
{ //构造有值结点
this.data = data;
left = right = null;
}
public BinTree(Object data,BinTree left,BinTree right)
{ //构造有值结点
this.data = data;
this.left = left;
this.right = right;
}
public String toString()
{
return data.toString();
}//前序遍历二叉树
public static void preOrder(BinTree parent){
if(parent == null)
return;
System.out.print(parent.data+" ");
preOrder(parent.left);
preOrder(parent.right);
}//中序遍历二叉树
public void inOrder(BinTree parent){
if(parent == null)
return;
inOrder(parent.left);
System.out.print(parent.data+" ");
inOrder(parent.right);
}//后序遍历二叉树
public void postOrder(BinTree parent){
if(parent == null)
return;
postOrder(parent.left);
postOrder(parent.right);
System.out.print(parent.data+" ");
}// 层次遍历二叉树
public void LayerOrder(BinTree parent)
{
elements[0]=parent;
front=0;rear=1;
while(frontrear)
{
try
{
if(elements[front].data!=null)
{
System.out.print(elements[front].data + " ");
if(elements[front].left!=null)
elements[rear++]=elements[front].left;
if(elements[front].right!=null)
elements[rear++]=elements[front].right;
front++;
}
}catch(Exception e){break;}
}
}//返回树的叶节点个数
public int leaves()
{
if(this == null)
return 0;
if(left == nullright == null)
return 1;
return (left == null ? 0 : left.leaves())+(right == null ? 0 : right.leaves());
}//结果返回树的高度
public int height()
{
int heightOfTree;
if(this == null)
return -1;
int leftHeight = (left == null ? 0 : left.height());
int rightHeight = (right == null ? 0 : right.height());
heightOfTree = leftHeightrightHeight?rightHeight:leftHeight;
return 1 + heightOfTree;
}
//如果对象不在树中,结果返回-1;否则结果返回该对象在树中所处的层次,规定根节点为第一层
public int level(Object object)
{
int levelInTree;
if(this == null)
return -1;
if(object == data)
return 1;//规定根节点为第一层
int leftLevel = (left == null?-1:left.level(object));
int rightLevel = (right == null?-1:right.level(object));
if(leftLevel0rightLevel0)
return -1;
levelInTree = leftLevelrightLevel?rightLevel:leftLevel;
return 1+levelInTree;
}
//将树中的每个节点的孩子对换位置
public void reflect()
{
if(this == null)
return;
if(left != null)
left.reflect();
if(right != null)
right.reflect();
BinTree temp = left;
left = right;
right = temp;
}// 将树中的所有节点移走,并输出移走的节点
public void defoliate()
{
String innerNode = "";
if(this == null)
return;
//若本节点是叶节点，则将其移走
if(left==nullright == null)
{
System.out.print(this + " ");
data = null;
return;
}
//移走左子树若其存在
if(left!=null){
left.defoliate();
left = null;
}
//移走本节点，放在中间表示中跟移走...
innerNode += this + " ";
data = null;
//移走右子树若其存在
if(right!=null){
right.defoliate();
right = null;
}
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
BinTree e = new BinTree("E");
BinTree g = new BinTree("G");
BinTree h = new BinTree("H");
BinTree i = new BinTree("I");
BinTree d = new BinTree("D",null,g);
BinTree f = new BinTree("F",h,i);
BinTree b = new BinTree("B",d,e);
BinTree c = new BinTree("C",f,null);
BinTree tree = new BinTree("A",b,c);
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
System.out.println("--------------------------------------");
tree.reflect();
System.out.println("交换每个节点的孩子节点后......");
System.out.println("前序遍历二叉树结果: ");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍历二叉树结果: ");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍历二叉树结果: ");
tree.postOrder(tree);
System.out.println();
System.out.println("层次遍历二叉树结果: ");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的层次: "+tree.level("F"));
System.out.println("这棵二叉树的高度: "+tree.height());
}
二叉树的java实现与几种遍历
二叉树的定义
二叉树(binary tree)是结点的有限集合，这个集合或者空，或者由一个根及两个互不相交的称为这个根的左子树或右子树构成.
从定义可以看出，二叉树包括：1.空树 2.只有一个根节点 3.只有左子树 4.只有右子树 5.左右子树都存在 有且仅有这5种表现形式
二叉树的遍历分为三种：前序遍历 中序遍历 后序遍历
前序遍历：按照“根左右”,先遍历根节点，再遍历左子树 ，再遍历右子树
中序遍历：按照“左根右“,先遍历左子树，再遍历根节点，最后遍历右子树
后续遍历：按照“左右根”，先遍历左子树，再遍历右子树，最后遍历根节点
其中前，后，中指的是每次遍历时候的根节点被遍历的顺序
具体实现看下图：
用JAVA语言实现二叉树的层次遍历的非递归算法及查找算法。
先序非递归算法
【思路】
假设：T是要遍历树的根指针，若T != NULL
对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。
问题：如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取T的右子树的根指针？
方法1：访问T-data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
方法2：访问T-data后，将T-rchild入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T-rchild，出栈，遍历以该指针为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法一
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T-data) ;
Push(S,T);
T = T-lchild;
}
if( !StackEmpty(S) ){
Pop(S,T);
T = T-rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 基于方法二
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T-data);
Push(S, T-rchild);
T = T-lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。
问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取T指针？
方法：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T-data，再中序遍历T的右子树。
【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T-lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T-data);
T = T-rchild;
}
}
}
进一步考虑：对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】
T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法，结点入栈时，配一个标志tag一同入栈(0：遍历左子树前的现场保护，1：遍历右子树前的现场保护)。
首先将T和tag(为0)入栈，遍历左子树；返回后，修改栈顶tag为1，遍历右子树；最后访问根结点。 [Page]
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T-lchild;
}
while ( !StackEmpty(S) GetTopTag(S)==1){
Pop(S, T);
Visit(T-data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T-rchild;
}else break;
}
}
java实现二叉树的问题
/**
* 二叉树测试二叉树顺序存储在treeLine中，递归前序创建二叉树。另外还有能
* 够前序、中序、后序、按层遍历二叉树的方法以及一个返回遍历结果asString的
* 方法。
*/
public class BitTree {
public static Node2 root;
public static String asString;
//事先存入的数组,符号#表示二叉树结束。
public static final char[] treeLine = {'a','b','c','d','e','f','g',' ',' ','j',' ',' ','i','#'};
//用于标志二叉树节点在数组中的存储位置，以便在创建二叉树时能够找到节点对应的数据。
static int index;
//构造函数
public BitTree() {
System.out.print("测试二叉树的顺序表示为：");
System.out.println(treeLine);
this.index = 0;
root = this.setup(root);
}
//创建二叉树的递归程序
private Node2 setup(Node2 current) {
if (index = treeLine.length) return current;
if (treeLine[index] == '#') return current;
if (treeLine[index] == ' ') return current;
current = new Node2(treeLine[index]);
index = index * 2 + 1;
current.left = setup(current.left);
index ++;
current.right = setup(current.right);
index = index / 2 - 1;
return current;
}
//二叉树是否为空。
public boolean isEmpty() {
if (root == null) return true;
return false;
}
//返回遍历二叉树所得到的字符串。
public String toString(int type) {
if (type == 0) {
asString = "前序遍历：\t";
this.front(root);
}
if (type == 1) {
asString = "中序遍历：\t";
this.middle(root);
}
if (type == 2) {
asString = "后序遍历：\t";
this.rear(root);
}
if (type == 3) {
asString = "按层遍历：\t";
this.level(root);
}
return asString;
}
//前序遍历二叉树的循环算法，每到一个结点先输出，再压栈，然后访问它的左子树，
//出栈，访问其右子树，然后该次循环结束。
private void front(Node2 current) {
StackL stack = new StackL((Object)current);
do {
if (current == null) {
current = (Node2)stack.pop();
current = current.right;
} else {
asString += current.ch;
current = current.left;
}
if (!(current == null)) stack.push((Object)current);
} while (!(stack.isEmpty()));
}
//中序遍历二叉树
private void middle(Node2 current) {
if (current == null) return;
middle(current.left);
asString += current.ch;
middle(current.right);
}
//后序遍历二叉树的递归算法
private void rear(Node2 current) {
if (current == null) return;
rear(current.left);
rear(current.right);
asString += current.ch;
}
}
/**
* 二叉树所使用的节点类。包括一个值域两个链域
*/
public class Node2 {
char ch;
Node2 left;
Node2 right;
//构造函数
public Node2(char c) {
this.ch = c;
this.left = null;
this.right = null;
}
//设置节点的值
public void setChar(char c) {
this.ch = c;
}
//返回节点的值
public char getChar() {
return ch;
}
//设置节点的左孩子
public void setLeft(Node2 left) {
this.left = left;
}
//设置节点的右孩子
public void setRight (Node2 right) {
this.right = right;
}
//如果是叶节点返回true
public boolean isLeaf() {
if ((this.left == null) (this.right == null)) return true;
return false;
}
}
一个作业题，里面有你要的东西。
主函数自己写吧。当然其它地方也有要改的。
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(depleftdepright){
return depleft+1;
}else{
return depright+1;
}
只有left大于right的时候采取left +1，相等是取right
关于二叉树与算法java和二叉树常用算法的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息，记得收藏关注本站。