java二叉树递归算法
Ⅰ java 递归 算 二叉树 层级
层次遍历从方法上不具有递归的形式，所以一般不用递归实现。当然了，非要写成递归肯定也是可以的，大致方法如下。 void LevelOrder(BTree T, int cnt) { BTree level = malloc(sizeof(struct BTNode)*cnt); if(level==NULL) return; int i=0,rear=0; if(cnt==0) return; for(i=0; i<cnt; i++){ printf("%c ",T[i].data); if(T[i].lchild) level[rear++]=*T[i].lchild; if(T[i].rchild) level[rear++]=*T[i].rchild; } printf("\n"); LevelOrder(level, rear); free(level); } 补充一下，在main里面调用的时候就得用LevelOrder(T,1)了。
Ⅱ 有关二叉树递归的算法
靠，缩进全被网络搞乱了，自己排版
#include <iostream>
using namespace std;
//二叉树节点
struct BiTreeNode{
int data;
BiTreeNode *left;
BiTreeNode *right;
};
//写一个类，方便二叉树的建立和删除
class BiTree{
private:
void deleteAllNode(BiTreeNode *root);
public:
BiTreeNode *root;
BiTree();
~BiTree();
void CreateTree();
void deleteLeaves(BiTreeNode *root);
bool DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather);
void FindMaxValue(BiTreeNode *currentNode, int *maxValue);
void ExchangeLeftAndRight(BiTreeNode *currentNode);
void OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather); //不好意思，用了拼音
};
BiTree::BiTree()
{
root = NULL;
}
BiTree::~BiTree()
{
deleteAllNode(root);
}
void BiTree::deleteAllNode(BiTreeNode *root)
{
if (root == NULL) return;
deleteAllNode(root->left);
deleteAllNode(root->right);
cout << root->data << ' '; //用来查看当前节点是不是被删除。
delete root;
}
//手动建立一个二叉树用于测试
// 1
// / \
// 2 3
// \ /
// 4 5
void BiTree::CreateTree()
{
if (root) return;
root = new BiTreeNode;
root->data = 1;
root->left = new BiTreeNode;
root->left->data = 2;
root->right = new BiTreeNode;
root->right->data = 3;
BiTreeNode *p;
p = root->left;
p->left = NULL;
p->right = new BiTreeNode;
p->right->data = 4;
p->right->left = p->right->right = NULL;
p= root->right;
p->left = new BiTreeNode;
p->left->data = 5;
p->left->left = p->left->right = NULL;
p->right = NULL;
}
//用递归算法删除叶子
void BiTree::deleteLeaves(BiTreeNode *root)
{
if (root == NULL) return;
if (!root->left && !root->right) return; //表示是根节点(或者出错，跑到叶子节点了，这种情况应该不会)，不删除
if (root->left) //当前节点有左子树
{
if (root->left->left || root->left->right) //左子树不是叶子
deleteLeaves(root->left);
else //当前节点的左子节点是叶子
{
delete root->left;
root->left = NULL;
}
}
if (root->right)
{
if (root->right->left || root->right->right)
deleteLeaves(root->right);
else //当前节点的右子节点是叶子
{
delete root->right;
root->right = NULL;
}
}
}
int depth = 0; //一个用来存储深度的全局变量，虽然在实际编程中这样用不好
//但一切为了方便。
//节点p的深度,递归法
bool BiTree::DepthOfTheNode(BiTreeNode *currentNode,BiTreeNode *p, int depthOfFather)
{
if (currentNode == NULL) return false;
if (currentNode == p) //当前节点为要找的节点
{
depth = depthOfFather + 1;
return true;;
}
if (DepthOfTheNode(currentNode->left, p, depthOfFather+1)) //找当前节点的左子树
return true;
else
return DepthOfTheNode(currentNode->right, p, depthOfFather+1);
}
//用递归找最大值，最大值存储在maxValue所指的内存 ,这里使用前序遍历
void BiTree::FindMaxValue(BiTreeNode *currentNode, int *maxValue)
{
if (currentNode == NULL) return;
*maxValue = *maxValue > currentNode->data ? *maxValue : currentNode->data;
FindMaxValue(currentNode->left, maxValue); //遍历左子树
FindMaxValue(currentNode->right, maxValue);
}
//交换左右，用前序遍历
void BiTree::ExchangeLeftAndRight(BiTreeNode *currentNode)
{
if (currentNode == NULL) return;
BiTreeNode *temp;
temp = currentNode->left;
currentNode->left = currentNode->right;
currentNode->right = temp;
ExchangeLeftAndRight(currentNode->left);
ExchangeLeftAndRight(currentNode->right);
}
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
void BiTree::OutputValueAndDepthByQIANXU(BiTreeNode *currentNode, int depthOfFather)
{
if (currentNode == NULL) return;
cout << "节点：" << currentNode->data;
cout << "\t深度：" << depthOfFather+1 << endl;
OutputValueAndDepthByQIANXU(currentNode->left, depthOfFather+1);
OutputValueAndDepthByQIANXU(currentNode->right, depthOfFather+1);
}
int main()
{
BiTree bt;
bt.CreateTree();
//求p的深度
bt.DepthOfTheNode(bt.root, bt.root->left->right, 0);
cout << "深度:" << depth << endl;
//找最大值
int maxValue;
bt.FindMaxValue(bt.root, &maxValue);
cout << "最大值为：" << maxValue << endl;
//交换左右节点
bt.ExchangeLeftAndRight(bt.root);
//以前序次序输出一棵二叉树所有结点的数据值及结点所在层次
bt.OutputValueAndDepthByQIANXU(bt.root, 0);
//删除叶子节点
bt.deleteLeaves(bt.root);
return 0;
}
Ⅲ 设二叉树的存储结构为二叉链表，编写有关二叉树的递归算法：
给了一个程序给你参考，有前中后序遍历，实现了前5个功能。
提示：8功能可以用任意一种遍历方法，在程序中，将打印字符的部分换成自己的判断程序即可。
6功能用后续遍历，当遍历到任意一节点时，判断其孩子是不是叶子，是就删除。
7功能参考求广度的实现】
9功能参考6功能，用前序遍历也可以
10功能也参考求广度的方法
程序：
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <time.h>
#define NUM_NODE 12
#define MOST_DEPTH 10
typedef struct BiTree{
int data;
BiTree *lchild;
BiTree *rchild;
}BiTree;
typedef struct Answear{
int Degree0;
int Degree1;
int Degree2;
int Depth;
} Answear;
BiTree* CreateTree(int n)
{
BiTree *t;
if (n <= 0 || n> NUM_NODE) return NULL;
if (!(t = (BiTree*)malloc(sizeof(BiTree))))
return NULL;
t->data = n;
printf("%d ", t->data);
t->lchild = CreateTree(2*n);
t->rchild = CreateTree(2*n+1);
return t;
}
void FreeTree(BiTree *t)
{
if (t)
{
if (t->lchild)
FreeTree(t->lchild);
if (t->rchild)
FreeTree(t->rchild);
printf("%d ", t->data);
free(t);
}
}
//中序遍历
void InOrder(BiTree *t)
{
BiTree **stack, **top, *p;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
}
else
{
p = *--top;//p出栈
if (p) printf("%d ", p->data);
p = p->rchild;
}
}
//前序遍历
void PreOrder(BiTree *t)
{
BiTree **stack, **top, *p;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
p = t;
while (p || top>stack)
if (p)
{
*top++ = p;
if (p) printf("%d ", p->data);
p = p->lchild;
}
else
{
p = *--top;
p = p->rchild;
}
}
//后序遍历
void PostOrder(BiTree *t)
{
BiTree **stack, **top, *p, *p_old, *p_new;
int Flag;
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
top = stack;
Flag = 0;
*top++ = t;
while (top > stack)
{
p = *(top-1);
if (p->lchild && !Flag)
*top++ = p->lchild;
else
{
if (p->rchild)
{
*top++ = p->rchild;
Flag = 0;
}
else
{
p_old = *--top;
printf("%d ", p_old->data);
while (top > stack)
{
p_new = *(top-1);
if (p_old == p_new->lchild)
{
Flag = 1;
break;
}
else
{
p_new = *--top;
printf("%d ", p_new->data);
p_old = p_new;
Flag = 0;
}
}
}
}
}
}
//中序遍历求结点的深度和度为0，1,2的结点数，结果保存在pAns指的。。。
void InOrderDO(BiTree *t , Answear * pAns)
{
//遍历用的数据
BiTree **stack, **top, *p;
//求深度的数据
int curDeep, MostDeep;
//创建堆栈
if (!(stack = (BiTree**)malloc(NUM_NODE * sizeof(BiTree))))
{
printf("InOrder failed for memery\n");
return;
}
//初始化堆栈
top = stack;
p = t;
//初始化数据
curDeep = MostDeep = 0;
pAns->Degree0 = pAns->Degree1 = pAns->Degree2 = 0;
//遍历循环
while (p || top>stack)//p不为NULL，堆栈不空
if (p)
{
*top++ = p;//p入堆栈
p = p->lchild;
curDeep++;
if (MostDeep < curDeep) MostDeep = curDeep; //保存最深度
}
else
{
p = *--top;//p出栈
curDeep--;
//if (p) printf("%d ", p->data); //Visit结点
//计算个结点的度
if (p->lchild && p->rchild) pAns->Degree2++;
else if (p->lchild || p->rchild) pAns->Degree1++;
else pAns->Degree0++;
p = p->rchild;
}
//得到深度
pAns->Depth = MostDeep;
return ;
}
//前序递归求广度
void Pre(BiTree *T, int* woed, int depth)
{
woed[depth]++;
if (T->lchild) Pre(T->lchild, woed, depth+1);
if (T->rchild) Pre(T->rchild, woed, depth+1);
}
//求广度的程序，返回值为广度
int GetTreeWidth(BiTree *root)
{
int i, WidthOfEachDepth[MOST_DEPTH]={0};
Pre(root, WidthOfEachDepth, 0);
for (i=1; i<MOST_DEPTH; i++)
if (WidthOfEachDepth[0] < WidthOfEachDepth[i])
WidthOfEachDepth[0] = WidthOfEachDepth[i];
return WidthOfEachDepth[0];
}
int main()
{
BiTree *root;
Answear ans;
printf("Create Tree\n");
root = CreateTree(1);
printf("\nInOrder\n");
InOrder(root);
printf("\nPreOrder\n");
PreOrder(root);
printf("\nPostOrder\n");
PostOrder(root);
InOrderDO(root, &ans);
printf("\nTheMostDepth is : %d\n", ans.Depth);
printf("TheMostWidth is : %d\n", GetTreeWidth(root));
printf("Each Degree (0,1,2)is: (%d, %d, %d)\n",
ans.Degree0, ans.Degree1, ans.Degree2);
printf("\nFree Tree\n");
FreeTree(root);
return 0;
}
Ⅳ 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
Ⅳ 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊
1、首先要定义两个类：结点类和二叉树类。
Ⅵ 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(front<rear)
{
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 == null&&right == 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 = leftHeight<rightHeight?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(leftLevel<0&&rightLevel<0)
return -1;
levelInTree = leftLevel<rightLevel?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==null&&right == 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());
}
Ⅶ 二叉树几个常用的递归算法
给定一个仅包含数字0-9的二叉树，每一条从根节点到叶子节点的路径都可以用一个数字表示。
例如根节点到叶子节点的一条路径是1->2-> 1->2->3,那么这条路径就用123来代替。
找出根节点到叶子节点的所有路径表示的数字之和
例如：
这棵二叉树一共有两条路径；
根节点到叶子节点的路径1->2用数字12代替
根节点到叶子结点的路径1->3用数字13代替
所以答案为12+13=25
利用先序遍历，直接通过一个数字传递路径上数字和，遇到叶节点返回左右子树相加的结果。
给定一棵二叉树，判断其是否是自身的镜像(即：是否对称)。希望你可以用递归和迭代两种方法解决这个问题。
Ⅷ 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊
叶子节点：没有孩子节点的节点
下面我给出两种求解思路，其中就包括你要的递归求解。Java版的示例代码如下：
packagecn.zifangsky.tree.binarytree.questions;
importorg.junit.Test;
importcn.zifangsky.queue.LinkQueue;
importcn.zifangsky.tree.binarytree.BinaryTreeNode;
/**
*求二叉树中叶子节点的个数
*@authorzifangsky
*
*/
publicclassQuestion2{
/**
*通过递归遍历获取叶子节点个数
*
*@时间复杂度O(n)
*@paramroot
*@return
*/
(BinaryTreeNode<Integer>root){
if(root==null){
return0;
}else{
if(root.getLeft()==null&&root.getRight()==null){//叶子节点
return1;
}else{//左子树叶子节点总数+右子树叶子节点总数
(root.getLeft())+getNumberOfLeavesByPreOrder(root.getRight());
}
}
}
/**
*使用层次遍历获取二叉树叶子节点个数
*
*@时间复杂度O(n)
*@paramroot
*/
(BinaryTreeNode<Integer>root){
intcount=0;//叶子节点总数
LinkQueue<BinaryTreeNode<Integer>>queue=newLinkQueue<>();
if(root!=null){
queue.enQueue(root);
}
while(!queue.isEmpty()){
BinaryTreeNode<Integer>temp=queue.deQueue();//出队
//叶子节点：左孩子节点和右孩子节点都为NULL的节点
if(temp.getLeft()==null&&temp.getRight()==null){
count++;
}else{
if(temp.getLeft()!=null){
queue.enQueue(temp.getLeft());
}
if(temp.getRight()!=null){
queue.enQueue(temp.getRight());
}
}
}
returncount;
}
/**
*测试用例
*/
@Test
publicvoidtestMethods(){
/**
*使用队列构造一个供测试使用的二叉树
*1
*23
*4567
*89
*/
LinkQueue<BinaryTreeNode<Integer>>queue=newLinkQueue<BinaryTreeNode<Integer>>();
BinaryTreeNode<Integer>root=newBinaryTreeNode<>(1);//根节点
queue.enQueue(root);
BinaryTreeNode<Integer>temp=null;
for(inti=2;i<10;i=i+2){
BinaryTreeNode<Integer>tmpNode1=newBinaryTreeNode<>(i);
BinaryTreeNode<Integer>tmpNode2=newBinaryTreeNode<>(i+1);
temp=queue.deQueue();
temp.setLeft(tmpNode1);
temp.setRight(tmpNode2);
if(i!=4)
queue.enQueue(tmpNode1);
queue.enQueue(tmpNode2);
}
System.out.println("叶子节点个数是："+getNumberOfLeavesByPreOrder(root));
System.out.println("叶子节点个数是："+getNumberOfLeavesByQueue(root));
}
}
输出如下：
叶子节点个数是：5
叶子节点个数是：5
附：上面代码中用到的两个类的定义：
i）BinaryTreeNode.java：
packagecn.zifangsky.tree.binarytree;
/**
*二叉树的单个节点定义
*@authorzifangsky
*
*@param<K>
*/
publicclassBinaryTreeNode<KextendsObject>{
privateKdata;//数据
privateBinaryTreeNode<K>left;//左孩子节点
privateBinaryTreeNode<K>right;//右孩子节点
publicBinaryTreeNode(Kdata){
this.data=data;
}
publicBinaryTreeNode(Kdata,BinaryTreeNode<K>left,BinaryTreeNode<K>right){
this.data=data;
this.left=left;
this.right=right;
}
publicKgetData(){
returndata;
}
publicvoidsetData(Kdata){
this.data=data;
}
publicBinaryTreeNode<K>getLeft(){
returnleft;
}
publicvoidsetLeft(BinaryTreeNode<K>left){
this.left=left;
}
publicBinaryTreeNode<K>getRight(){
returnright;
}
publicvoidsetRight(BinaryTreeNode<K>right){
this.right=right;
}
}
ii）LinkQueue.java：
packagecn.zifangsky.queue;
importcn.zifangsky.linkedlist.SinglyNode;
/**
*基于单链表实现的队列
*@authorzifangsky
*@param<K>
*/
publicclassLinkQueue<KextendsObject>implementsQueue<K>{
privateSinglyNode<K>frontNode;//队首节点
privateSinglyNode<K>rearNode;//队尾节点
publicLinkQueue(){
frontNode=null;
rearNode=null;
}
/**
*返回队列是否为空
*@时间复杂度O(1)
*@return
*/
@Override
publicbooleanisEmpty(){
return(frontNode==null);
}
/**
*返回存储在队列的元素个数
*@时间复杂度O(n)
*@return
*/
@Override
publicintsize(){
intlength=0;
SinglyNode<K>currentNode=frontNode;
while(currentNode!=null){
length++;
currentNode=currentNode.getNext();
}
returnlength;
}
/**
*入队：在链表表尾插入数据
*@时间复杂度O(1)
*@paramdata
*/
@Override
publicvoidenQueue(Kdata){
SinglyNode<K>newNode=newSinglyNode<K>(data);
if(rearNode!=null){
rearNode.setNext(newNode);
}
rearNode=newNode;
if(frontNode==null){
frontNode=rearNode;
}
}
/**
*出队：删除表头节点
*@时间复杂度O(1)
*@return
*/
@Override
publicKdeQueue(){
if(isEmpty()){
thrownewRuntimeException("QueueEmpty!");
}else{
Kresult=frontNode.getData();
if(frontNode==rearNode){
frontNode=null;
rearNode=null;
}else{
frontNode=frontNode.getNext();
}
returnresult;
}
}
/**
*返回队首的元素，但不删除
*@时间复杂度O(1)
*/
@Override
publicKfront(){
if(isEmpty()){
thrownewRuntimeException("QueueEmpty!");
}else{
returnfrontNode.getData();
}
}
/**
*遍历队列
*@时间复杂度O(n)
*@return
*/
@Override
publicvoidprint(){
SinglyNode<K>tmpNode=frontNode;
while(tmpNode!=null){
System.out.print(tmpNode.getData()+"");
tmpNode=tmpNode.getNext();
}
}
/**
*删除整个队列
*@时间复杂度O(1)
*@return
*/
@Override
publicvoiddeleteQueue(){
frontNode=null;
rearNode=null;
}
}
iii）SinglyNode.java：
packagecn.zifangsky.linkedlist;
/**
*单链表的定义
*
*@authorzifangsky
*@param<K>
*/
publicclassSinglyNode<KextendsObject>{
privateKdata;//数据
privateSinglyNode<K>next;//该节点的下个节点
publicSinglyNode(Kdata){
this.data=data;
}
publicSinglyNode(Kdata,SinglyNode<K>next){
this.data=data;
this.next=next;
}
publicKgetData(){
returndata;
}
publicvoidsetData(Kdata){
this.data=data;
}
publicSinglyNode<K>getNext(){
returnnext;
}
publicvoidsetNext(SinglyNode<K>next){
this.next=next;
}
@Override
publicStringtoString(){
return"SinglyNode[data="+data+"]";
}
}
Ⅸ 建立二叉树的递归算法怎样理解
不断地在纸上或脑子里执行每一步，在一点要深刻理解函数的调用和形参和实参的概念，还有return语句。熟能生巧一位牛人说的.
Ⅹ java二叉树中序遍历 的递归算法没有看懂。。search(data.getLeft());之后不就回到最左边的一个
最左边的节点是没有左子树和右子树的。
if(data.getLeft()!=null){ // 这里getLetf()为null
search(data.getLeft());
}
System.out.print(data.getObj()+","); //只有这句是执行的！
if(data.getRight()!=null){ // 这里getRight()为null
search(data.getRight());
}
然后就会退到上一个节点的遍历函数了。