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());
}
然後就會退到上一個節點的遍歷函數了。