二叉树叶子结点,非叶子节点以及深度的计算

article/2025/8/26 20:57:42

二叉树叶子结点的计算

//统计叶子结点的数目
int LeafNum(BiTree T) {if (!T) {return 0;} else if (!T->lchild && !T->rchild) {return 1;} else {return LeafNum(T->lchild) + LeafNum(T->rchild);}
}

二叉树非叶子节点的计算

//统计非叶子结点的数目
int NotLeafNum(BiTree T) {if (!T) {return 0;} else if (!T->lchild && !T->rchild) {return 0;} else {return NotLeafNum(T->lchild) + NotLeafNum(T->rchild) + 1;}
}

二叉树深度的计算

//计算二叉树的深度
int BiTreeDeepth(BiTree T) {if (!T) {return 0;}return BiTreeDeepth(T->lchild) > BiTreeDeepth(T->rchild) ?1 + BiTreeDeepth(T->lchild) : 1 + BiTreeDeepth(T->rchild);
}

测试

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <windows.h>
//定义一个二叉树
typedef struct Node {char data;struct Node* lchild;struct Node* rchild;
}BitNode, *BiTree;
//创建二叉树
void CreateBiTree(BiTree* T) {char ch = 0;scanf("%c", &ch);if (ch == ' ') {*T = NULL;} else {*T = (BiTree)malloc(sizeof(BitNode));if (!(*T)) {exit(-1);}(*T)->data = ch;CreateBiTree(&((*T)->lchild));CreateBiTree(&((*T)->rchild));}
}
//遍历二叉树
void PreOrderTraverse(BiTree T) {if (T) {printf("%2c", T->data);PreOrderTraverse(T->lchild);PreOrderTraverse(T->rchild);}
}
void Destroy(BiTree* T) {if (*T) {if ((*T)->lchild) {Destroy(&((*T)->lchild));}if ((*T)->rchild) {Destroy(&((*T)->rchild));}free(*T);*T = NULL;}
}
//统计叶子结点的数目
int LeafNum(BiTree T) {if (!T) {return 0;} else if (!T->lchild && !T->rchild) {return 1;} else {return LeafNum(T->lchild) + LeafNum(T->rchild);}
}
//统计非叶子结点的数目
int NotLeafNum(BiTree T) {if (!T) {return 0;} else if (!T->lchild && !T->rchild) {return 0;} else {return NotLeafNum(T->lchild) + NotLeafNum(T->rchild) + 1;}
}
//计算二叉树的深度
int BiTreeDeepth(BiTree T) {if (!T) {return 0;}return BiTreeDeepth(T->lchild) > BiTreeDeepth(T->rchild) ?1 + BiTreeDeepth(T->lchild) : 1 + BiTreeDeepth(T->rchild);
}
int main() {BiTree t1;CreateBiTree(&t1);printf("**********************\n");PreOrderTraverse(t1);printf("\n**********************\n");printf("叶子结点的数目: %d\n", LeafNum(t1));printf("************************\n");printf("非叶子结点的数目: %d\n", NotLeafNum(t1));printf("************************\n");printf("深度: %d\n", BiTreeDeepth(t1));printf("************************\n");Destroy(&t1);if (!t1) {printf("OK\n");}system("pause");return 0;
}