二叉树的右视图

17 Mar 2025 | 5 分钟阅读

树是一种常见的非线性数据结构。与数组、栈、队列和链表等线性数据结构不同，树展现出一种分层结构。树的排序信息无关紧要。树由两个指针和节点组成。这两个指针代表父节点的左孩子和右孩子。让我们彻底理解树中使用的术语。

树中没有父节点的最高节点被视为树的根。每棵树都有一个根节点。
父节点：一个节点的父节点是该节点在节点树中的前一个节点。
子节点：一个节点的直接后继节点被称为该节点的子节点。
兄弟节点：同一父节点的子节点互为兄弟节点。
边：边作为父节点和子节点之间的连接节点。
叶子：没有子节点的节点被称为叶子节点。它是树的最后一个节点。一棵树可以有多个叶子节点。
一个节点的子树是把该特定节点视为根节点的树。
深度：一个节点的深度是它与根节点之间的距离。
高度：一个节点的高度是它与子树中最深节点之间的距离。
任何节点的最大高度被称为树的高度。这与根节点的高度相同。
层：在树中，层是与特定节点对应的父节点的数量。
节点度：一个节点的度由它拥有的子节点数量决定。
二叉树有 (N+1) 个 NULL 节点，其中 N 是树中节点的总数。

为什么要使用基于树的数据结构？

您可能希望存储自然形成层次结构的信息，这是使用树的原因之一。例如，计算机的文件系统。
树提供了合理的访问/搜索速度（通过一些排序，如 BST）（比链表快，比数组慢）。
树提供了有限的插入和删除速度（比数组快，比无序链表慢）。
因为指针用于连接节点，所以树，像链表一样，没有最大节点数。

树数据结构的主要用途包括：

分层数据操作。
使信息可搜索（参见树遍历）。
操作数据排序列表。
用于创建视觉效果的数字图片。
路由协议
多阶段决策过程类型（参见商业象棋）。

什么是二叉树？

二叉树是一种由节点组成的数据结构——这些节点也称为左节点和右节点——每个节点最多有两个子节点。树从根节点开始。

二叉树表示

树中的每个节点都包含以下信息：

指向左子节点的指针
指向右子节点的指针

在 C 语言中，我们可以使用结构体来表示树节点。我们可以利用其他语言的面向对象特性中的类。下面是一个包含整数数据的树节点的示例。

// Structure of each node of the tree
struct node {
	int data;
	struct node* left;
	struct node* right;
};

当从右侧查看二叉树时可见的节点集合称为右视图。

示例

Input:
          1
       /     \
     2        3
   /   \       /  \
  4     5   6    7
                 \
                   8

输出

Right view of the tree is 1 3 7 8

使用递归实现二叉树的右视图

其思路是利用递归，同时跟踪最高层级。此外，遍历树时应先访问右子树，再访问左子树。

上述策略的应用如下所示：

// C program to print right view of Binary Tree
#include <stdio.h>
#include <stdlib.h>

struct Node {
	int data;
	struct Node *left, *right;
};

// A utility function to create a new Binary Tree Node
struct Node* newNode(int item)
{
	struct Node* temp
		= (struct Node*)malloc(sizeof(struct Node));
	temp->data = item;
	temp->left = temp->right = NULL;
	return temp;
}

// Recursive function to print right view of a binary tree.
void rightViewUtil(struct Node* root, int level,
				int* max_level)
{
	// Base Case
	if (root == NULL)
		return;

	// If this is the last Node of its level
	if (*max_level < level) {
		printf("%d\t", root->data);
		*max_level = level;
	}

	// Recur for right subtree first, then left subtree
	rightViewUtil(root->right, level + 1, max_level);
	rightViewUtil(root->left, level + 1, max_level);
}

// A wrapper over rightViewUtil()
void rightView(struct Node* root)
{
	int max_level = 0;
	rightViewUtil(root, 1, &max_level);
}

// Driver Program to test above functions
int main()
{
	struct Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	root->right->left->right = newNode(8);
	rightView(root);
	return 0;
}

输出

1 3 7 8
?????..
Process executed in 1.11 seconds
Press any key to continue.

说明

要解决此问题，请遵循下面列出的说明

应使用后序遍历首先检索最右侧的节点。
维护一个名为 max_level 的变量，它将保存数据，直到打印出右视图为止。
以后序方式遍历树时，如果当前层级高于 max_level，则打印当前节点并将 max_level 增加到当前层级。

使用层序遍历实现二叉树的右视图

// C program to print right view of
// Binary Tree using level order traversal
#include <stdio.h>
#include <stdlib.h>
struct Node {
	int data;
	struct Node *left, *right;
};
// A utility function to create a new Binary Tree Node
struct Node* newNode(int item)
{
	struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
	temp->data = item;
	temp->left = temp->right = NULL;
	return temp;
}
// function to print Right view of
// binary tree
void printRightView(Node* root)
{
	if (root == NULL)
		return;
	queue<Node*> q;
	q.push(root);

	while (!q.empty()) {
		// get number of nodes for each level
		int n = q.size();

		// traverse all the nodes of the current level
		while (n--) {

			Node* x = q.front();
			q.pop();

			// print the last node of each level
			if (n == 0) {
				printf("%d\t", x->data);
			}
			// if left child is not null push it into the
			// queue
			if (x->left)
				q.push(x->left);
			// if right child is not null push it into the
			// queue
			if (x->right)
				q.push(x->right);
		}
	}
}

// Driver code
int main()
{
	// Let's construct the tree as
	// shown in example

	Node* root = newNode(1);
	root->left = newNode(2);
	root->right = newNode(3);
	root->left->left = newNode(4);
	root->left->right = newNode(5);
	root->right->left = newNode(6);
	root->right->right = newNode(7);
	root->right->left->right = newNode(8);
	printRightView(root);
}

输出

 1 3 7 8 
????
Process executed in 1.22 seconds
Press any key to continue

说明

思路是利用层序遍历，因为每个层级的最后一个节点构成了二叉树的右视图。

要解决此问题，请遵循下面列出的说明

按层序遍历树。
打印每个层级的最后一个节点。

下一主题严格二叉树

二叉树的右视图

为什么要使用基于树的数据结构？

二叉树表示

使用递归实现二叉树的右视图

使用层序遍历实现二叉树的右视图

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

二叉树的右视图

为什么要使用基于树的数据结构？

二叉树表示

使用递归实现二叉树的右视图

使用层序遍历实现二叉树的右视图

相关帖子

C++ 程序查找最长非递减子段的长度

B 树可视化

JavaScript 中图的实现

在平衡 BST 中查找和为给定对

Floyd 的慢指针和快指针方法是如何工作的

对 0、1 和 2 的数组进行排序

不相交集数据结构

AVL 树的优点

滚入迷宫的球

如何检查二进制数是否可被 3 整除

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器