//// Created by KKONE on 2022/3/17.//#include #include using namespace std;struct BinaryNode { //数据源 char ch; //指针域 struct BinaryNode *lChild; struct BinaryNode *rChild;};void calculateLeafNum(struct BinaryNode *root, int *p) { if (root == NULL) { return; } //如果节点，左子树 与 右子树 同时为空 称为叶子 if (root->rChild == NULL && root->lChild == NULL) { (*p)++; } calculateLeafNum(root->lChild, p); calculateLeafNum(root->rChild, p);}//获取树的高度int getTreeHeight(struct BinaryNode *root) { if (root == NULL) { return 0; } //获取左子树的高度 int lHeight = getTreeHeight(root->lChild); //获取右子树的高度 int rHeight = getTreeHeight(root->rChild); //从左子树和右子树中最大值+1 int height = lHeight > rHeight ? lHeight + 1 : rHeight + 1; return height;}//拷贝二叉树struct BinaryNode *copyTree(struct BinaryNode *root) { if (root == NULL) { return NULL; } //先拷贝左子树 struct BinaryNode *lChild = copyTree(root->lChild); //再拷贝右子树 struct BinaryNode *rChild = copyTree(root->rChild); struct BinaryNode *newNode; newNode->ch = root->ch; newNode->lChild = root->lChild; newNode->rChild = root->rChild; return newNode;}//遍历void recursion(struct BinaryNode *root) { if (root == NULL) { return; } cout <ch <lChild); recursion(root->rChild);}//树的释放void freeTree(struct BinaryNode *root) { if (root == NULL) { return; } //先释放左子树 freeTree(root->lChild); //再释放右子树 freeTree(root->rChild); //释放根 cout <ch << " "; free(root);}//创建一个实体类void test() { struct BinaryNode nodeA = {'A', NULL, NULL}; struct BinaryNode nodeB = {'B', NULL, NULL}; struct BinaryNode nodeC = {'C', NULL, NULL}; struct BinaryNode nodeD = {'D', NULL, NULL}; struct BinaryNode nodeE = {'E', NULL, NULL}; struct BinaryNode nodeF = {'F', NULL, NULL}; struct BinaryNode nodeG = {'G', NULL, NULL}; struct BinaryNode nodeH = {'H', NULL, NULL}; //建立tree nodeA.lChild = &nodeB; nodeA.rChild = &nodeF; nodeB.lChild = &nodeC; nodeC.lChild = &nodeD; nodeC.rChild = &nodeE; nodeF.rChild = &nodeG; nodeG.lChild = &nodeH; //1、求二叉树 叶子的数量 int num = 0; calculateLeafNum(&nodeA, &num); cout << "叶子的数量为： " << num << endl; //2、求树的高度 int height = getTreeHeight(&nodeA); cout << "树的高度为： " << height << endl; //3、拷贝二叉树 struct BinaryNode *newTree = copyTree(&nodeA); //递归遍历 recursion(newTree); cout << endl; //释放二叉树 freeTree(newTree);}int main() { test(); return 0;}
