数据结构与算法-树篇（C语言版）

树

二叉树遍历

1. 构建

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode * left, * right;
} * Tree;


int main() {
    struct TreeNode * A = malloc(sizeof (Tree));
    struct TreeNode * B = malloc(sizeof (Tree));
    struct TreeNode * C = malloc(sizeof (Tree));

    A->data = 'A';
    B->data = 'B';
    C->data = 'C';
    A->left = B;
    A->right = C;
    B->left = B->right = NULL;
    C->left = C->right = NULL;
}

2. 递归遍历

#include <stdio.h>
#include <stdlib.h>

typedef struct TreeNode {
    char data;
    struct TreeNode * left, * right;
} * Tree;

void visit(Tree root) {
    printf("%c", root->data);
}

// 前序遍历
void preOrder(Tree root) {
    if(root) {
        visit(root);
        preOrder(root->left);
        preOrder(root->right);
    }
}

// 中序遍历
void inOrder(Tree root) {
    if(root) {
        inOrder(root->left);
        visit(root);
        inOrder(root->right);
    }
}


// 后序遍历
void postOrder(Tree root) {
    if(root) {
        postOrder(root->left);
        postOrder(root->right);
        visit(root);
    }
}

3. 非递归遍历

前序中序后序均利用了栈

层序利用了队列

#include <stdio.h>
#include <stdlib.h>

/**
 * 二叉树节点
 */
typedef struct TreeNode {
    char data;
    struct TreeNode * left, * right;
} * Tree;

/**
 * 栈
 */
typedef struct StackNode {
    // 栈中存储的是二叉树节点
    Tree treeNode;
    struct StackNode * next;
} * Stack;

/**
 * 栈空判断
 */
_Bool isEmpty(Stack stack) {
    return stack->next == NULL;
}

/**
 * 栈初始化
 */
void initStack(Stack stack) {
    stack->next = NULL;
}

/**
 * 入栈
 */
void pushStack(Stack stack, Tree root) {
    struct StackNode * newStackNode = malloc(sizeof (Stack));
    newStackNode->next = stack->next;
    newStackNode->treeNode = root;
    stack->next = newStackNode;
}

/**
 * 出栈
 */
Tree popStack(Stack stack) {
    struct StackNode * topStackNode = stack->next;
    stack->next = topStackNode->next;
    Tree pNode = topStackNode->treeNode;
    free(topStackNode);
    return pNode;
}

void visit(Tree root) {
    printf("%c", root->data);
}

// 前序遍历
void preOrder(Tree root) {
    struct StackNode stack;
    struct TreeNode * p = root;
    initStack(&stack);
    while (p || !isEmpty(&stack)) {
        if(p) {
            visit(p);
            pushStack(&stack, p);
            p = p->left;
        }
        else {
            p = popStack(&stack);
            p = p->right;
        }
    }
}

// 中序遍历
void inOrder(Tree root) {
    struct StackNode stack;
    initStack(&stack);
    struct TreeNode * p = root;
    while (p || !isEmpty(&stack)) {
        if(p) {
            pushStack(&stack, p);
            p = p->left;
        } else {
            p = popStack(&stack);
            visit(p);
            p = p->right;
        }
    }
}


// 仅获取栈顶元素（并不出栈）
Tree getTopTreeNode(Stack stack) {
    return stack->next->treeNode;
}
// 后序遍历
void postOrder(Tree root) {
    struct StackNode stack;
    initStack(&stack);
    struct TreeNode * p = root;
    // 用于标记右孩子是否已被访问
    struct TreeNode * rightFlag = NULL;
    while (p || !isEmpty(&stack)) {
        if(p) {
            pushStack(&stack, p);
            p = p->left;
        } else {
            // 仅获取栈顶元素
            p = getTopTreeNode(&stack);
            // 有右孩子且未被访问过
            if(p->right && p->right != rightFlag) {
                p = p->right;
            } else {
                p = popStack(&stack);
                visit(p);
                // 标记访问过的节点并重置p指针
                rightFlag = p;
                p = NULL;
            }
        }
    }
}

/**
 * 队列
 */
typedef struct QueueNode {
    Tree treeNode;
    struct QueueNode * next;
} * QueueNode;
// 队列的头尾指针
typedef struct Queue {
    struct QueueNode * front, * rear;
} * Queue;

/**
 * 初始化队列
 */
void initQueue(Queue queue) {
    QueueNode qNode = malloc(sizeof (QueueNode));
    queue->front = queue->rear = qNode;
}

/**
 * 入队
 */
void enQueue(Queue queue, Tree root) {
    QueueNode newQNode = malloc(sizeof (QueueNode));
    newQNode->next = queue->rear->next;
    newQNode->treeNode = root;
    queue->rear->next = newQNode;
    queue->rear = newQNode;
}

/**
 * 出队
 */
Tree deQueue(Queue queue) {
    struct QueueNode * tempNode = queue->front->next;
    Tree pNode = tempNode->treeNode;
    queue->front->next = tempNode->next;
    // 队列只剩一个元素的情况
    if(tempNode == queue->rear) {
        queue->rear = queue->front;
    }
    free(tempNode);
    return pNode;
}

/**
 * 队列判空操作
 */
_Bool isEmptyQueue(Queue queue) {
    return queue->front == queue->rear;
}

/**
 * 层次遍历
 */
void levelOrder(Tree root) {
    struct Queue queue;
    initQueue(&queue);
    enQueue(&queue, root);
    while (!isEmptyQueue(&queue)) {
        root = deQueue(&queue);
        visit(root);
        // 看当前节点是否有左右孩子，有就全部入队
        if(root->left) {
            enQueue(&queue, root->left);
        }
        if(root->right) {
            enQueue(&queue, root->right);
        }
    }
}

线索二叉树

线索化的过程就是在遍历的过程中修改空指针的过程

1. 前序线索化

#include <stdio.h>

typedef struct TreeNode{
    int data;
    struct TreeNode * left, * right;
    // 0表示孩子，1表示线索
    int leftTag, rightTag;
}* ClueTree;

// 始终指向刚刚访问过的结点
ClueTree pre = NULL;

// 前序线索化
void preOrder(ClueTree root) {
    if(root) {
        if(root->left == NULL) {
            root->left = pre;
            root->leftTag = 1;
        }
        if(pre && pre->right == NULL) {
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
        if(root->leftTag == 0) {
            preOrder(root->left);
        }
        if(root->rightTag == 0) {
            preOrder(root->right);
        }
    }
}

前序线索化后遍历：

void preTraverse(ClueTree root) {
    while (root) {
        printf("%c", root->data);
        // 左边是孩子，先走左边
        if(root->leftTag == 0) {
            root = root->left;
        } else{
            // 左边不是孩子，无论右边是线索还是孩子都要走了
            root = root->right;
        }
    }
}

2. 中序线索化

// 中序线索化
void inOrder(ClueTree root) {
    if(root) {
        // 递归左孩子
        if(root.leftTag == 0) {
            inOrder(root->left);
        }
        
        // 没有左孩子时
        if(root->left == NULL) {
            // 前驱线索
            root->left = pre;
            root->leftTag = 1;
        }
        // 没有右孩子时
        if(pre && pre->right == NULL) {
            // 后继线索
            pre->right = root;
            pre->rightTag = 1;
        }
        // 记录刚访问的结点
        pre = root;
        
        if(root.rightTag == 0) {
             // 递归右孩子
        	inOrder(root->right);
        }
    }
}

中序线索化后遍历：

// 中序线索后遍历
void inTraverse(ClueTree root) {
    while (root) {
        // 中序遍历需先去到最左边，若是非线索则持续往左边走
        while (root && root->leftTag == 0) {
            root = root->left;
        }
        // 去到最左边，打印中序遍历第一个结点
        printf("%c", root->data);
        // 有后继线索，沿着线索往后即可
        while(root && root->rightTag == 1) {
            root = root->right;
            printf("%c", root->data);
        }
        // 否则继续正常处理右孩子
        root = root->right;
    }
}

3. 后序线索化

void postOrder(ClueTree root) {
    if(root) {
        if(root.leftTag == 0) {
            postOrder(root->left);
        }
        if(root.rightTag == 0) {
            postOrder(root->right);
        }
        
        // 线索化
        if(root->left == NULL) {
            root->left = pre;
            root->leftTag = 1;
        }
        if(pre && pre->right == NULL) {
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
    }
}

后序线索化后遍历：

• 首先需要修改结点结构，添加一个指向双亲结点的指针域

typedef struct TreeNode{
    int data;
    struct TreeNode * left, * right， * parent;
    // 0表示孩子，1表示线索
    int leftTag, rightTag;
}* ClueTree;

• 线索化操作同时建立父子关系

void postOrder(ClueTree root) {
    if(root) {
        if(root.leftTag == 0) {
            postOrder(root->left);
            // 建立父子关系
            if(root->left)
                root->left->parent = root;
        }
        if(root.rightTag == 0) {
            postOrder(root->right);
            // 建立父子关系
            if(root->right)
                root->right->parent = root;
        }
        
        // 线索化
        if(root->left == NULL) {
            root->left = pre;
            root->leftTag = 1;
        }
        if(pre && pre->right == NULL) {
            pre->right = root;
            pre->rightTag = 1;
        }
        pre = root;
    }
}

• 后序线索后遍历

void postTraverse(ClueTree root) {
    // 记录上一个访问节点和当前节点
    ClueTree lastNode = NULL;
    ClueTree currentNode = root;
    while (currentNode) {
        // 一直往最左边走
        while (currentNode->left != lastNode && currentNode->leftTag == 0) {
            currentNode =  currentNode->left;
        }
        // 往右若有线索则跟随线索一直走
        while (currentNode && currentNode->rightTag  == 1) {
            printf("%c",  currentNode->data);
            lastNode = currentNode;
            currentNode = currentNode->right;
        }
        // 上面情况（左右节点情况已结束），此时需要处理的是兄弟节点
        // 特殊情况处理：若此时的节点就是根节点且其右孩子也已经被访问过，说明此时就是最后一个节点了
        if (currentNode == root && currentNode->right == lastNode) {
            printf("%c", currentNode->data);
            return;
        }
        // 若不是特殊情况，则表示需要通过父节点寻找兄弟节点了（如图中去到了B结点，需要寻找兄弟结点C）
        while(currentNode && currentNode->right == lastNode) {
            printf("%c", currentNode->data);
            lastNode = currentNode;
            currentNode =  currentNode->parent;
        }
        // 若右边不是线索，则直接往右找孩子，若是线索则等下一轮循环解决
        if(currentNode && currentNode->rightTag == 0) {
            currentNode = currentNode->right;
        }
    }
}

二叉查找树

又可以叫二叉排序树

• 所有左孩子均比根节点小
• 所有右孩子均比根节点大

1. 创建

#include <stdio.h>
#include <malloc.h>

typedef struct TreeNode{
    int data;
    struct TreeNode * left, * right;
}* Node;

Node createNode(int data) {
    Node root = malloc(sizeof (struct TreeNode));
    root->left = root->right = NULL;
    root->data = data;
    return root;
}

// 一边比较一边插入
Node insert(Node root, int data) {
    if(root) {
        // 插入的元素比根节点小，往左走
        if(root->data > data) {
            root->left = insert(root->left, data);
        }
        // 插入元素比根节点大，往右走
        else if(root->data < data) {
            root->right = insert(root->right, data);
        }
    } else {
        // 遇到空节点，代表可以插入了，创建新节点占位
        root = createNode(data);
    }
    return root;
}

void inOrder(Node root) {
    if(root) {
        inOrder(root->left);
        printf("%d\t", root->data);
        inOrder(root->right);
    }
}


int main() {
    Node root = insert(NULL, 18);   //插入后，得到根结点
    insert(root, 10);   
    insert(root, 22);   
    inOrder(root);   //用中序遍历查看一下结果
}

2. 查找

Node find(Node root, int target) {
    while (root) {
        // 目标值大的往右找
        if(root->data < target) {
            root = root->right;
        } 
        // 小的往左找
        else if(root->data > target) {
            root = root->left;
        } 
        // 找到了
        else {
            return root;
        }
    }
    // 遍历完都未找到
    return NULL;
}

3. 查找最大值

int findMax(Node root) {
    while (root && root->right) {
        root = root->right;
    }
    return root->data;
}

4. 删除

• 删除的是叶子结点
• 删除的结点还带有一个孩子
• 删除的结点带有两个孩子
  • 让左子树中最大值结点上位
  • 让右子树中最小值结点上位