二叉树右视图

Problem statement:

问题陈述：

Given a Binary Tree, print Right view of it. Right view of a Binary Tree is set of nodes visible when tree is visited from Right side.

给定一个二叉树，打印它的右视图 。 二叉树的右视图是从右侧访问树时可见的节点集。

Example:

例：

For the above tree:        Output: Right view    2, 5, 9, 4

Solution

解

Right view of a binary tree

二叉树的右视图

Right view of a binary tree means the nodes which are visible when tree is view from right direction only.

二叉树的右视图表示仅从右方向查看树时可见的节点。

The above problem can be solved using . For every level traversed, print only the rightmost node.

可以使用来解决上述问题。 对于遍历的每个级别，仅打印最右边的节点。

Algorithm

算法

Pre-requisite:

先决条件：

A Queue, input binary tree

队列，输入二叉树

FUNCTION rightView(root)1.  Declare a queue q to store tree nodes.    EnQueue (q, root);    EnQueue (q, NULL);    NULL is EnQueued after end of each level. Root determines level-0      While (q is not empty)        temp=DeQueue(q)        IF (temp==NULL)            IF (q is not empty)                EnQueue (q, NULL);				            END IF            Printstore  //it actually contains the right most node                         //of the last level traversed				        ELSE			            store=temp->data //update store to current temp->data every time         END IF                IF (temp->left is not NULL)            EnQueue (q, temp->left);        IF (temp->right is not NULL)            EnQueue (q, temp->right);        END IF-ELSE    END WHILEEND FUNCTION

C++ implementation:

C ++实现：

#include 
    
     using namespace std;// tree node is definedclass TreeNode{
       	public:	int data;	TreeNode *left;	TreeNode *right;};// creating new node for treeTreeNode* newnode(int data)  {
    	TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode)); 	node->data = data; 	node->left = NULL; 	node->right = NULL; 	return(node); } void rightView(TreeNode *root){
   	queue
     
       q;	TreeNode* temp;	int store; //to store the nodes		q.push(root);	q.push(NULL);	while(!q.empty()){
   		temp=q.front();		q.pop();		if(temp==NULL){
   			if(!q.empty()){
   				q.push(NULL);			}			cout<
      
       <<" "; //printing the rightmost node		}		else{
   			store=temp->data;			if(temp->left)				q.push(temp->left);			if(temp->right)				q.push(temp->right);		}	} }int main() {
    	//**same tree is builted as shown in example**	cout<<"same tree is built as shown in example\n";		TreeNode *root=newnode(2); 		root->left= newnode(7); 	root->right= newnode(5); 	root->right->right=newnode(9);	root->right->right->left=newnode(4);	root->left->left=newnode(2); 	root->left->right=newnode(6);	root->left->right->left=newnode(5);	root->left->right->right=newnode(11);	cout<<"Right view of the tree is:\n";	rightView(root);	return 0; }
      
     
    

Output

输出量

same tree is built as shown in exampleRight view of the tree is:2 5 9 4

Example with explanation

带说明的例子

For our example tree...Root=2;EnQueue(root)Queue status: 2EnQueue(NULL)Queue status: 2, NULL----------------------------------------------------1st iterationQueue not emptyQueue front is 2Pop 2Store=2Push: 2->left(7) & 2->right(5)Queue status: NULL, 7, 5K=3----------------------------------------------------2nd iterationQueue not emptyQueue front is NULLPop NULLPrint store, 2Push: NULLQueue status: 7, 5, NULL----------------------------------------------------3rd iterationQueue not emptyQueue front is 7Pop 7Store=7Push: 7->left (2) and 7->right (6) onlyQueue status: 5, NULL, 2, 6 ----------------------------------------------------4th iterationQueue not emptyQueue front is 5Pop 5Store=5Push: 5->right (9) (5->left is NULL)Queue status: NULL, 2, 6, 9 ----------------------------------------------------5th iterationQueue not emptyQueue front is NULLPop NULLPrint store, 5Push: NULLQueue status: 2, 6, 9, NULL----------------------------------------------------6th iterationQueue not emptyQueue front is 2Pop 2Store=2Push: Nothing (2->left is NULL, 2->right is NULL)Queue status: 6, 9, NULL ----------------------------------------------------7th iterationQueue not emptyQueue front is 6Pop 6Store=6Push: 6->left (5) & 6->right (11)Queue status: 9, NULL, 5, 11 ----------------------------------------------------8th iterationQueue not emptyQueue front is 9Pop 9Store=9Push: 9->left (4) (9->right is NULL)Queue status: NULL, 5, 11, 4 ----------------------------------------------------9th iterationQueue not emptyQueue front is NULLPop NULLPrint store, 9Push: NULLQueue status: 5, 11, 4, NULL----------------------------------------------------10th iterationQueue not emptyQueue front is 5Pop 5Store=5Push: Nothing (9->left NULL, 9->right is NULL)Queue status: 11, 4, NULL ----------------------------------------------------11th iterationQueue not emptyQueue front is 11Pop 11Store=11Push: Nothing (11->left NULL, 11->right is NULL)Queue status: 4, NULL ----------------------------------------------------12th iterationQueue not emptyQueue front is 4Pop 4Store=4Push: Nothing (11->left NULL, 11->right is NULL)Queue status: NULL ----------------------------------------------------13th iterationQueue not emptyQueue front is NULLPop NULLPrint Store, 4Now Queue is emptyPush: Nothing (11->left NULL, 11->right is NULL)Queue status: empty QueueExit from programHence right view is:2 5 9 4

翻译自:

二叉树右视图