二叉樹中相關遞歸求解(c,c++數據結構，演算法設計與分析)

//二叉樹的定義

typedef struct BiTNode{BElemType data;struct BiTNode *lchild, *rchild;}BiTNode, *BiTree;

//二叉樹相關操作中的部分相關遞歸操作

//按先序遍歷建立二叉鏈表（遞歸）

status CreateBiTree(BiTree &T){TElemtype e,flag=0;//特殊標誌「0」表示空樹e=getchar();if(e==flag) T=NULL;else{T=(BiTree)malloc(sizeof(BiTNode));if(!T)exit(OVERFLOW);T->data=e;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}return OK;}

//輸出二叉樹，用嵌套括弧表示（遞歸）

void outputBiTree(BiTree T){if(T){putchar(T->data);if(T->lchild||T->rchild){putchar(();outputBiTree(T->lchild);if(T->rchild)putchar(,);outputBiTree(T->rchild);putchar());}}}

//求二叉樹的節點數（遞歸）

int Node(BiTree T){if(!T)return 0;return 1+Node(T->lchild)+Node(T->rchild);}

//求二叉樹的葉子節點（遞歸）

int leaves(BiTree T){if(!T) return 0;if(!T->lchild && !T->rchild) return 1;return leaves(T->lchild )+leaves(T->rchild );}

//求二叉樹的深度(遞歸)

int Depth(BiTree T){if(!T)return 0;if(Depth(T->lchild)>Depth(T->rchild))return (Depth(T->lchild)+1);return (Depth(T->rchild)+1);}

推薦閱讀：