数据结构 -- 树的遍历

一.树的结构和方法

//定义树节点的数据类型
typedef struct treeNode{
    int  data;
    struct treeNode* leftChild;
    struct treeNode* rightChild;
    int tag;
}treeNode;

//定义二叉树的数据类型
typedef struct bintree{
    treeNode *root;//记录根节点地址
}bintree;

//初始化结点
treeNode *node(int data){
    treeNode *node = (treeNode *)malloc(sizeof(treeNode));
    node->data = data;
    node->leftChild = NULL;
    node->rightChild = NULL;

    return node;
}

//初始化树
bintree *tree(treeNode *node){
    bintree *tree;
    tree = (bintree *)malloc(sizeof(bintree));
    tree->root = node;
    return tree;
}
//树插入左节点
void insertLeftNode(treeNode *fatherNode,treeNode*LeftNode){
    fatherNode->leftChild = LeftNode;
}
//树插入右节点
void insertRightNode(treeNode *fatherNode,treeNode*rightNode){
    fatherNode->rightChild = rightNode;
}

二.栈的结构与方法

//用链表定义栈
typedef struct SNode *stack;
struct SNode{
    treeNode *data;
    struct SNode *next;
};
//初始化栈
stack CreatStack(){
    stack S;
    S = (stack)malloc(sizeof(struct SNode));
    S->next = NULL;
    return S;
}
//判断栈是否空
int  stackIsEmpty(stack S){
    return (S->next == NULL);
}
//压栈
void Push(treeNode *node ,stack S){
    struct SNode *newNode;
    newNode = (struct SNode *)malloc(sizeof(struct SNode));
    newNode ->data = node;
    newNode->next = S->next;
    S->next = newNode;
}
//出栈
treeNode* Pop(stack S){

    if (stackIsEmpty(S)) {
        printf("空");
        return NULL;
    }else{
        struct SNode *newNode;
        treeNode *topElem;
        newNode = S->next;
        S->next = newNode->next;
        topElem = newNode->data;
        free(newNode);
        return topElem;
    }
}

三.队列的结构与方法

//链表定义队列
typedef struct queueNode{
    treeNode *data;
    struct queueNode *next;
}queueNode;

typedef struct LinkQueue{
    queueNode *rear;
    queueNode *front;
}LinkQueue;
//队列初始化
LinkQueue *createQueue(){
    LinkQueue *queue = (LinkQueue *)malloc(sizeof(LinkQueue));
    if (!queue) {
        printf("空间不足！\n");
        return NULL;
    }
    queue->front = NULL;
    queue->rear = NULL;
    return queue;
}
//判断队列是否空
int queueIsEmpty(LinkQueue* queue){
    return (queue->front == NULL);
}
//队列删除操作
treeNode *queueDelete(LinkQueue *queue){
    if (queueIsEmpty(queue)) {
        printf("队列空\n");
        return NULL;
    }

    queueNode *itempQueueNode = queue->front;
    treeNode *itemData;
    if (queue->front == queue->rear) {
        queue->front = NULL;
        queue->rear = NULL;

    }else{
          queue->front = queue->front->next;
    }
    itemData = itempQueueNode->data;
    free(itempQueueNode);
    return itemData;

}
//队列增加操作
void queueAdd(LinkQueue *queue,treeNode *node){
    queueNode *newNode = (queueNode *)malloc(sizeof(queueNode));
    if (!newNode) {
        printf("空间不足");
        return;
    }
    newNode->data = node;
    newNode->next = NULL;

    if (queue->front == NULL) {
        queue->front = newNode;
    }

    if (queue->rear == NULL) {
        queue->rear = newNode;
    }else{
        queue->rear->next = newNode;
        queue->rear = newNode;
    }

}
//打印队列操作
void PrintQueue(LinkQueue* q) {
    if (queueIsEmpty(q)) {
        printf("空队列\n");
        return;
    }
    printf("打印队列数据元素：\n");
    queueNode* qNode = q->front;
    while (qNode != NULL) {
        printf("%d " , qNode->data->data);
        qNode = qNode->next;
    }
    printf("\n");
}

四.递归实现先序遍历，中序遍历，后序遍历。

//递归实现先序遍历
void preOrderTraversal(treeNode *node){
    if (node) {
        printf("%d\n",node->data);
        preOrderTraversal(node->leftChild);
        preOrderTraversal(node->rightChild);
    }
}
//递归实现中序遍历
void inOrderTraversal(treeNode *node){
    if (node) {
        inOrderTraversal(node->leftChild);
        printf("%d\n",node->data);
        inOrderTraversal(node->rightChild);
    }
}
//递归实现后序遍历
void postOrderTraversal(treeNode *node){
    if (node) {
    postOrderTraversal(node->leftChild);
    postOrderTraversal(node->rightChild);
    printf("%d\n",node->data);
    }
}

五.非递归实现先序遍历，中序遍历，后序遍历。

//非递归先序遍历
void preOrderNoRecursion(bintree *tree){
    treeNode *node = tree->root;
    stack s = CreatStack();
    while (node || !stackIsEmpty(s)) {
        while (node) {
            Push(node, s);
            printf("%d\n",node->data);
            node = node->leftChild;
        }
        if (!stackIsEmpty(s)) {
            node = Pop(s);

            node = node->rightChild;
        }
    }
}

//非递归中序遍历
void inOrderNoRecursion(bintree *tree){
    treeNode *node = tree->root;
    stack s = CreatStack();
    while (node || !stackIsEmpty(s)) {
        while (node) {
            Push(node, s);
            node = node->leftChild;
        }
        if (!stackIsEmpty(s)) {
            node = Pop(s);
            printf("%d\n",node->data);
            node = node->rightChild;
        }
    }
}
//非递归后序遍历
void postOrderNoRecursion(bintree *tree){
    treeNode *node = tree->root;
    stack s = CreatStack();
    while (node || !stackIsEmpty(s)) {
        while (node) {
            Push(node, s);
            node->tag = 1;
            node = node->leftChild;

        }
        if (!stackIsEmpty(s)) {
           struct SNode *newNode = s->next;
            node =  newNode->data;
            if (node->tag == 2) {
                node = Pop(s);
                printf("%d\n",node->data);
                node = NULL;
            }else if(node->tag == 1){
                node ->tag = 2;
                node = node->rightChild;
            }

        }
    }
}

六.层序遍历

//层序遍历
void layerOrder(bintree *tree){
    treeNode *node = tree->root;
    LinkQueue *queue = createQueue();
    if (!queue) {
        return;
    }
    if (!node) {
        return;
    }
    queueAdd(queue, node);

    while (!queueIsEmpty(queue)) {
        treeNode * tempNode = queueDelete(queue);
        printf("%d\n",tempNode->data);

        if (tempNode->leftChild) {
            queueAdd(queue, tempNode->leftChild);
        }
        if (tempNode->rightChild) {
            queueAdd(queue, tempNode->rightChild);
        }

    }


}

七.辅助操作

//非递归插入
void insert(treeNode *insertNode,treeNode *rootNode){

    if (!rootNode) {
        rootNode = insertNode;
        return;
    }
    treeNode *node = rootNode;

    while (node) {
        if (insertNode->data>node->data) {
            if (node->rightChild) {
                node = node->rightChild;
            }else{
                node->rightChild = insertNode;
                return;
            }
        }else if (insertNode->data<node->data){
            if (node->leftChild) {
                node = node->leftChild;
            }else{
                node->leftChild = insertNode;
                return;
            }
        }else if (insertNode->data==node->data){
            return;
        }
    }
}

//递归插入
treeNode * insertRecursionR(int X,treeNode *rootNode){
    if (!rootNode) {
        rootNode = (treeNode *)malloc(sizeof(treeNode));
        rootNode->data = X;
        rootNode->leftChild = rootNode->rightChild = NULL;
    }else{
        if (X<rootNode->data) {
         rootNode->leftChild  = insertRecursionR(X, rootNode->leftChild);
        }else if (X>rootNode->data){
          rootNode->rightChild = insertRecursionR(X, rootNode->rightChild);
        }
    }
    return rootNode;
}


//树中找节点
treeNode * Find(int X,treeNode *rootNode){

    treeNode *node = rootNode;
    while (node) {
        if (X>node->data) {
            node = node->rightChild;
        }else if (X<node->data){
            node = node->leftChild;
        }else{
            return node;
        }
    }
    return NULL;
}
//树中找最小节点
treeNode * FindMin(treeNode *rootNode){

    treeNode *node = rootNode;
    while (node) {
        if (node->leftChild) {
            node = node->leftChild;
        }else{
            return node;
        }
    }
    return NULL;
}
//树中找最大节点
treeNode * FindMax(treeNode *rootNode){

    treeNode *node = rootNode;
    while (node) {
        if (node->rightChild) {
            node = node->rightChild;
        }else{
            return node;
        }
    }
    return NULL;
}

//递归删除结点。顺序分为三步，1.查找该结点。2判断该结点的左右儿子状态。3.删除。查找结点就用上面的方法，然后删除节点第一种是结点有左右儿子，则在左子树查找最大结点替代该结点，或者右子树查找最小结点替代该结点，第二种情况，就是用子节点替代该结点。
treeNode *deleteRecursion(int X,treeNode *rootNode){
    treeNode *tmp;
    if (!rootNode) {
        printf("未找到");
    }else if(X<rootNode->data){
        rootNode->leftChild = deleteRecursion(X, rootNode->leftChild);
    }else if (X>rootNode->data){
        rootNode->rightChild = deleteRecursion(X, rootNode->rightChild);
    }else{
        if (rootNode->leftChild && rootNode->rightChild) {
            tmp = FindMin(rootNode->rightChild);
            rootNode->data = tmp->data;
            rootNode->rightChild = deleteRecursion(rootNode->data, rootNode->rightChild);
        }else{
            tmp = rootNode;
            if (!rootNode->leftChild) {
                rootNode = rootNode->rightChild;
            }else if (!rootNode->rightChild){
                rootNode = rootNode->leftChild;
            }
            free(tmp);
        }
    }
    return rootNode;
}

八.开始测试

//二叉树生成  
 treeNode *n1 = node(1);
        treeNode *n2 = node(2);
        treeNode *n3 = node(3);
        insertLeftNode(n1, n2);
        insertRightNode(n1, n3);
        treeNode *n4 = node(4);
        treeNode *n5 = node(5);
        insertLeftNode(n2, n4);
        insertLeftNode(n4, n5);
        treeNode *n6 = node(6);
        insertRightNode(n4, n6);
        treeNode *n7 = node(7);
        treeNode *n8 = node(8);
        insertLeftNode(n3, n7);
        insertRightNode(n3, n8);
        treeNode *n9 = node(9);
        treeNode *n10 = node(10);
        insertLeftNode(n8, n9);
        insertRightNode(n8, n10);
        //树初始化成功
        bintree *binTree1 = tree(n1);
        //各种遍历方法
        printf("先序遍历 递归：");
        preOrderTraversal(binTree1->root);
        printf("  先序遍历 非递归：");
        preOrderNoRecursion(binTree1);
        printf("  中序遍历 递归：");
        inOrderTraversal(binTree1->root);
        printf("  中序遍历 非递归：");
        inOrderNoRecursion(binTree1);
        printf("  后序遍历 递归：");
        postOrderTraversal(binTree1->root);
        printf("  后序遍历 非递归：");
        postOrderNoRecursion(binTree1);
        printf("  层序遍历 队列：");
        layerOrder(binTree1);

打印结果为：

//有序二叉树的生成
 treeNode *n50 = node(50);
//树初始化成功
bintree *binTree2 = tree(n50);
//有序插入节点，形成有序二叉树
        insertRecursionR(38, n50);
        insertRecursionR(70, n50);
        insertRecursionR(28, n50);
        insertRecursionR(40, n50);
        insertRecursionR(18, n50);
        insertRecursionR(30, n50);
        insertRecursionR(39, n50);
        insertRecursionR(41, n50);
        insertRecursionR(42, n50);
        insertRecursionR(56, n50);
        insertRecursionR(78, n50);
        insertRecursionR(100, n50);
        printf("  层序遍历 队列方法：");
        layerOrder(binTree2);
        printf("先序遍历 递归：");
        preOrderTraversal(binTree2->root);
        //求最小值
        treeNode *minNode =FindMin(binTree2->root);
        printf("  最小值：%d  ",minNode->data);
        //求最大值
        treeNode *maxNode =FindMax(binTree2->root);
        printf("  最大值：%d  ",maxNode->data);
        treeNode *node =  Find(78, binTree2->root);
        if (node) {
                      printf(" 找到值：%d  ",node->data);
            }else{
                      printf("  没找到值  ");
            }
        deleteRecursion(70, binTree2->root);
        printf("  层序遍历 队列方法：");
         layerOrder(binTree2);

打印结果为：