打印二叉树的左边界_打印二叉树的边界和

拼搏现实的明天。 2023-03-05 13:27 177阅读 0赞

打印二叉树的左边界

**Problem statement:** Given a binary tree, print the boundary sum of the tree.

**问题陈述：**给定二叉树，打印树的边界和。

**Solution:**

**解：**

First of all we need to understand **what the boundary sum of a binary tree is**? It's simply the cumulative sum of all boundary nodes surrounding the tree. For the following example:

首先，我们需要了解**二叉树的边界和是**什么？ 它只是树周围所有边界节点的累积和。 对于以下示例：

![print boundry sum of a binary tree][]

The boundary nodes are: **2, 7, 2, 5, 11, 4, 9, and 5** (from left to right direction)

边界节点为： **2、7、2、5、11、4、9和5** (从左到右方向)

So there are four types of node considered to be boundary node:

因此，有四种类型的节点被视为边界节点：

1.  Root node
    
    根节点
2.  All the leaf nodes
    
    所有叶节点
3.  All the nodes at the leftmost side (there will be a duplicate since the last leftmost node is itself a leaf node, discard the duplicate)
    
    最左边的所有节点(由于最后一个最左边的节点本身是叶节点，因此将有重复节点，请丢弃重复节点)
4.  All the nodes at the rightmost side ( there will be a duplicate since the last rightmost node is itself a leaf node, discard the duplicate)
    
    最右边的所有节点(由于最后一个最右边的节点本身是叶节点，因此将存在重复项，请丢弃重复项)

Thus, **the boundary sum is: 45**

因此， **边界和为：45**

**Algorithm:**

**算法：**

1.  Set **sum=0**
    
    设置**总和= 0**
2.  Add **root->data** to **sum**; (type-1 boundary node)
    
    将**root-> data**添加到**sum** ; (类型1边界节点)
3.  **Find all the leaf nodes** & add their values respectively. (type-2 boundary node)
    
    **查找所有叶节点**并分别添加其值。 (类型2边界节点)
    
    For this portion we do a level-order traversal & keep checking whether the traversed node has both its left & right point NULL or not.
    
    对于此部分，我们进行一个级别顺序遍历，并继续检查遍历的节点是否同时具有其左和右点NULL。
    
    If the traversed node has both its pointer NULL then it’s a leaf node & of course add to sum cumulatively.
    
    如果遍历的节点的指针都为NULL，则它是叶节点，当然也要累加总和。
4.  **Find the leftmost nodes** (without leaf node) & add their respective values. (type-3 boundary node)
    
    **找到最左边的节点** (没有叶节点)并添加它们各自的值。 (类型3边界节点)
    
    Set temp to root->left
    
    将温度设置为root-> left
5.      while(!(temp->right==NULL&&temp->left==NULL)){//avoiding leaf node
            sum+=temp->data; //add temp->data
            //always tend to move left side 
            //first for left most nodes
            if(temp->left) 
                temp=temp->left;
            else
                temp=temp->right;
        }
6.  **Find the rightmost nodes** (without leaf node) & add their respective values. (type-4 boundary node)
    
    **找到最右边的节点** (没有叶节点)并添加它们各自的值。 (类型4边界节点)
    
    Set temp to root->right
    
    将temp设置为root-> right
7.      while(!(temp->right==NULL&& temp->left==NULL)){//avoiding leaf node
            sum+=temp->data;//add temp->data
            //always tend to move right side 
            //first for right most nodes
            if(temp->right) 
                temp=temp->right;
            else
                temp=temp->left;
        }

## C ++程序打印二叉树的边界和 **(**C++ program to print Boundary Sum of a Binary Tree**)** ##

#include <bits/stdc++.h>
    using namespace std;
    
    // tree node is defined
    class tree{
        
    	public:
    		int data;
    		tree *left;
    		tree *right;
    };
    
    
    int findBoundarySum(tree* root){
         //finding boundary sum
    if(root==NULL) //base case
    	return 0;
    int sum=0; //(step1)
    sum+=root->data; //add root value (step2)
    
    //find the leaf nodes & add(step3)
    tree* temp=root, *store; //copy root to temp
    queue<tree*> q; //creat a queue to store tree* variables (pointer to nodes)
    
    //doing level order traversal
    q.push(temp);
    while(!q.empty()){
        
    	store=q.front();
    	q.pop();
    	// if left & right both pointers are NULL, it's a leaf node
    	if(store->left==NULL && store->right==NULL) 
    		sum+=store->data; // add leaf node value
    	if(store->left)
    		q.push(store->left);
    	if(store->right)
    		q.push(store->right);
    }
    
    /end of step3
    
    
    //adding the leftmost nodes excluding leaf node(step4)///
    temp=root->left;
    while(!(temp->right==NULL && temp->left==NULL)){
        //avoiding leaf node
    	sum+=temp->data;
    	if(temp->left)
    		temp=temp->left;
    	else
    		temp=temp->right;
    }
    
    end of step4//
    
    //adding the rightmost nodes excluding leaf node(steps)///
    temp=root->right;
    while(!(temp->right==NULL && temp->left==NULL)){
        //avoiding leaf node
    	sum+=temp->data;
    	if(temp->right)
    		temp=temp->right;
    	else
    		temp=temp->left;
    }
    end of step5//
    //boundary sum is now calculated, return it
    return sum;
    }
    
    // creating new node
    tree* newnode(int data)  
    {
         
    	tree* node = (tree*)malloc(sizeof(tree)); 
    	node->data = data; 
    	node->left = NULL; 
    	node->right = NULL; 
    	return(node); 
    } 
    
    int main() 
    {
         
    	//**same tree is builted as shown in example**
    	cout<<"Tree is built like the example aforesaid"<<endl;
    	//building the tree like as in the example
    	tree *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<<"finding boundary sum......"<<endl; 
    	cout<<"boundary sum is "<<findBoundarySum(root)<<endl;
    
    	return 0; 
    }

**Output**

**输出量**

Tree is built like the example aforesaid
    finding boundary sum......
    boundary sum is 45

> 翻译自: [https://www.includehelp.com/icp/print-boundary-sum-of-a-binary-tree.aspx][https_www.includehelp.com_icp_print-boundary-sum-of-a-binary-tree.aspx]

打印二叉树的左边界

[print boundry sum of a binary tree]: /images/20230208/a9d09af7c09549adbf72351e47a0e1c8.png
[https_www.includehelp.com_icp_print-boundary-sum-of-a-binary-tree.aspx]: https://www.includehelp.com/icp/print-boundary-sum-of-a-binary-tree.aspx