本文主要是介绍5.2.数据结构-c/c++二叉树详解(下篇)(算法面试题),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
本章所有代码请见:5.3.数据结构-c/c++二叉树代码-CSDN博客
上篇:5.数据结构-c/c++二叉树详解(上篇)(遍历方法,完全二叉树)-CSDN博客
目录
1 求二叉树 第k层的节点
2 查找一个节点是否在二叉树中
3 求二叉树节点的个数
4 求二叉树叶子节点的个数
5 求树的深度
6 判断一棵树是否为完全二叉树
1 求二叉树 第k层的节点
思路:我们要求第k层结点个数,需要传入参数k。利用递归思想,我们从上到下没下一层,让k--,当k=1的时候到达第k层。
然后我们让每一个结果返回1即可
如下图,计算第三层结点的递归图
函数返回值的返回图
这样就能够准确得出k层的节点数
代码
//求二叉树第k层结点的个数
int TreeKSize(BTNode* root, int k)
{if (root == nullptr)return 0;if (k == 1)return 1;return TreeKSize(root->left, k - 1) + TreeKSize(root->right, k - 1);
}
2 查找一个节点是否在二叉树中
只需使用遍历方法遍历一遍同时查找即可,遍历方法详见二叉树遍历
//查找某个结点是否在二叉树中
BTNode* TreeFind(BTNode* root, BTDataType x)
{if (root == nullptr)return nullptr;if (root->data == x)return root;BTNode* node1 = TreeFind(root->left, x);if (node1 != nullptr)return node1;BTNode* node2 = TreeFind(root->right, x);if (node2 != nullptr)return node2;
}
3 求二叉树节点的个数
有两种方法
1.遍历
//遍历
void TreeSize1(BTNode* root, int* psize)
{if (root == nullptr)return;else(*psize)++;TreeSize1(root->left, psize);TreeSize1(root->right, psize);
}
2.分治
分治的思想类似于第1题,求k个节点个数。
第一题让k层节点都返回1,最后得到答案
而这里让每一个节点都返回1,最后就能返回节点的个数
//分治
int TreeSize2(BTNode* root)
{if (root == nullptr)return 0;elsereturn 1 + TreeSize2(root->left) + TreeSize2(root->right);
}
4 求二叉树叶子节点的个数
与第一题类似,这里只要保证返回的条件是叶子节点(左右孩子都为空的节点)
//求叶子节点个数
int TreeLeafSize(BTNode* root)
{if (root == nullptr)return 0;//保证遇到叶子节点的时候返回1if (root->left == nullptr && root->right == nullptr)return 1;//分治且其他所有节点都不返回值return TreeLeafSize(root->left) + TreeLeafSize(root->right);
}
5 求树的深度
求一棵树的深度,只要找到最深一层的结点即可
如下图,红色表示深一层结点向上返回,黑色表示其他节点返回
每一次返回的时候,返回较大的一个值即可
//求树的深度
int TreeDepth(BTNode* root)
{if (root == nullptr)return 0;int leftdepth = TreeDepth(root->left);int rightdepth = TreeDepth(root->right);if (leftdepth > rightdepth)return leftdepth + 1;elsereturn rightdepth + 1;
}
6 判断一棵树是否为完全二叉树
要判断一棵树是否为完全二叉树,只要判断树最后一层结点是否只集中在左侧且其他层结点都是满的。
思路:
我们依次将所有结点放入一个队列中(如果遇到空结点也放入队列中),遇到空结点的时候退出,再判断队列中还有无结点,如果有不为空的结点,则说明该二叉树不是完全二叉树。
例图:
代码
//判断一棵树是否为完全二叉树
bool TreeComplete(BTNode* root)
{queue<BTNode*> q;//空树是完全二叉树if (!root) return true;q.push(root);while (!q.empty()){BTNode* front = q.front();q.pop();if (front == nullptr)break;q.push(front->left);q.push(front->right);}//判断while (!q.empty()){BTNode* front = q.front();q.pop();if (front != nullptr)return false;}return true;
}
7 简单测试
测试代码
int main()
{BTNode* A = CreatNode('A');BTNode* B = CreatNode('B');BTNode* C = CreatNode('C');BTNode* D = CreatNode('D');BTNode* E = CreatNode('E');BTNode* F = CreatNode('F');BTNode* G = CreatNode('G');A->left = B;A->right = C;B->left = D;B->right = E;//C->left = F;C->right = G;int sizeA = 0;TreeSize1(A, &sizeA);cout << "TreeSize1:" << sizeA << endl;cout << "TreeSize2:" << TreeSize2(A) << endl;cout << "TreeLeafSize:" << TreeLeafSize(A) << endl;cout << "TreeDepth:" << TreeDepth(A) << endl;cout << "k=3 TreeKsize:" << TreeKSize(A, 3) << endl;if (TreeComplete(A))cout << "是完全二叉树" << endl;elsecout << "不是完全二叉树" << endl;return 0;
}
测试结果
注释掉F结点
这篇关于5.2.数据结构-c/c++二叉树详解(下篇)(算法面试题)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!