Tree

  发表  更新  NJU  6 分钟读完 (大约868个字)  0次访问

二叉树的相关算法
递归 && 非递归 && 搜索树

树的递归算法

先-中-后序遍历

1
2
3
4
5
6
7
8
void preOrder(TreeNode *root)
{
    // visit(p);     先序
    preOrder(root->left);
    // visit(p);     中序
    preOrder(root->right);
    // visit(p);     后序
}

统计节点数

1
2
3
4
5
6
7
8
9
10
11
12
int degree(TreeNode *root)
{
    if (!root)
        return 0;

    if (!(root->left || root->right))  // 0-degree
    if ((root->left && !root->right) || (root->right && !root->left))   // 1-degree
    if (root->left && root->right)     // 2-degree
        return degree(root->left) + degree(root->right) + 1;
    else
        return degree(root->left) + degree(root->right);
}

树的高度

1
2
3
4
5
6
7
8
int height(TreeNode *root)
{
    if (!root)
        return 0;
    int hleft = height(root->left);
    int hright = height(root->right);
    return (hleft > hright) ? hleft + 1 : hright + 1;
}

树的宽度

1
2
3
4
5
6
7
8
9
10
void width(TreeNode *root, int k, int *v)
{
    if (!root)
        return;
    v[k]++;
    if (v[0] < v[k])
        v[0] = v[k];
    width(root->left, k + 1, v);
    width(root->right, k + 1, v);
}

先序+中序构建树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode *buildTree(int *pre, int s1, int e1, int *in, int s2, int e2)
{
    if (s1 > e1)
        return NULL;

    int f = pre[s1];
    TreeNode *p = new TreeNode(f);
    int i;
    for (i = 0; in[s2 + i] != f; i++)
        ;
    p->left = buildTree(pre, s1 + 1, s1 + i, in, s2, s2 + i - 1);
    p->right = buildTree(pre, s1 + i + 1, e1, in, s2 + i + 1, e2);

    cout << "Build Tree is:" << endl;
    prettyPrintTree(p);
    return p;
}

交换左右子树

1
2
3
4
5
6
7
8
9
10
11
12
13
TreeNode *swapLeftAndRight(TreeNode *root)
{
    if (root)
    {
        swapLeftAndRight(root->left);
        swapLeftAndRight(root->right);
        
        TreeNode *temp = root->left;
        root->left = root->right;
        root->right = temp;
    }
    return root;
}

先序第k个节点

1
2
3
4
5
6
7
8
9
10
11
12
13
int preOrderOfK(TreeNode *root, int &i, int k)
{
    if (!root)
        return -1;
    if (i == k)
        return root->val;
    i++;
    int val = preOrderOfK(root->left, i, k);
    if (val != -1)
        return val;
    val = preOrderOfK(root->right, i, k);
    return val;
}

最大值

1
2
3
4
5
6
7
8
9
int maxVal(TreeNode *root)
{
    if (!root)
        return -1;
    int maxL = maxVal(root->left);
    int maxR = maxVal(root->right);
    int max = maxL > maxR ? maxL : maxR;
    return root->val > max ? root->val : max;
}

删除节点

1
2
3
4
5
6
7
8
9
void deleteTree(TreeNode *root)
{
    if (root)
    {
        deleteTree(root->left);
        deleteTree(root->right);
        delete root;
    }
}

删除特点节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
TreeNode *deleteValOfX(TreeNode *root, int x)
{
    if (!root)
        return NULL;
    if (root->val == x)
    {
        deleteTree(root);
        root = NULL;
    }
    else
    {
        root->left = deleteValOfX(root->left, x);
        root->right = deleteValOfX(root->right, x);
    }
    return root;
}

树的非递归算法

先序遍历

算法1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void preOrder1(TreeNode *root)
{
    Stack S;
    TreeNode *p = root;

    while (p || !S.empty())
    {
        if (p)
        {
            visit(p);
            if (p->right)
                S.push(p->right);
            p = p->left;
        }
        else
            p = S.pop();
    }
}

算法2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void preOrder2(TreeNode *root)
{
    Stack S;
    TreeNode *p = root;
    S.push(p);

    while (!S.empty())
    {
        p = S.pop();
        if (p)
        {
            visit(p);
            S.push(p->right);
            S.push(p->left);
        }
    }
}

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void inOrder(TreeNode *root)
{
    Stack S;
    TreeNode *p = root;

    while (p || !S.empty())
    {
        if (p)
        {
            S.push(p);
            p = p->left;
        }
        else
        {
            p = S.pop();
            visit(p);
            p = p->right;
        }
    }
}

后序遍历

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
29
30
31
void postOrder(TreeNode *root)
{
    Stack S;
    TreeNode *p = root, *r;

    while (p || !S.empty())
    {
        if (p)
        {
            S.push(p);
            p = p->left;
        }
        else
        {
            p = S.top();
            if (p->right && p->right != r)
            {
                p = p->right;
                S.push(p);
                p = p->left;
            }
            else
            {
                p = S.pop();
                visit(p);
                r = p;
                p = NULL;
            }
        }
    }
}

层次遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void levelOrder(TreeNode *root)
{
    Queue Q;

    if (!root)
        return;

    TreeNode *p = root;
    Q.enqueue(p);

    while (!Q.empty())
    {
        p = Q.dequeue();
        visit(p);
        if (p->left)
            Q.enqueue(p->left);
        if (p->right)
            Q.enqueue(p->right);
    }
}

求树高

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
int height(TreeNode *root)
{
    if (root == NULL)
        return 0;

    Queue Q;
    TreeNode *p = root, *r = root;
    int height = 0;
    Q.enqueue(p);

    while (!Q.empty())
    {
        p = Q.dequeue();
        if (p->left)
            Q.push(p->left);
        if (p->right)
            Q.push(p->right);

        if (p == r)
        {
            height++;
            r = Q.back();
        }
    }
    return height;
}

树的宽度

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
int width(TreeNode *root)
{
    if (!root)
        return 0;
    int width = 0;
    int levelwidth = 0;
    queue<TreeNode *> q;
    TreeNode *p = root, *r = root;
    q.push(p);

    while (!q.empty())
    {
        p = q.front();
        q.pop();
        levelwidth++;
        if (p->left)
            q.push(p->left);
        if (p->right)
            q.push(p->right);
        if (p == r)
        {
            width = (levelwidth > width) ? levelwidth : width;
            levelwidth = 0;
            r = q.back();
        }
    }
    return width;
}

搜索树结构

递归搜索

1
2
3
4
5
6
7
8
9
10
11
TreeNode *search(TreeNode *root, int key)
{
    if (root == NULL)
        return NULL;
    else if (root->val == key)
        return root;
    else if (root->val < key)
        return search(root->right, key);
    else
        return search(root->left, key);
}

非递归搜索

1
2
3
4
5
6
7
8
9
10
11
TreeNode *search(TreeNode *root, int key)
{
    while (root && key != root->val)
    {
        if (key < root->val)
            root = root->left;
        else
            root = root->right;
    }
    return root;
}

插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
bool insert(TreeNode *&root, int key)
{
    if (!root)
    {
        root = new TreeNode(key);
        root->left = root->right = NULL;
        return true;
    }
    else
    {
        TreeNode *p = NULL, *q = NULL;
        q = search(root, key, p);
        if (q)
            return false;
        else if (key < p->val)
            p->left = new TreeNode(key);
        else
            p->right = new TreeNode(key);
        return true;
    }
}

删除

Tree

http://blog.czccc.cc/p/170cf1e2/

作者

Cheng

发布于

2018-08-13

更新于

2022-08-06

许可协议

#

喜欢这篇文章？打赏一下作者吧

评论

关注我
×