java二叉树递归
Ⅰ 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
Ⅱ 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)了。
Ⅲ 二叉树先序遍历递归算法和非递归算法本质区别
在前面一文，说过二叉树的递归遍历算法（二叉树先根（先序）遍历的改进），此文主要讲二叉树的非递归算法，采用栈结构
总结先根遍历得到的非递归算法思想如下：
1）入栈，主要是先头结点入栈，然后visit此结点
2）while，循环遍历当前结点，直至左孩子没有结点
3）if结点的右孩子为真，转入1）继续遍历，否则退出当前结点转入父母结点遍历转入1）
先看符合此思想的算法：
[cpp] view plain print?
int (const BiTree &T, int (*VisitNode)(TElemType data))
{
if (T == NULL)
{
return -1;
}
BiTNode *pBiNode = T;
SqStack S;
InitStack(&S);
Push(&S, (SElemType)T);
while (!IsStackEmpty(S))
{
while (pBiNode)
{
VisitNode(pBiNode->data);
if (pBiNode != T)
{
Push(&S, (SElemType)pBiNode);
}
pBiNode = pBiNode->lchild;
}
if(pBiNode == NULL)
{
Pop(&S, (SElemType*)&pBiNode);
}
if ( pBiNode->rchild == NULL)
{
Pop(&S, (SElemType*)&pBiNode); //如果此时栈已空，就有问题
}
pBiNode = pBiNode->rchild;
}
return 0;
}
Ⅳ 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊
1、首先要定义两个类：结点类和二叉树类。
Ⅳ 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
12345if(depleft>depright){ return depleft+1;}else{ return depright+1;}
只有left大于right的时候采取left
+1，相等是取right
Ⅵ 假设二叉树以二叉链表作为存储结构，试设计一个计算二叉树叶子结点树的递归算 法 要求用递归算法啊
叶子节点：没有孩子节点的节点
下面我给出两种求解思路，其中就包括你要的递归求解。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+"]";
}
}
Ⅶ 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;
}
}
一个作业题，里面有你要的东西。
主函数自己写吧。当然其它地方也有要改的。