《数据结构》--二叉树【下】

🎋二叉树的基本操作

一、树的节点个数

1.所有节点个数

size_t getAllNodesNumber(Node* node) {
    size_t cur=0;
	if (!node) return 0;
    cur=1;

	size_t left =  getAllNodesNumber(node->lchild);
	size_t right = getAllNodesNumber(node->rchild);
			
	return left + right + cur;//左子树＋右子树＋根
}

2.叶子节点个数

叶子节点是度为0的节点。也就是没有孩子节点。

size_t getLeafNodesNumber(Node* node) {
	size_t cur = 0;
	if (!node)return 0;
	if (!node->lchild && !node->rchild)cur=1;

	size_t left = getAllNodesNumber(node->lchild);
	size_t right = getAllNodesNumber(node->rchild)；

	return cur + left + right;
}

3.分支节点个数

分支节点是度不为0的节点。也就是有孩子节点存在

size_t getBranchNodesNumber(Node* node) {
	size_t cur = 0;
	if (!node)return 0;
	if (node->lchild || node->rchild)cur = 1;

	size_t left = getAllNodesNumber(node->lchild);
	size_t right = getAllNodesNumber(node->rchild);

	return cur + left + right;
}

4.满度节点个数

二叉树满度也就是节点的度为2。也就是左右孩子都存在。

size_t getFullNodesNumber(Node* node) {
	size_t cur = 0;
	if (!node)return 0;
	if (node->lchild && node->rchild)cur = 1;

	size_t left = getAllNodesNumber(node->lchild);
	size_t right = getAllNodesNumber(node->rchild);

	return cur + left + right;
}

二、遍历时显示层号

在节点结构中加入层号属性。结果容器由vector<int>：res改为multimap<int,int>：m

struct TreeNode {
    int id;
	int val;
	TreeNode* lchild, * rchild;

	TreeNode():id(0),val(0),lchild(nullptr),rchild(nullptr){}
	TreeNode(const int& _val):id(0),val(_val),lchild(nullptr),rchild(nullptr){}	
};

使用层序遍历：

void Tree::levelTraverse() {
	m = {};//遍历前将容器清空
	queue<Node*> que;
	Node* cur = root;
    cur->id=1;//根节点为第一层
	que.push(cur);
	while (!que.empty()) {
		Node* front = que.front();
		que.pop();
		m.insert( {front->id,front->val} );
		if (front->lchild){
            front->lchild->id = front->id+1;//入队前，序号为父节点层号加1,
            que.push(front->lchild);
        }
		if (front->rchild){
            front->rchild->id = front->id+1;//入队前，序号为父节点层号加1,
            que.push(front->rchild);
        }
	}
}

 输出时，输出m.first和m.second即可将层号和节点值同时打印出来

三、输出第 i 层节点

在 二 的基础上，输出时，如果m.first == i,输出。

或者将代码改为：（插入时直接判断）

void Tree::levelTraverse(int i) {
	m = {};//遍历前将容器清空
	queue<Node*> que;
	Node* cur = root;
    cur->id=1;//根节点为第一层
	que.push(cur);
	while (!que.empty()) {
		Node* front = que.front();
		que.pop();
		if(front->id == i)m.insert( {i,front->val} );
		if (front->lchild){
            front->lchild->id = front->id+1;//入队前，序号为父节点层号加1,
            que.push(front->lchild);
        }
		if (front->rchild){
            front->rchild->id = front->id+1;//入队前，序号为父节点层号加1,
            que.push(front->rchild);
        }
	}
}

四、获取树的高度(深度)

最简单的方法就是在上面的基础上，输出m的最后一个元素的first属性值。

int getHeight(){
    return m.rbegin()->fisrt;
}

🎄二叉树的Leetcode习题练习

100. 相同的树 - 力扣（LeetCode）

101. 对称二叉树 - 力扣（LeetCode）

226. 翻转二叉树 - 力扣（LeetCode）

LCR 174. 寻找二叉搜索树中的目标节点 - 力扣（LeetCode）

114. 二叉树展开为链表 - 力扣（LeetCode）