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;
}
}
一個作業題，裡面有你要的東西。
主函數自己寫吧。當然其它地方也有要改的。