二叉樹的直徑怎麼算?
求助，想知道求一顆二叉樹所有直徑及路徑長度怎麼做，中根和後根次序
/*先序遞歸遍歷*/ void DLR(BTNode *bt) { if(bt) { printf("%c",bt->data); DLR(bt->lchild); DLR(bt->rchild); } } /*中序遞歸遍歷*/ void LDR(BTNode *bt) { if(bt) { LDR(bt->lchild); printf("%c",bt->data); LDR(bt->rchild); } } /*後序遞歸遍歷*/ void LRD(BTNode *bt) { if(bt) { LRD(bt->lchild); LRD(bt->rchild); printf("%c",bt->data); } }
數據結構（求一棵二叉樹的所有直徑和路徑長度） 可不可以幫忙代寫一下啊·····
f（a）{
if（a）{
f（a）;
}
}
求二叉樹一條所有的data之和最大的路徑
用先序遍歷可以完成該操作。維護兩條路徑，一條是當前遍歷路徑，一條是當前最大值的路徑
初略寫個算法，兩個路徑的增刪就不寫了，可以是個指針數組或鏈表。
GetMaxPath（struct NODE *root, long curTotal, long *MaxTotal）
{
if (root != NULL)
{
//將本節點加入當前遍歷路徑
if ((curTotal + root->data) > MaxTotal)
{
//將當前遍歷路徑覆蓋當前最大值路徑
}
GetMaxPath(root->left , curTotal + root->data, MaxTotal);
GetMaxPath(root->right, curTotal + root->data, MaxTotal);
//將本節點從當前遍歷路徑中刪除
}
}
最終獲取的最大值路徑即為最終結果。
編寫c++算法求任意二叉樹中一條最長的路徑，並輸出此路徑上各結點的值
#include
#define MaxSize 1000
typedef struct BiTNode {
int data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
void LongestPath(BiTree bt)//求二叉樹中的第一條最長路徑長度,並輸出最長路徑上的節點
{
BiTree p = bt, l[MaxSize], s[MaxSize]; //l, s是棧，元素是二叉樹結點指針，l中保留當前最長路徑中的結點
int i,top = 0, tag[MaxSize], longest = 0;
while (p || top >0)
{
while (p)
{
s[++top] = p;
tag[top] = 0;
p = p->lchild;
} //沿左分枝向下
if (tag[top] == 1) //當前結點的右分枝已遍歷
{
if (!s[top]->lchild && !s[top]->rchild) //只有到葉子結點時，才查看路徑長度
if (top>longest)
{
for (i = 1; i <= top; i++)
l[i] = s[i];
longest = top;
top--;
}//保留當前最長路徑到l棧，記住最高棧頂指針，退棧
}
else if (top>0)
{
tag[top] = 1;
p = s[top]->rchild;
} //沿右子分枝向下
}//while(p!=null||top>0)
int k = 0;
for (k = 0; k < longest; k++)
{
printf("%d ", l[k]->data);
}
}//結束LongestPath
以二叉鏈表為存儲結構,寫出求二叉樹高度和寬度的算法
原題：
以二叉鏈表為存儲結構，分別寫出求二叉樹高度及寬度的算法。所謂寬度是指在二叉樹的各層上，具有結點數最多的那一層上的結點總數。
標準答案：
①求償的高度
思想：對非空二叉樹，其深度等於左子樹的最大深度加1。
Int Depth(BinTree *T)
{
int dep1,dep2;
if(T==Null) return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}
②求樹的寬度
思想：按層遍歷二叉樹，採用一個隊列q，讓根結點入隊列，最後出隊列，若有左右子樹，則左右子樹根結點入隊列，如此反覆，直到隊列為空。
int Width(BinTree *T)
{
int
front=-1,rear=-1;/*
隊列初始化*／
int flag=0,count=0,p;
/* p用於指向樹中層的最右邊的結點，標誌flag記錄層中結點數的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 當前層已遍歷完畢*/
{
if(flag
flag=count;
count=0;
p=rear; /* p指向下一層最右邊的結點*/
}
}
/* endwhile*/
return(flag);
}