既然涉及到二叉樹了，遞歸就肯定存在了
在寧德等地區(qū)，都構(gòu)建了全面的區(qū)域性戰(zhàn)略布局，加強(qiáng)發(fā)展的系統(tǒng)性、市場前瞻性、產(chǎn)品創(chuàng)新能力，以專注、極致的服務(wù)理念，為客戶提供成都做網(wǎng)站、成都網(wǎng)站制作 網(wǎng)站設(shè)計(jì)制作按需網(wǎng)站制作,公司網(wǎng)站建設(shè),企業(yè)網(wǎng)站建設(shè),成都品牌網(wǎng)站建設(shè),成都全網(wǎng)營銷推廣,成都外貿(mào)網(wǎng)站制作,寧德網(wǎng)站建設(shè)費(fèi)用合理。
private Baumknoten deleteMaxValue() {
Baumknoten newRoot; //一個節(jié)點(diǎn)
if (this.rightTree == null) { //右子節(jié)點(diǎn) == null
newRoot = this.leftTree; //賦值
} else {
this.rightTree = this.rightTree.deleteMaxValue(); //本節(jié)點(diǎn) = 本節(jié)點(diǎn)的右子節(jié)點(diǎn)的這個方法（也就是你貼出來的方法）返回的節(jié)點(diǎn)。
newRoot = this; //節(jié)點(diǎn)賦值
}
return newRoot; //返回節(jié)點(diǎn)
}
這就是一個遞歸，或許樹的定義是左子節(jié)點(diǎn)比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)比父節(jié)點(diǎn)大，
但有些出路，不能肯定。
遞歸的意思就是在方法內(nèi)部調(diào)用自己，滿足一定條件后跳出，可以理解為循環(huán)，
但有些循環(huán)是不能實(shí)現(xiàn)某些遞歸能實(shí)現(xiàn)的功能的。
我給你講解下這個方法的意思吧：
其實(shí)這個方法的需求是找出二叉樹中最大的值，并返回。
假設(shè)樹的定義是左子節(jié)點(diǎn)比父節(jié)點(diǎn)小，右子節(jié)點(diǎn)比父節(jié)點(diǎn)大的常規(guī)樹：
進(jìn)入方法，定義一個節(jié)點(diǎn)，然后判斷當(dāng)前節(jié)點(diǎn)的右節(jié)點(diǎn)是不是空，如果是空就證
明當(dāng)前節(jié)點(diǎn)是最大值了，返回當(dāng)前節(jié)點(diǎn)就行了（但他返回的是當(dāng)前節(jié)點(diǎn)的左子節(jié)
點(diǎn)，詫異?。?，如果不是空就調(diào)用當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)的deleteMaxValue方法
（也就是你貼出來的方法，是自己，這就構(gòu)成了遞歸），并把右子節(jié)點(diǎn)的
deleteMaxValue方法的返回值返回到父節(jié)點(diǎn)的方法里，父節(jié)點(diǎn)的方法接收返回值
并返回給調(diào)用者，進(jìn)入右子節(jié)點(diǎn)的deleteMaxValue方法后，繼續(xù)上面的操作，直
到滿足了條件跳出為止，條件就是if (this.rightTree == null)。
典型的遞歸。
二叉樹
1
2??? 3
4 ?5 6 ?7
這個二叉樹的深度是3，樹的深度是最大結(jié)點(diǎn)所在的層，這里是3.
應(yīng)該計(jì)算所有結(jié)點(diǎn)層數(shù)，選擇最大的那個。
根據(jù)上面的二叉樹代碼，遞歸過程是：
f(1)=f(2)+1 f(3) +1 ? f(2) + 1 : f(3) +1
f(2) 跟f(3)計(jì)算類似上面，要計(jì)算左右結(jié)點(diǎn)，然后取大者
所以計(jì)算順序是f(4.left) = 0, f(4.right) = 0
f(4) = f(4.right) + 1 = 1
然后計(jì)算f(5.left) = 0,f(5.right) = 0
f(5) = f(5.right) + 1 =1
f(2) = f(5) + 1 =2
f(1.left) 計(jì)算完畢，計(jì)算f(1.right) f(3) 跟計(jì)算f(2)的過程一樣。
得到f(3) = f(7) +1 = 2
f(1) = f(3) + 1 =3
if(depleftdepright){
return?depleft+1;
}else{
return?depright+1;
}
只有l(wèi)eft大于right的時候采取left +1，相等是取right
#includestdio.h
#includestring.h
#includestdlib.h
#define Max 20 //結(jié)點(diǎn)的最大個數(shù)
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結(jié)點(diǎn)類型
typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結(jié)點(diǎn)數(shù)，leaf為葉子數(shù)
//基于先序遍歷算法創(chuàng)建二叉樹
//要求輸入先序序列，其中加入虛結(jié)點(diǎn)"#"以示空指針的位置
BinTree CreatBinTree(void){
BinTree T;
char ch;
if((ch=getchar())=='#')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode)); //生成結(jié)點(diǎn)
T-data=ch;
T-lchild=CreatBinTree(); //構(gòu)造左子樹
T-rchild=CreatBinTree(); //構(gòu)造右子樹
return(T);
}
}
//先序遍歷
void Preorder(BinTree T){
if(T){
printf("%c",T-data); //訪問結(jié)點(diǎn)
Preorder(T-lchild); //先序遍歷左子樹
Preorder(T-rchild); //先序遍歷右子樹
}
}
//中序遍歷
void Inorder(BinTree T){
if(T){
Inorder(T-lchild); //中序遍歷左子樹
printf("%c",T-data); //訪問結(jié)點(diǎn)
Inorder(T-rchild); //中序遍歷右子樹
}
}
//后序遍歷
void Postorder(BinTree T){
if(T){
Postorder(T-lchild); //后序遍歷左子樹
Postorder(T-rchild); //后序遍歷右子樹
printf("%c",T-data); //訪問結(jié)點(diǎn)
}
}
//采用后序遍歷求二叉樹的深度、結(jié)點(diǎn)數(shù)及葉子數(shù)的遞歸算法
int TreeDepth(BinTree T){
int hl,hr,max;
if(T){
hl=TreeDepth(T-lchild); //求左深度
hr=TreeDepth(T-rchild); //求右深度
max=hlhr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結(jié)點(diǎn)數(shù)
if(hl==0hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//主函數(shù)
void main(){
BinTree root;
int i,depth;
printf("\n");
printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結(jié)點(diǎn)，如ABD###CE##F##
root=CreatBinTree(); //創(chuàng)建二叉樹，返回根結(jié)點(diǎn)
do{ //從菜單中選擇遍歷方式，輸入序號。
printf("\t********** select ************\n");
printf("\t1: Preorder Traversal\n");
printf("\t2: Iorder Traversal\n");
printf("\t3: Postorder traversal\n");
printf("\t4: PostTreeDepth,Node number,Leaf number\n");
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",i); //輸入菜單序號（0-4）
switch (i){
case 1: printf("Print Bin_tree Preorder: ");
Preorder(root); //先序遍歷
break;
case 2: printf("Print Bin_Tree Inorder: ");
Inorder(root); //中序遍歷
break;
case 3: printf("Print Bin_Tree Postorder: ");
Postorder(root); //后序遍歷
break;
case 4: depth=TreeDepth(root); //求樹的深度及葉子數(shù)
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5: printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
}while(i!=0);
}
//按層遍歷
Levelorder( BinTNode *root){
BinTNode * q[Max]; //定義BinTNode類型的隊(duì)列 用于存放節(jié)點(diǎn) 隊(duì)列長最大為20個元素
int front=0,rear=0; //初始化隊(duì)列為空
BinTNode *p; //臨時節(jié)點(diǎn)指針
if(root!=NULL){ //將根節(jié)點(diǎn)進(jìn)隊(duì)
rear=(rear+1)%Max;
q[rear]=root;
}
while(front!=rear){
front=(front+1)%Max;
p=q[front]; //刪除隊(duì)首的元素 讓兩個節(jié)點(diǎn)（左右節(jié)點(diǎn)）孤立
printf("%c",p-data); //輸出隊(duì)列首元素的值
if(p-left!=null){ //如果存在左孩子節(jié)點(diǎn)，則左孩子節(jié)點(diǎn)進(jìn)入隊(duì)列
rear=(rear+1)%Max;
q[rear]=p-left;
}
if(p-right!=null){ //如果存在右孩子節(jié)點(diǎn)，則右孩子節(jié)點(diǎn)進(jìn)入隊(duì)列
rear=(rear+1)%Max;
q[rear]=p-right;
}
}
}
二叉樹，和數(shù)據(jù)庫的B樹操作流程是一樣的，例如：有如下字段
F,C,B,H,K,I；
如果要形成二叉樹的話，則，首先取第一個數(shù)據(jù)作為根節(jié)點(diǎn)，所以，現(xiàn)在是 F ，如果字段比根節(jié)點(diǎn)小，則保存在左子樹，如果比根節(jié)點(diǎn)大或者等于根節(jié)點(diǎn)則保存在右子樹，最后按左---根-----右輸出所以數(shù)據(jù)。
所以，實(shí)現(xiàn)的關(guān)鍵就是在于保存的數(shù)據(jù)上是否存在大小比較功能，而String類中compareTo()有這個能力,節(jié)點(diǎn)類要保存兩類數(shù)據(jù)，左節(jié)點(diǎn)，右節(jié)點(diǎn)
class Node
{
private String data;
private Node left;
private Node right;
public Node (String data){
this.data = data;
}
public void setLeft(Node left) {
this.left = left;
}
public void setRight(Node right){
this.right = right;
}
public String getDate() {
return this.data;
}
public Node getLeft(){
return this.left;
}
public Node getRight(){
return this.right;
}
public void addNode(Node newNode){
if(this.data.compareTo(newNode.data)=0) {
if(this.left == null){
this.left = newNode;
}else {
this.left.addNode(newNode);
}
}else {
if(this.right == null) {
this.right = newNode;
} else {
this.right.addNode(newNode);
}
}
}
public void printNode(){
if(this.left!= null){
this.left.printNode();
}
System.out.println(this.data);
if(this.right != null){
this.right.printNode();
}
}
}
class BinaryTree
{
private Node root = null;
public void add(String data) {
Node newNode = new Node(data);
if(this.root == null) {
this.root = newNode;
}else{
this.root.addNode(newNode);
}
}
public void print() {
this.root.printNode();
}
}
public class Hello
{
public static void main (String args[]) {
BinaryTree link = new BinaryTree();
link.add("F");
link.add("C");
link.add("B");
link.add("H");
link.add("K");
link.add("I");
link.print();
}
}
你一看就英文就知道什么意思了，應(yīng)該可以理解了
這個二叉樹捉摸不透就別琢磨了，開放中一般用不上
}
好了，代碼如下，自己運(yùn)行下，看下是否符合你的要求：
public class Test
{
static Node root;
static class Node
{
Node left;
Node right;
char data;
Node(char data)
{
this.data = data;
}
}
public static void main(String[] args)
{
String content = "welcomeyou";
for(int i=0;icontent.length();i++)
{
root = insert(root, content.charAt(i));
}
System.out.println("先序遍歷結(jié)果如下：");
perorder(root);
System.out.println("中序遍歷結(jié)果如下：");
inorder(root);
System.out.println("后序遍歷結(jié)果如下：");
postorder(root);
}
public static Node insert(Node node, char data)
{
if(node == null)
node = new Node(data);
else
{
if(node.data data)
node.left = insert(node.left,data);
else
node.right = insert(node.right,data);
}
return node;
}
public static void perorder(Node node)
{
if (node == null)
return;
System.out.println(node.data);
if (node.left != null)
perorder(node.left);
if (node.right != null)
perorder(node.right);
}
public static void inorder(Node node)
{
if (node == null)
return;
if (node.left != null)
inorder(node.left);
System.out.println(node.data);
if (node.right != null)
inorder(node.right);
}
public static void postorder(Node node)
{
if (node == null)
return;
if (node.left != null)
postorder(node.left);
if (node.right != null)
postorder(node.right);
System.out.println(node.data);
}
}
java構(gòu)造二叉樹，可以通過鏈表來構(gòu)造，如下代碼：
public?class?BinTree?{
public?final?static?int?MAX=40;
BinTree?[]elements?=?new?BinTree[MAX];//層次遍歷時保存各個節(jié)點(diǎn)
int?front;//層次遍歷時隊(duì)首
int?rear;//層次遍歷時隊(duì)尾
private?Object?data;?//數(shù)據(jù)元數(shù)
private?BinTree?left,right;?//指向左,右孩子結(jié)點(diǎn)的鏈
public?BinTree()
{
}
public?BinTree(Object?data)
{?//構(gòu)造有值結(jié)點(diǎn)
this.data?=?data;
left?=?right?=?null;
}
public?BinTree(Object?data,BinTree?left,BinTree?right)
{?//構(gòu)造有值結(jié)點(diǎn)
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;}
}
}
//返回樹的葉節(jié)點(diǎn)個數(shù)
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());
}
//結(jié)果返回樹的高度
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;
}
//如果對象不在樹中,結(jié)果返回-1;否則結(jié)果返回該對象在樹中所處的層次,規(guī)定根節(jié)點(diǎn)為第一層
public?int?level(Object?object)
{
int?levelInTree;
if(this?==?null)
return?-1;
if(object?==?data)
return?1;//規(guī)定根節(jié)點(diǎn)為第一層
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;
}
//將樹中的每個節(jié)點(diǎn)的孩子對換位置
public?void?reflect()
{
if(this?==?null)
return;
if(left?!=?null)
left.reflect();
if(right?!=?null)
right.reflect();
BinTree?temp?=?left;
left?=?right;
right?=?temp;
}
//?將樹中的所有節(jié)點(diǎn)移走,并輸出移走的節(jié)點(diǎn)
public?void?defoliate()
{
if(this?==?null)
return;
//若本節(jié)點(diǎn)是葉節(jié)點(diǎn)，則將其移走
if(left==nullright?==?null)
{
System.out.print(this?+?"?");
data?=?null;
return;
}
//移走左子樹若其存在
if(left!=null){
left.defoliate();
left?=?null;
}
//移走本節(jié)點(diǎn)，放在中間表示中跟移走...
String?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("前序遍歷二叉樹結(jié)果:?");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結(jié)果:?");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍歷二叉樹結(jié)果:?");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結(jié)果:?");
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("交換每個節(jié)點(diǎn)的孩子節(jié)點(diǎn)后......");
System.out.println("前序遍歷二叉樹結(jié)果:?");
tree.preOrder(tree);
System.out.println();
System.out.println("中序遍歷二叉樹結(jié)果:?");
tree.inOrder(tree);
System.out.println();
System.out.println("后序遍歷二叉樹結(jié)果:?");
tree.postOrder(tree);
System.out.println();
System.out.println("層次遍歷二叉樹結(jié)果:?");
tree.LayerOrder(tree);
System.out.println();
System.out.println("F所在的層次:?"+tree.level("F"));
System.out.println("這棵二叉樹的高度:?"+tree.height());
}
重慶分公司
重慶分公司
