求節點演算法

① 完全二叉樹葉子節點的演算法

設：度為i的結點數為ni，由二叉樹的性質可知：
n0 = n2 + 1……………………①式
n = n0 + n1 + n2……………②式
由①式可得 n2 = n0 - 1，帶入②式得：
n0 = （n + 1 - n1）/ 2
由完全二叉樹性質可知：
如圖，當n為偶數時，n1 = 1， n0 = n / 2

將兩式合並，寫作：n0 = ⌊（n+1）/2⌋（向下取整符號不能丟）

(1)求節點演算法擴展閱讀：

完全二叉樹的特點:

1.葉子結點只可能在層次最大的兩層上出現。

2.對任一結點，若其由分支下的子孫的最大層次為l，則其左分支下的子孫的最大層次必為l或l+1。

完全二叉樹的性質：

1.具有n個結點的完全二叉樹的深度為⌊log₂n⌋+1。

2.如果對一棵有n個結點的完全二叉樹的結點按層序編號，則對任一結點i，有：

（1）如果i=1，則結點i是二叉樹的根節點，無雙親；如果i>1，則其雙親是結點⌊i/2⌋。

（2）如果2i>n，則結點i無左孩子；否則其左孩子是結點2i。

（3）如果2i+1>n，則結點i無右孩子；否則其右孩子是結點2i+1。

② 關節點的求解演算法

利用深度優先搜索便可以求的圖的關節點，本由此可判別圖是否重連通。
從任一點出發深度優先遍歷得到優先生成樹，對於樹中任一頂點V而言，其孩子節點為鄰接點。由深度優先生成樹可得出兩類關節點的特性：
（1）若生成樹的根有兩棵或兩棵以上的子樹，則此根頂點必為關節點。因為圖中不存在連接不同子樹頂點的邊，若刪除此節點，則樹便成為森林。
（2）若生成樹中某個非葉子節點V，其某棵子樹與V的祖先節點無連接，則V為關節點。因為刪去v，則其子樹和圖的其它部分被分割開來 low[v] 設對連通圖G=（V,E）進行先深搜索的先深編號為dnf[v]，產生的先深生成樹為S=（V,T），B試回退邊之集。對每個頂點v，low[v]定義如下
low[v]=Min{dfn[v],Min{low[w]|w是v的一個子女}，Min{dfn[x]|（v，x）是一條回邊}}//dfn數組記錄頂點的深度優先數
演算法： 求無向圖的雙連通分量
輸入：連通的無向圖G=( V, E )。L[v]表示關於v的鄰接表
輸出：G的所有雙連通分量，每個連通分量由一序列的邊組成。 1.計算先深編號：對圖進行先深搜索，計算每個結點v的先深編號dnf[v]，形成先深生成樹S=（V,T）。
2.計算low[v]：在先深生成樹上按後根順序進行計算每個頂點v的 low[v]， low[v]取下述三個結點中的最小者：
(1) dfn[v]；
(2) dfn[w]，凡是有回退邊（v,w）的任何結點w；
(3) low[y]，對v的任何兒子y。
3.求關節點：
(1)樹根是關節點，當且僅當它有兩個或兩個以上的兒子（第一類關節點）；
(2)非樹根結點v是關節點當且僅當v有某個兒子y，使low[y]≥dnf[v]（第二類關節點）。
求雙連通分量的演算法――同先深搜索演算法（略）

③ 完全二叉樹葉子節點的演算法

設二叉樹的葉子節點數為n0，度數為2的節點數為n2，設n1為二叉樹中度為1的節點數

因為二叉樹中所有節點的度都釣魚或者等於2，所以二叉樹節點總數n=n0+n1+n2

再看二叉樹的分支數，除了根節點外，其餘節點都有一個分支進入，設B為分支總數，則n=B+1

由於這些分支都是有度為1或者2 的節點射出的，所以B=n1+n2;於是有n=n1+2*n2+1

綜合n=n0+n1+n2和n=n1+2*n2+1兩式即可得到n0=n2+1

完全二叉樹是特殊的二叉樹，對於n0=n2+1當然成立

④ 求C語言統計一棵二叉樹節點總數的演算法（只要函數）

用遞歸啊，除了葉子節點以外，每個節點都有左子樹和右子樹，只要判斷子節點不為空就用遞歸調用函數統一子樹的節點數，例如
f（t)=f(l)+f(r)+1;
節點總數等於左子樹的節點數+右子樹的節點數+1

⑤ 求葉子節點的演算法

你的k要定義到int leaf_a(BTree root)函數外面去，定義成全局變數，每次遞歸的k是形參，每次調用都是不一樣的
我試過是對的

⑥ 節點的演算法

#include <stdio.h>
# include<stdlib.h>
#include <malloc.h>
typedef int datatype;
int p=0,d=0;

typedef struct node
{
datatype data;
struct node *lchild;
struct node *rchild;

}BINTNODE;

typedef BINTNODE *BINTREE;

void createbintree(BINTREE *t)
{
int a;
scanf("%d",&a);
if(a==0)
*t=NULL;
else
{
*t=(BINTNODE *)malloc(sizeof(BINTNODE));
(*t)->data=a;
createbintree(&(*t)->lchild);
createbintree(&(*t)->rchild);
}
}

void preorder(BINTREE T)
{
if(T)
{
printf("%d ",T->data);
d++;
preorder(T->lchild);

preorder(T->rchild);

if(((T->lchild)==NULL)&&((T->rchild)==NULL))
p++;

}

}
main()
{
BINTREE t=NULL;
printf("\nplease input nodes of BINTREE:");
createbintree(&t);
printf("the preorder is:");
preorder(t);

printf("\n葉子節點數：%d",p);

printf("\n總節點數：%d",d);
}
是這樣的嗎？

⑦ 關於樹的結點演算法，請大家幫幫忙，過程詳細點，謝謝！！！

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#define Max 20 //結點的最大個數
typedef struct node{
char data;
struct node *lchild,*rchild;
}BinTNode; //自定義二叉樹的結點類型
typedef BinTNode *BinTree; //定義二叉樹的指針
int NodeNum,leaf; //NodeNum為結點數，leaf為葉子數
//==========基於先序遍歷演算法創建二叉樹==============
//=====要求輸入先序序列，其中加入虛結點"#"以示空指針的位置==========
BinTree CreatBinTree(void)
{
BinTree T;
char ch;
if((ch=getchar())==' ')
return(NULL); //讀入#，返回空指針
else{
T=(BinTNode *)malloc(sizeof(BinTNode));//生成結點
T->data=ch;
T->lchild=CreatBinTree(); //構造左子樹
T->rchild=CreatBinTree(); //構造右子樹
return(T);
}
}
//========NLR 先序遍歷=============
void Preorder(BinTree T)
{
if(T) {
printf("%c",T->data); //訪問結點
Preorder(T->lchild); //先序遍歷左子樹
Preorder(T->rchild); //先序遍歷右子樹
}
}
//========LNR 中序遍歷===============
void Inorder(BinTree T)
{
if(T) {
Inorder(T->lchild); //中序遍歷左子樹
printf("%c",T->data); //訪問結點
Inorder(T->rchild); //中序遍歷右子樹
}
}
//==========LRN 後序遍歷============
void Postorder(BinTree T)
{
if(T) {
Postorder(T->lchild); //後序遍歷左子樹
Postorder(T->rchild); //後序遍歷右子樹
printf("%c",T->data); //訪問結點
}
}
//=====採用後序遍歷求二叉樹的深度、結點數及葉子數的遞歸演算法========
int TreeDepth(BinTree T)
{
int hl,hr,max;
if(T){
hl=TreeDepth(T->lchild); //求左深度
hr=TreeDepth(T->rchild); //求右深度
max=hl>hr? hl:hr; //取左右深度的最大值
NodeNum=NodeNum+1; //求結點數
if(hl==0&&hr==0) leaf=leaf+1; //若左右深度為0，即為葉子。
return(max+1);
}
else return(0);
}
//====利用"先進先出"（FIFO）隊列，按層次遍歷二叉樹==========
void Levelorder(BinTree T)
{
int front=0,rear=1;
BinTNode *cq[Max],*p; //定義結點的指針數組cq
cq[1]=T; //根入隊
while(front!=rear)
{
front=(front+1)%NodeNum;
p=cq[front]; //出隊
printf("%c",p->data); //出隊，輸出結點的值
if(p->lchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->lchild; //左子樹入隊
}
if(p->rchild!=NULL){
rear=(rear+1)%NodeNum;
cq[rear]=p->rchild; //右子樹入隊
}
}
}
//==========主函數=================
void main()
{
BinTree root;
int i,depth;
printf("NodeNum:%d\n",NodeNum);
printf("Creat Bin_Tree； Input preorder:"); //輸入完全二叉樹的先序序列，
// 用#代表虛結點，如ABD###CE##F##
root=CreatBinTree(); //創建二叉樹，返回根結點
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("\t5: Level Depth\n"); //先判斷節點數是否已有。不用再先選擇4，求出該樹的結點數。
printf("\t0: Exit\n");
printf("\t*******************************\n");
scanf("%d",&i); //輸入菜單序號（0-5）
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); //求樹的深度及葉子數
printf("BinTree Depth=%d BinTree Node number=%d",depth,NodeNum);
printf(" BinTree Leaf number=%d",leaf);
break;
case 5:
if(!NodeNum)
TreeDepth(root);
printf("LevePrint Bin_Tree: ");
Levelorder(root); //按層次遍歷
break;
default: exit(1);
}
printf("\n");
} while(i!=0);
}

⑧ 求一個計算循環鏈表節點數目的演算法

int number_L(linklist L)
{
int m=1;/*至少一個節點*/
linklist p=L->next;
while(&p!=&L)/*當p和L不是同一個節點*/
{
m++;
p=p->next;
}
return m;
}

若循環鏈表允許為空表，則加上
if(L==NULL) return 0;
即可

⑨ 求統計二叉樹葉子結點數的遞歸演算法

···cpp

由於不知道你的存儲方式，假設你是指針存，用孩子兄弟表示法。

（偽）代碼：

structnode{
data{
...
}val;
node*fchild,*brother;
}
voidgetnum(nodex){
if(x.fchild==nu)ans++;
else{
getnum(*x.fchild);
getnum(*x.brother);
}
}

就這樣

⑩ 寫出中序線索二叉樹求第n個節點的演算法。

在後序序列中，若結點p有右子女，則右子女是其前驅，若無右子女而有左子女，則左子女是其前驅。若結點p左右子女均無，設其中序左線索指向某祖先結點f（p是f右子樹中按中序遍歷的第一個結點），若f有左子女，則其左子女是結點p在後序下的前驅；若f無左子女，則順其前驅找雙親的雙親，一直繼續到雙親有左子女（這時左子女是p的前驅）。還有一種情況，若p是中序遍歷的第一個結點，結點p在中序和後序下均無前驅。
BiThrTree InPostPre (BiThrTree t,p)
//在中序線索二叉樹t中，求指定結點p在後序下的前驅結點q
{BiThrTree q;
if (p->rtag==0) q=p->rchild; //若p有右子女，則右子女是其後序前驅
else if (p->ltag==0) q=p->lchild; //若p無右子女而有左子女，左子女是其後序前驅。
else if(p->lchild==null) q=null;//p是中序序列第一結點，無後序前驅
else //順左線索向上找p的祖先，若存在，再找祖先的左子女
{while(p->ltag==1 && p->lchild!=null) p=p->lchild;
if(p->ltag==0) q=p->lchild; //p結點的祖先的左子女是其後序前驅
else q=null; //僅右單枝樹（p是葉子），已上到根結點，p結點無後序前驅
}
return(q); }//結束InPostPre