二叉树

发表于 分类于 本文字数： 12k
二叉树的建立、遍历、线索化

生成二叉树

首先得快速生成一棵二叉树才能继续接下来的工作，下面是一棵二叉排序树的生成

定义树和树结点的结构体

1
2
3
4
5
6
7
8
9
// 顺序表中的数据元素
typedef int ElemType;

// 定义二叉树结点的结构体
typedef struct Node {
    ElemType data;      // 数据域
    struct Node* left;  // 左子树
    struct Node* right; // 右子树
} Node, *SortTree;

向二叉排序树中插入结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 向二叉排序树中插入结点
 * @param tree
 * @param elemType
 */
void insert(SortTree *tree, ElemType elemType) {
    if ((*tree) == NULL) {
        // 如果树是空的，创建新结点
        (*tree) = (Node*)malloc(sizeof(Node));
        (*tree)->data = elemType;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
    } else if (elemType < (*tree)->data) {
        // 插入到左子树
        insert(&((*tree)->left), elemType);
    } else {
        // 插入到右子树
        insert(&((*tree)->right), elemType);
    }
}

通过如下代码，向二叉树中插入

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SortTree sortTree = NULL;

/**
 * 形成二叉树如下
 *        5
 *      /   \
 *     3     7
 *    / \   / \
 *   2   4 6   8
 */
insert(&sortTree, 5);
insert(&sortTree, 3);
insert(&sortTree, 7);
insert(&sortTree, 2);
insert(&sortTree, 4);
insert(&sortTree, 6);
insert(&sortTree, 8);

访问结点数据

1
2
3
4
5
6
7
/**
 * 访问根结点数据
 * @param elemType
 */
void visit(ElemType elemType) {
    printf("%d ", elemType);
}

遍历二叉树

递归遍历

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
32
33
34
35
/**
 * 中序遍历（左-根-右）
 * @param tree
 */
void inorderTraversal(SortTree tree) {
    if (tree != NULL) {
        inorderTraversal(tree->left);  // 访问左子树
        visit(tree->data);             // 访问根结点数据
        inorderTraversal(tree->right); // 访问右子树
    }
}

/**
 * 先序遍历（根-左-右）
 * @param tree
 */
void preorderTraversal(SortTree tree) {
    if (tree != NULL) {
        visit(tree->data);             // 访问根结点数据
        preorderTraversal(tree->left); // 访问左子树
        preorderTraversal(tree->right);// 访问右子树
    }
}

/**
 * 后序遍历（左-右-根）
 * @param tree
 */
void postorderTraversal(SortTree tree) {
    if (tree != NULL) {
        postorderTraversal(tree->left); // 访问左子树
        postorderTraversal(tree->right);// 访问右子树
        visit(tree->data);              // 访问根结点数据
    }
}

非递归遍历

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
/**
 * 非递归中序遍历（左-根-右）
 * @param tree
 */
void inorderTraversal2(SortTree tree) {
    // 需要借助一个栈实现
    int top = -1;                       // 栈顶指针
    Node* stack[STACK_MAX_LENGTH];  // 栈

    SortTree p = tree;

    while (p != NULL || top != -1) {
        if (p != NULL) {
            // 根结点及其所有左孩子统统入栈
            stack[++top] = p;
            p = p->left;
        } else {
            // 从栈中取出结点并访问
            p = stack[top--];
            visit(p->data);

            // 转向结点的右子树
            // 若该右子树为NULL，下一趟循环会从栈中继续取结点
            // 若该右子树不为NULL，下一趟循环会将该右子树及其所有左孩子入栈
            p = p->right;
        }
    }
}

/**
 * 非递归先序遍历（根-左-右）
 * @param tree
 */
void preorderTraversal2(SortTree tree) {
    // 需要借助一个栈实现
    int top = -1;                       // 栈顶指针
    Node* stack[STACK_MAX_LENGTH];  // 栈

    SortTree p = tree;

    while (p != NULL || top != -1) {
        if (p != NULL) {
            // 根结点及其所有左孩子统统入栈
            stack[++top] = p;

            // 入栈时访问节点
            visit(p->data);

            p = p->left;
        } else {
            // 从栈中取出结点
            p = stack[top--];

            // 转向结点的右子树
            // 若该右子树为NULL，下一趟循环会从栈中继续取结点
            // 若该右子树不为NULL，下一趟循环会将该右子树及其所有左孩子入栈
            p = p->right;
        }
    }
}

/**
 * 非递归后序遍历（左-右-根）
 * @param tree
 */
void postorderTraversal2(SortTree tree) {
    // 需要借助一个栈实现
    int top = -1;                       // 栈顶指针
    Node* stack[STACK_MAX_LENGTH];  // 栈

    SortTree p = tree;
    Node *t = NULL;

    while (p != NULL || top != -1) {
        if (p != NULL) {
            // 根结点及其所有左孩子统统入栈
            stack[++top] = p;
            p = p->left;
        } else {
            // GetTop操作，读取栈顶结点
            p = stack[top];
            if (p->right != NULL && p->right != t) {
                // 如果栈顶结点的右孩子结点未被访问过,则转向右孩子结点
                p = p->right;
            } else {
                // 如果栈顶结点的右孩子结点已经被访问过,从栈中取出结点并访问
                p = stack[top--];
                visit(p->data);

                // 记录访问过的结点,并置空p,下一趟循环直接从栈中取结点
                t = p;
                p = NULL;
            }
        }
    }
}

层序遍历

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
/**
 * 层序遍历
 * @param tree
 */
void levelTraversal(SortTree tree) {
    // 层序遍历需要借助一个队列
    Node *queue[QUEUE_MAX_LENGTH];
    int front = 0, rear = 0;    // 队首及队尾指针

    SortTree p = tree;

    queue[rear++] = p;

    while (rear > front){
        // 结点出队
        p = queue[front++];
        // 访问结点
        visit(p->data);
        // 结点左右孩子入队
        if (p->left != NULL)
            queue[rear++] = p->left;
        if (p->right != NULL)
            queue[rear++] = p->right;
    }
}

线索二叉树

中序线索二叉树

添加ltag rtag标志结点的左右指针是否是线索

定义线索二叉树结点的结构体

1
2
3
4
5
6
// 定义线索二叉树结点的结构体
typedef struct Node {
    ElemType data;
    struct Node *left, *right;  // 左右子树指针
    int ltag, rtag;             // 标志左右指针是否是线索
} Node, *SortTree;

在插入结点时，将ltag rtag初始化为0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 向二叉排序树中插入结点
 * @param tree
 * @param elemType
 */
void insert(SortTree *tree, ElemType elemType) {
    if ((*tree) == NULL) {
        // 如果树是空的，创建新结点
        (*tree) = (Node*)malloc(sizeof(Node));
        (*tree)->data = elemType;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
        (*tree)->rtag = 0;
        (*tree)->ltag = 0;
    } else if (elemType < (*tree)->data) {
        // 插入到左子树
        insert(&((*tree)->left), elemType);
    } else {
        // 插入到右子树
        insert(&((*tree)->right), elemType);
    }
}

通过中序遍历给二叉树线索化

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * 以中序遍历的方式建立线索
 * @param currentNode   当前遍历到的结点
 * @param previousNode  当前结点的前驱结点
 */
void inThread(Node *currentNode, Node **previousNode) {
    if (currentNode == NULL)
        return;

    // 递归，先对当前结点的左子树进行线索化
    inThread(currentNode->left, previousNode);

    // 建立 当前结点 的 前驱结点 的 后继线索
    // 当前结点的前驱结点是左子树中按中序遍历时的最后一个结点
    // 即，若 当前结点 的 前驱结点 的 右指针为空，则使其指向当前结点
    if ((*previousNode) != NULL && (*previousNode)->right == NULL) {
        (*previousNode)->rtag = 1;
        (*previousNode)->right = currentNode;
    }
    // 建立 当前结点 的 前驱线索
    if (currentNode->left == NULL) {
        currentNode->ltag = 1;
        currentNode->left = (*previousNode);
    }
    // 使当前结点成为前驱结点
    (*previousNode) = currentNode;

    // 递归，对右子树进行线索化
    inThread(currentNode->right, previousNode);
}

/**
 * 给二叉树建立线索
 * @param sortTree
 */
void createInThread(SortTree sortTree) {
    if (sortTree == NULL)
        return;

    Node *preNode = NULL;
    inThread(sortTree, &preNode);
    // 处理最后一个结点
    // 第一个结点的前驱线索和最后一个结点的后继线索都指向NULL，且tag为1
    preNode->right = NULL;
    preNode->rtag = 1;
}

在中序线索二叉树中，寻找某结点的前驱结点

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
/**
 * 在中序线索二叉树中，寻找第一个结点
 * @param sortTree
 * @return
 */
Node* firstNode(SortTree sortTree) {
    Node *temp = sortTree;
    while (temp->ltag == 0)
        temp = temp->left;

    return temp;
}

/**
 * 提供一个结点，在中序线索二叉树中，找到该结点的后继结点
 * @param node
 * @return
 */
Node* nextNode(Node *node) {
    // 若该结点存在右子树，则右子树中第一个结点即为当前结点的后继结点
    if (node->rtag == 0)
        return firstNode(node->right);

    // 若该结点不存在右子树，则其右指针域所指的结点必是其后继结点
    return node->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
/**
 * 在中序线索二叉树中，寻找线索树树中最后一个结点
 * @param sortTree
 * @return
 */
Node* tailNode(SortTree sortTree) {
    Node *temp = sortTree;
    while (temp->rtag == 0)
        temp = temp->right;

    return temp;
}

/**
 * 提供一个结点，在中序线索二叉树中，找到该结点的前驱结点
 * @param node
 * @return
 */
Node* preNode(Node *node) {
    // 若该结点存在左子树，则左子树中最后一个结点即为当前结点的前驱结点
    if (node->ltag == 0)
        return tailNode(node->left);

    // 若该结点不存在左子树，则其左指针域所指的结点必是其前驱结点
    return node->left;
}

遍历中序线索二叉树

1
2
3
4
5
6
7
8
9
10
11
/**
 * 遍历中序线索二叉树
 * @param sortTree
 */
void inOrder(SortTree sortTree) {
    Node *node = firstNode(sortTree);
    while (node != NULL) {
        visit(node->data);
        node = nextNode(node);
    }
}

先序线索二叉树

在先序线索二叉树中，若某结点拥有左子树，那么就无法通过左线索来寻找前驱，此时他的前驱有可能是父结点，也有可能是以左兄弟结点为根结点的子树的最后一个结点，无论如何要访问其父结点，所以在结点的结构中添加父结点，形成三叉树

定义线索三叉树结点的结构体

1
2
3
4
5
6
7
// 定义线索三叉树结点的结构体
typedef struct Node {
    ElemType data;
    struct Node *left, *right;  // 左右子树指针
    struct Node *parent;        // 父结点
    int ltag, rtag;             // 标志左右指针是否是线索
} Node, *SortTree;

插入结点，在插入结点时，需指明结点的父结点

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
SortTree parentNode = NULL;

/**
 * 向三叉排序树中插入结点
 * @param tree
 * @param elemType
 */
void insert(SortTree *tree, ElemType elemType) {
    if ((*tree) == NULL) {
        // 如果树是空的，创建新结点
        (*tree) = (Node*)malloc(sizeof(Node));
        (*tree)->data = elemType;
        (*tree)->right = NULL;
        (*tree)->left = NULL;
        (*tree)->parent = parentNode;   // 指明父结点
        (*tree)->rtag = 0;
        (*tree)->ltag = 0;
        parentNode = NULL;
    } else if (elemType < (*tree)->data) {
        // 插入到左子树
        parentNode = *tree;
        insert(&((*tree)->left), elemType);
    } else {
        // 插入到右子树
        parentNode = *tree;
        insert(&((*tree)->right), elemType);
    }
}

通过先序遍历给三叉树线索化

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/**
 * 以先序遍历的方式建立线索
 * @param currentNode   当前结点
 * @param previousNode  前驱结点
 */
void preThread(Node *currentNode, Node **previousNode) {
    if (currentNode == NULL)
        return;

    // 建立 当前结点 的 前驱结点 的 后继线索
    if ((*previousNode) != NULL && (*previousNode)->right == NULL) {
        (*previousNode)->rtag = 1;
        (*previousNode)->right = currentNode;
    }
    // 建立 当前结点 的 前驱线索
    if (currentNode->left == NULL) {
        currentNode->ltag = 1;
        currentNode->left = (*previousNode);
    }
    // 使当前结点成为前驱结点
    (*previousNode) = currentNode;

    // 递归，先对左子树进行线索化
    // 需要防止对建立后的线索再进行线索化
    if (currentNode->ltag == 0)
        preThread(currentNode->left, previousNode);

    // 递归，对右子树进行线索化
    preThread(currentNode->right, previousNode);
}

/**
 * 给三叉树建立线索
 * @param sortTree
 */
void createPreThread(SortTree sortTree) {
    if (sortTree == NULL)
        return;

    Node *preNode = NULL;
    preThread(sortTree, &preNode);
    // 处理最后一个结点
    preNode->right = NULL;
    preNode->rtag = 1;
}

在先序线索三叉树中，寻找某结点的前驱结点

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
32
33
34
35
36
37
/**
 * 在先序线索三叉树中，寻找最后一个结点
 * @param sortTree
 * @return
 */
Node* tailNode(SortTree sortTree) {
    if (sortTree->rtag == 0)
        return tailNode(sortTree->right);
    else if (sortTree->ltag == 0)
        return tailNode(sortTree->left);

    return sortTree;
}

/**
 * 提供一个结点，在先序线索三叉树中，找到该结点的前驱结点
 * 注意，若某结点拥有左子树，那么就无法通过左线索来寻找前驱
 * @param node
 * @return
 */
Node* preNode(Node *node) {
    // 若该结点不存在左子树，则存在左线索，左线索必是其前驱结点
    if (node->ltag == 1)
        return node->left;
    
    // 若该结点存在左子树，那么就无法通过左线索来寻找前驱
    /* 下面两个条件
     * 1. 若parent为空，说明是根结点
     * 2. 防止当前结点就是parent的左子结点
     */
    if (node->parent != NULL && node->parent->left != node)
        // 如果存在左兄弟结点，那么当前结点的前驱结点即为“以左兄弟结点为根结点的树的尾结点”
        return tailNode(node->parent->left);
    else
        // 如果不存在左兄弟结点，那么当前结点的前驱结点是父结点
        return node->parent;
}

在先序线索三叉树中，寻找某结点的后继结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 提供一个结点，在先序线索三叉树中，找到该结点的后继结点
 * @param node
 * @return
 */
Node* nextNode(Node *node) {
    // 若该结点存在左子树，则左子树的根结点为后继结点
    if (node->ltag == 0)
        return node->left;

    // 不存在左子树，但存在右子树，则右子树的根结点为后继结点
    // 不存在左右子树，则其右指针域所指的结点必是其后继结点
    return node->right;
}

遍历先序线索三叉树

1
2
3
4
5
6
7
8
9
10
11
/**
 * 遍历先序线索三叉树
 * @param sortTree
 */
void preOrder(SortTree sortTree) {
    Node *node = sortTree;
    while (node != NULL) {
        visit(node->data);
        node = nextNode(node);
    }
}

后序线索二叉树

在后序线索二叉树中，同样需要三叉树，因为如果某结点拥有右子树，那么就无法通过右线索来寻找后继，此时他的后继有可能是父结点，也有可能是以右兄弟结点为根结点的子树的第一个结点，无论如何要访问其父结点

通过先序遍历给三叉树线索化

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
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * 以后序遍历的方式建立线索
 * @param currentNode   当前结点
 * @param previousNode  前驱结点
 */
void postThread(Node *currentNode, Node **previousNode) {
    if (currentNode == NULL)
        return;

    // 递归，先对左子树进行线索化
    postThread(currentNode->left, previousNode);

    // 递归，对右子树进行线索化
    postThread(currentNode->right, previousNode);

    // 建立 当前结点 的 前驱结点 的 后继线索
    if ((*previousNode) != NULL && (*previousNode)->right == NULL) {
        (*previousNode)->rtag = 1;
        (*previousNode)->right = currentNode;
    }
    // 建立 当前结点 的 前驱线索
    if (currentNode->left == NULL) {
        currentNode->ltag = 1;
        currentNode->left = (*previousNode);
    }
    // 使当前结点成为前驱结点
    (*previousNode) = currentNode;
}

/**
 * 给三叉树建立线索
 * @param sortTree
 */
void createPostThread(SortTree sortTree) {
    if (sortTree == NULL)
        return;

    Node *preNode = NULL;
    postThread(sortTree, &preNode);

    // 处理最后一个结点，防止把根结点的右子树处理掉
    if (preNode->right == NULL)
        preNode->rtag = 1;
}

在先序线索三叉树中，寻找某结点的前驱结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 提供一个结点，在先序线索三叉树中，找到该结点的前驱结点
 * @param node
 * @return
 */
Node* preNode(Node *node) {
    // 若该结点存在右子树，则右子树的根结点为前驱结点
    if (node->rtag == 0)
        return node->right;

    // 不存在左子树，但存在左子树，则左子树的根结点为前驱结点
    // 不存在左右子树，则其左指针域所指的结点必是其前驱结点
    return node->left;
}

在先序线索三叉树中，寻找某结点的后继结点

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
32
33
34
35
36
/**
 * 在后序线索二叉树中，寻找第一个结点
 * @param sortTree
 * @return
 */
Node* firstNode(SortTree sortTree) {
    if (sortTree != NULL && sortTree->ltag == 0)
        return firstNode(sortTree->left);

    if (sortTree != NULL && sortTree->rtag == 0)
        return firstNode(sortTree->right);

    return sortTree;
}

/**
 * 提供一个结点，在先序线索三叉树中，找到该结点的后继结点
 * @param node
 * @return
 */
Node* nextNode(Node *node) {
    // 若该结点不存在右子树，则存在右线索，右线索必是其后继结点
    if (node->rtag == 1)
        return node->right;

    // 若该结点存在右子树，那么就无法通过右线索来寻找后继
    // 此时后继结点要么是“以右兄弟结点为根的子树”中第一个结点，要么是父结点
    /* 下面两个条件
     * 1. 若parent为空，说明是根结点，没有后继
     * 2. 防止当前结点就是parent的右结点
     */
    if (node->parent != NULL && node->parent->right != node)
        return firstNode(node->parent->right);

    return node->parent;
}

遍历后序线索三叉树

1
2
3
4
5
6
7
8
9
10
11
/**
 * 遍历后序线索三叉树
 * @param sortTree
 */
void postOrder(SortTree sortTree) {
    Node *node = firstNode(sortTree);
    while (node != NULL) {
        visit(node->data);
        node = nextNode(node);
    }
}