二叉树的边界遍历

17 Mar 2025 | 4 分钟阅读

二叉树的边界遍历包括左边界、叶子节点和右边界，不重复节点，因为节点可能包含重复的值。边界有两种类型，即左边界和右边界。左边界可以定义为从根节点到最左边节点的路径，而右边界可以定义为从根节点到最右边节点的路径。如果根节点不包含任何左子树和右子树，那么根节点本身将被视为左边界和右边界。

让我们通过一个例子来理解二叉树的边界遍历。

考虑下面的树

我们需要在上面的二叉树中执行边界遍历。首先，我们遍历上面二叉树中属于边界遍历的左侧所有节点。出现在左侧的节点是a b c d f e。出现在右侧的节点是 a k l n。我们已经遍历了左右节点，现在我们将遍历叶子节点。在上面的树中，叶子节点是 e g h j m n。有些节点在所有边界中重复出现；例如，节点 'a' 出现在左边界和右边界中，所以我们将 'a' 从右边界中移除，现在它只出现一次。有些节点也可能在叶子节点中重复出现。由于节点 'e' 出现在左边界和叶子节点中，所以我们将 'e' 从叶子节点中移除。节点 'n' 也出现在右边界和叶子节点中，所以我们将节点 'n' 从叶子节点中移除。因此，最终的边界遍历结果是

a b c d f e k l n g h j

假设我们要以逆时针方向执行二叉树的边界遍历，那么问题可以分解为四个部分：

首先打印根节点。
遍历除叶子节点之外的最左边的节点。
叶子节点
遍历除叶子节点之外的最右边的节点。

下面是查找二叉树最左边节点的源代码

void left_boundary_tree(node *p)
{
    if(p)
   {
         if(p->left)
         {
           print(p->data);
           left_boundary_tree(p->left);
        }
   }
else if(p->right)
{
    print(p->data);
   left_boundary_tree(p->right);
}
}
In the above, the pointer p which is passed to the function is the pointer that points to the root node of the binary tree. If the current node has a left node then the condition p->left would be true. It will print the current node data and the pointer p moves to the left of the current node data. The function left_boundary_tree(p->left); calls itself till wee find the left node.

下面是查找二叉树最右边节点的源代码

void right_boundary_tree(node *p)
{
    if(p)
   {
         if(p->right)
         {
           print(p->data);
           right_boundary_tree(p->right);
        }
   }
else if(p->left)
{
    print(p->data);
   right_boundary_tree(p->left);
}
}

打印叶子节点的源代码。

void print_leaf_node(node *p)
{
   if(p)
  {
       print_leaf(p->left);
      if((!p->left) && !(p->right))
      {
           print(p->data);
      }
  print_leaf(p->right);
  }
}

以下是实现二叉树边界遍历的 C 语言实现

/* C program for boundary traversal 
of a binary tree */
  
#include <stdio.h>
#include <stdlib.h>
  
/* Creation of user-defined structure named as node that has data, pointer to left child
and a pointer to right child */

struct node {
    int data;
    struct node *left, *right;
};
  
// A function that prints all the leaf nodes of a binary tree
void print_Leaf(struct node* root)
{
    if (root == NULL)
        return;
  
    print_Leaf(root->left);
  
    // Condition would be true if the node does not have any left and right child.
    if (!(root->left) && !(root->right))
        printf("%d ", root->data);
  
    print_Leaf(root->right);
}
  
// A function that prints all the left boundary nodes, except a leaf node.
// Print the nodes in from the top to the bottom manner
void print_left_boundary(struct node* root)
{
    if (root == NULL)
        return;
  
    if (root->left) {
  
        // print the root data before calling the function itself in a top-down manner.
        
        printf("%d ", root->data);
        print_left_boundary(root->left);
    }
    else if (root->right) {
        printf("%d ", root->data);
        print_left_boundary(root->right);
    }
    
// if the node is a leaf node then we do not need to do anything otherwise it will create duplicacy..
}

// A function that prints all the left boundary nodes, except a leaf node.
// Print the nodes in from the bottom to the top manner

void print_right_boundary(struct node* root)
{
    if (root == NULL)
        return;
  
    if (root->right) {
        // First, we will call the right subtree in order to maintain the bottom to top approach.
        print_right_boundary(root->right);
        printf("%d ", root->data);
    }
    else if (root->left) {
        print_right_boundary(root->left);
        printf("%d ", root->data);
    }
// if the node is a leaf node then we do not need to do anything otherwise it will create duplicacy..

}
  
// A function to do boundary traversal of a given binary tree
void print_boundary_nodes(struct node* root)
{
    if (root == NULL)
        return;
  
    printf("%d ", root->data);
  
    // Print the left boundary in top-down manner.
    print_left_boundary(root->left);
  
    // Print all leaf nodes
    print_Leaf(root->left);
    print_Leaf(root->right);
  
    // Print the right boundary in bottom-up manner
    print_right_boundary(root->right);
}
  
// A function used to create a node
struct node* new_Node(int data)
{
    struct node* temp = (struct node*)malloc(sizeof(struct node));
  
    temp->data = data;
    temp->left = temp->right = NULL;
  
    return temp;
}
  
// main() function from where the execution gets started.
int main()
{
    // first we construct a tree by calling the function new_Node()
    struct node* root = new_Node(30);
    root->left = new_Node(18);
    root->left->left = new_Node(14);
    root->left->right = new_Node(21);
    root->left->right->left = new_Node(9);
    root->left->right->right = new_Node(24);
    root->right = new_Node(22);
    root->right->right = new_Node(28);
  
    print_boundary_nodes(root);
  
    return 0;
}

输出

下一个主题二叉树对角线遍历

二叉树的边界遍历

联系信息

关注我们

教程

面试题

在线编译器

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 选择题

其他

二叉树的边界遍历

相关帖子

二叉迷宫中的最短路径

在行和列排序的矩阵中搜索

最小交换次数将二叉树转换为二叉搜索树

使用 Trie 实现自动完成功能

最大化总分数

栈指针

叶节点到动态链接库 (DLL)

正整数数组中 k 个整数的最小乘积

数据结构中栈的表示

数字交换后的最大数字 (按奇偶性)

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器