首页 > 代码库 > 遍历二叉树

遍历二叉树

2024-07-05 14:47:37   233人阅读

二叉树

定义：每个结点最多有两个子树的树

?
1
2
3
4
5
6
struct TreeNode {
     int val;
     TreeNode *left;
     TreeNode *right;
     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 };

基本操作：

1. 先序遍历 ：先访问根节点，在访问左子树，最后访问右子树

?
1
2
3
4
5
6
7
8
9
void PreOrderVisit(TreeNode *root)
{
    if (root == NULL)
        return;
         
    cout << root->val << endl;
    PreOrderVisit(root->left);
    PreOrderVisit(root->right);
}

2. 中序遍历：先访问左子树，在访问根节点，最后访问右子树

?
1
2
3
4
5
6
7
8
9
void PreOrderVisit(TreeNode *root)
{
    if (root == NULL)
        return;
         
    PreOrderVisit(root->left);
    cout << root->val << endl;
    PreOrderVisit(root->right);
}

3. 后序遍历：先访问左子树，在访问右子树，最后访问根节点

?
1
2
3
4
5
6
7
8
9
void PreOrderVisit(TreeNode *root)
{
    if (root == NULL)
        return;
         
    PreOrderVisit(root->left);
    PreOrderVisit(root->right);
    cout << root->val << endl;
}

可见，所谓的前序，中序，后序遍历仅仅是由访问根节点的顺序决定。

4. 层次遍历 ： 一层一层访问

 借助一个队列，将每一层的结点都存放于队列中，从队列中取数据。

 那么如何记录一层呢，可以通过记录每层的个数。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void LevelVisit(TreeNode *root)
{
    if (root == NULL)
        return;
         
    deque<TreeNode*> q;
    q.push_back(root);
     
    int levelNum = 0;
    while (!q.empty())
    {
        levelNum = q.size();
        while (levelNum > 0)
        {
            TreeNode *node = q.front();
            q.pop_front();
            levelNum--;
 
            cout << node->val << " ";
 
            if (root->left != NULL)
                q.push_back(root->left);
            if (root->right != NULL)
                q.push_back(root->right);
        }
        cout << endl;
    }
}　

5. 求树的高度

?
1
2
3
4
5
6
7
8
9
10
int Height(Tree *root)
{
    if (root == NULL)
        return 0;
         
    int lh = Height(root->left);
    int rh = Height(root->right);
     
    return max(lh, rh) + 1;
}

基本操作应该就这些，还是很简单的。


联系
我们