首页 > 编程语言 >数据结构与算法---------4

数据结构与算法---------4

时间：2024-02-18 22:55:52浏览次数：27  
标签：return int 元素 ptrS Queue 队列 算法 数据结构 ---------

树

树是一种一对多的结构，它在一些有层次结构的系统中使用非常多，例如政府系统中，它们的关系就可以用树来表示。

 当树中没有节点时，称为空树。

树中有一个称为"根"特殊节点。

其中每一颗子树不相交也就是没有环。

除了根节点之外的所有节点有且只有一个父节点。

一颗树有N个节点，那么就有N - 1条边，因为只有根节点没有边，所以就只有根节点没有边，根据上一个结论

节点的度:节点的子树个数

树的度:树中所有节点中度最大的度数

叶节点:度为0的节点

兄弟节点:具有同一个父节点的节点就是兄弟节点

路径长度:经过的边的个数

节点的层次:规定根节点在第一层,其他节点的层数时它父节点的层数加一

树的高度:树中所有节点中，层次最大的

二叉树

二叉树是有左右子树之分的，分为左子树和右子树

特殊二叉树

斜二叉树

所有节点都只有左子树，就是一颗左斜二叉树，所有节点都只有右字树，就是一颗右斜二叉树。这些树就是斜二叉树。也就是我们线性表中的(链表)。

左斜二叉树

 

右斜二叉树

 

满二叉树(完美二叉树)

 在一颗二叉树中，如果所有分支节点都有左子树和右子树，并且所有叶子节点都在同一层，那么这样的二叉树就是一颗满二叉树(完美二叉树)。

完全二叉树

对于一颗具有n个节点的二叉树按层序编号，如果编号为i(1 <= i <= n)的节点与同样深度的满二叉树的编号相同那么这颗树就是一颗完全二叉树。

二叉树的性质

  1. 二叉树的第i层最多有2i - 1个节点
  2. 深度为k的二叉树节点个数不会超过2k - 1个节点
  3. 对于任意一个二叉树，如果叶子节点为n0,有两个孩子的节点数为n2,则n0 = n2 + 1。证明:设有一个孩子数的节点为n1,对于有n个节点的二叉树来说，一共有n - 1条边。所有总边数等于(n1 + n2 + n0 ) - 1= 0 * n0 + 1 * n1 + 2 * n2，经过移项后发现这个等式成立。
  4. 有n个节点的完全二叉树的深度为[log2n] + 1

二叉树的遍历

二叉树的遍历本质就是让一个二维的结构改变成一个一维的线性序列。

前序遍历

力扣题目链接

前序遍历就是先访问根节点，再访问左子树，最后访问右子树。

代码实现

递归实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define pr printf
#define ERROR -1 

typedef int ELEMENT;//设置队列存放的元素

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Queue CreateQueue(int n);//创建一个大小为n的队列 
bool isFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item从队列尾部加入 
bool empty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//把队列头的元素出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int size(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct TreeNode *Tree;

void pre(Tree t, Queue q) {//前序遍历
    if (t == NULL) {
        return ;
    }

    addQ(q, t -> val);//把二叉树的节点的值入队，即int类型的值，添加到队列里面去
    pre(t -> left, q);
    pre(t -> right, q);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    Queue q = CreateQueue(100);//创建一个最大能容纳100个元素的队列

    pre(root, q);//前序遍历二叉树

    int *ans = (int*)malloc(sizeof(int) * size(q));//开辟一个大小为队列元素个数的数组
    //因为队列中有多少个人元素就代表着二叉树有多少个节点
    int i = 0;//从零开始给数组赋值

    *returnSize = size(q);//返回的大小就是队列的元素个数

    while(!empty(q)) {//如果队列不为空，就让队列的元素一直出队
        ans[i++] = deleteQ(q);
    }

    FreeQueue(q);//释放队列的空间

    return ans;//返回二叉树的节点的值的数组
}
Queue CreateQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool empty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (empty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
ELEMENT tail(Queue q)
{
	if (empty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int size(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

非递归实现

注意是先压入根节点，再压入右子树入栈，最后压入左子树，因为栈是先进后出，如果先压入根节点，再压入左子树，最后压入右子树，那么就不是先序遍历了。而是根右左了。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define pr printf
#define ERROR -1//返回-1代表出错 

typedef struct TreeNode* ELEMENT;//元素类型为存放二叉树的节点的指针，抽象的艺术 

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;
}SNode,*Stack;

typedef struct queue {
	int *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Stack createStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isStackFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool isStackEmpty(Stack ptrS);//判断栈是不是空栈 
int stackSize(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, int item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
int deleteQ(Queue q);//把队列头的元素出队 
int head(Queue q);//取出队头的元素但不出队 
int tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct TreeNode* Tree;

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    if (root == NULL) {//如果根节点为空直接返回NULL
        *returnSize = 0;//让返回的大小为0，因为二叉树中没有节点
        return NULL;
    }

    Stack s = createStack(100);//创建一个大小为100的栈
    Queue q = createQueue(100);//创建一个大小为100的队列

    push(s, root);//把根节点压入到栈里面去

    while(!isStackEmpty(s)) {//只要栈不为空
        Tree cur = pop(s);//让一个指针指向栈顶弹出来的元素
        addQ(q, cur -> val);//把栈顶弹出来的节点的值放入队列

        if (cur -> right) {//如果栈顶节点有右孩子
            push(s, cur -> right);//把栈顶节点的右孩子入栈
        }
        if (cur -> left) {//如果栈顶节点有左孩子
            push(s, cur -> left);//把栈顶节点的左孩子入栈
        }
    }

    *returnSize = queueSize(q);//返回的大小就是队列元素的个数

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));//开辟一个有队列元素个数的数组的大小
    int i = 0;//从0开始给数组赋值

    while(!isQueueEmpty(q)) {//只要队列不为空
        ans[i++] = deleteQ(q);//把队列头的元素赋值给ans数组
    }

    FreeQueue(q);
    FreeStack(s);

    return ans;//返回ans数组
}

Stack createStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isStackFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackEmpty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool isStackEmpty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int stackSize(Stack ptrS)
{
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (isStackEmpty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);
}

Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(int) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, int item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
int deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	int ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
int head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
int tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

中序遍历

中序遍历就是先访问左子树，再访问根节点，最后访问右子树。

递归实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
 #define ERROR -1
 typedef struct TreeNode* BinTree;
 typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//把队列头的元素出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

void inOrderBinTree(BinTree t, Queue q)
{
	if (t == NULL) {
		return ;
	}

	inOrderBinTree(t -> left, q);
	addQ(q, t -> val);
	inOrderBinTree(t -> right, q);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize){
    Queue q = createQueue(100);

    inOrderBinTree(root, q);

    *returnSize = queueSize(q);

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));
    int len = 0;

    while(!isQueueEmpty(q)) {
        ans[len++] = deleteQ(q);
    }

    FreeQueue(q);

    return ans;
}
Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
ELEMENT tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

非递归实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define pr printf
 #define ERROR -1
 typedef struct TreeNode* BinTree;
 typedef BinTree ELEMENT;

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;//最大能够存放的元素个数 
}SNode,*Stack;

typedef struct queue {
	int *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Stack createStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isStackFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool isStackEmpty(Stack ptrS);//判断栈是不是空栈 
int stackSize(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, int item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
int deleteQ(Queue q);//把队列头的元素出队 
int head(Queue q);//取出队头的元素但不出队 
int tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

int* inorderTraversal(struct TreeNode* root, int* returnSize){ 
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    Queue q = createQueue(100);
    Stack s = createStack(100);

    while(!isStackEmpty(s) || root) {
        while(root) {// 一直压入左边的节点
            push(s, root);
            root = root -> left;
        }
        root = pop(s);//从上面的循环出来肯定是root为空，所以弹出栈顶的节点，也就是它的父亲
        addQ(q, root -> val);//让栈顶节点的值入队
        root = root -> right;//去右子树，重复上面的步骤
    }

    *returnSize = queueSize(q);

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));
    int len = 0;

    while(!isQueueEmpty(q)) {
        ans[len++] = deleteQ(q);
    }

    FreeQueue(q);
    FreeStack(s);

    return ans;
}
Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (int*)malloc(sizeof(int) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, int item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
int deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	int ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
int head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
int tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}
Stack createStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isStackFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackEmpty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool isStackEmpty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int stackSize(Stack ptrS)
{
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (isStackEmpty(ptrS)) {// 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

后序遍历

后序遍历就是先访问左子树，再访问右子树，最后访问根节点。

递归实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define ERROR -1 

typedef int ELEMENT;

typedef struct queue {
	ELEMENT *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, ELEMENT item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
ELEMENT deleteQ(Queue q);//把队列头的元素出队 
ELEMENT head(Queue q);//取出队头的元素但不出队 
ELEMENT tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct TreeNode* BinTree;

void postOrderBinTree(BinTree t, Queue q)
{
	if (t == NULL) {
		return ;
	}

	postOrderBinTree(t -> left, q);
	postOrderBinTree(t -> right, q);
	addQ(q, t -> val);//让t的值入队
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    Queue q = createQueue(100);

    postOrderBinTree(root , q);//后序遍历二叉树，节点的值放入队列

    *returnSize = queueSize(q);//节点的个数等于队列的元素个数

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));//开辟二叉树节点个数的大小的数组
    int len = 0;//从0开始给数组赋值

    while(!isQueueEmpty(q)) {//只要队列不为空，就一直给队列赋值
        ans[len++] = deleteQ(q);
    }

    FreeQueue(q);//释放队列的空间

    return ans;//返回结果
}
Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, ELEMENT item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
ELEMENT deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return ERROR;
	}
	
	ELEMENT ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
ELEMENT head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
ELEMENT tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return ERROR;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

非递归实现

两个栈实现

解题思路
  1. 先序遍历是中左右，后序遍历是左右中，而改变一下先序的顺序就是中右左，再颠倒一下顺序，就是后序遍历的结果了。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define ERROR NULL 
#define pr printf
typedef struct TreeNode* ELEMENT;

typedef struct queue {
	int *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;//最大能够存放的元素个数 
}SNode,*Stack;

Stack createStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isStackFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool isStackEmpty(Stack ptrS);//判断栈是不是空栈 
int stackSize(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, int item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
int deleteQ(Queue q);//把队列头的元素出队 
int head(Queue q);//取出队头的元素但不出队 
int tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct TreeNode* BinTree;

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    Queue q = createQueue(100);
    Stack s = createStack(100);
    Stack res = createStack(100);

    push(s, root);

    while(!isStackEmpty(s)) {
        BinTree cur = pop(s);
        addQ(q, cur -> val);
        if (cur -> left) {
            push(s, cur -> left);
        }
        if (cur -> right) {
            push(s, cur -> right);
        }
    }

    *returnSize = queueSize(q);//节点的个数等于队列的元素个数

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));//开辟二叉树节点个数的大小的数组
    int len = 0;//从0开始给数组赋值

    while(!isQueueEmpty(q)) {//只要队列不为空，就一直给队列赋值
        push(res, deleteQ(q));
    }

    while(!isStackEmpty(res)) {
        ans[len++] = pop(res);
    }

    FreeQueue(q);//释放队列的空间
    FreeStack(s);
    FreeStack(res);

    return ans;//返回结果
}
Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (int*)malloc(sizeof(int) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, int item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
int deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return -1;
	}
	
	int ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
int head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return -1;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
int tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return -1;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

Stack createStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isStackFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackEmpty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool isStackEmpty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int stackSize(Stack ptrS)
{
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (isStackEmpty(ptrS)) {//如果栈是空的返回栈顶元素违法，返回一个特定的值，即ERROR 
		pr("栈已经空了\n");
		return ERROR; 
	}
	 
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

一个栈实现

解题思路
  1. 用一个指针标记访问过的节点，来避免重复访问。
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
#define ERROR NULL 
#define pr printf
typedef struct TreeNode* ELEMENT;

typedef struct queue {
	int *data;//存放元素 
	int head;//指向队头，也就是队列的第一个元素
	int tail;//指向下一个入队的位置，所以区间为[head, tail) 
	int size;//记录队列元素的个数 
	int MaxSize;//记录队列最大能同时存在的元素个数 
}QNode, *Queue;

typedef struct SNode {//定义栈的数据类型 
	ELEMENT *data;//使用数组实现，当然也可以用指针来开辟 
	int size;//栈中元素的个数 
	int MaxSize;//最大能够存放的元素个数 
}SNode,*Stack;

Stack createStack(int MaxSize);//创建一个最大大小为MaxSize的栈 
bool isStackFull(Stack ptrS);//判断栈是不是满了不能再存放了 
bool push(Stack ptrS, ELEMENT item);//把元素ITEM压入栈中 
ELEMENT pop(Stack ptrS);//把栈顶的元素弹出 
bool isStackEmpty(Stack ptrS);//判断栈是不是空栈 
int stackSize(Stack ptrS);//返回栈中元素的个数 
ELEMENT peek(Stack ptrS);//返回栈顶元素，但不弹出栈顶元素 
void FreeStack(Stack ptrS);//释放ptrS所指向的空间

Queue createQueue(int n);//创建一个大小为n的队列 
bool isQueueFull(Queue q);//判断队列是不是满了 
bool addQ(Queue q, int item);//把元素item从队列尾部加入 
bool isQueueEmpty(Queue q);//判断队列是不是空 
int deleteQ(Queue q);//把队列头的元素出队 
int head(Queue q);//取出队头的元素但不出队 
int tail(Queue q);//取出队尾的元素 
int queueSize(Queue q);//返回队列的元素个数 
void FreeQueue(Queue q);//释放队列

typedef struct TreeNode* BinTree;

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    Queue q = createQueue(100);
    Stack s = createStack(100);

    push(s, root);

    while(!isStackEmpty(s)) {
        BinTree cur = peek(s);//是当前访问的节点
        if (cur -> left != NULL //如果当前访问的节点有左子树
            && cur -> left != root //如果左子树没有被访问过
            && cur -> right != root) {//如果右子树被访问过了那么左子树也一定被访问过了，注意是左右中
                push(s, cur -> left);//让左孩子入栈
            }
        else if (cur -> right != NULL//有右子树
                && cur -> right != root) {//并且右子树没有被访问过
                    push(s, cur -> right);//让右孩子入栈
        }
        else {//1.没有左右孩子
            //2.左右子树被访问过了
            addQ(q, cur -> val);//让根节点入队
            root = pop(s);//弹出栈顶元素，也就是刚刚被入队列的节点
        }
    }

    *returnSize = queueSize(q);//节点的个数等于队列的元素个数

    int* ans = (int*)malloc(sizeof(int) * queueSize(q));//开辟二叉树节点个数的大小的数组
    int len = 0;//从0开始给数组赋值

    while(!isQueueEmpty(q)) {//只要队列不为空，就一直出队
        ans[len++] = deleteQ(q);
    }

    FreeQueue(q);
    FreeStack(s);

    return ans;//返回结果
}
Queue createQueue(int n)
{
	Queue t = (Queue)malloc(sizeof(QNode));//开辟一个队列 
	
	t -> data = (int*)malloc(sizeof(int) * n);//开辟空间来存放元素 
	t -> head = 0;//初始化队头 
	t -> tail = 0;//初始化队尾 
	t -> MaxSize = n;//初始化最大的大小
	t -> size = 0; 
	
	return t;//返回队列 
}
bool isQueueEmpty(Queue q)
{
	return q -> size == 0;//队列中没有元素，那么队列就是空的 
}
bool isQueueFull(Queue q)
{
	return q -> size == q -> MaxSize;//如果队列中元素个数等于最大能容纳的元素，那么就满了 
}
bool addQ(Queue q, int item)
{
	if (isQueueFull(q)) {//如果队列是满的，不能入队返回false 
		return false;
	}
	
	q -> data[q -> tail++] = item;//把元素item入队，因为是[head, tail)，所以自增在后面 
	q -> tail %= q -> MaxSize;//如果到了数组尾，回到下标0位置 
	q -> size++;//队列元素个数加一 
	
	return true;//能入队返回true 
}
int deleteQ(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，那么就不能出队，返回一个错误信息 
		return -1;
	}
	
	int ans = q -> data[q -> head++];
	
	q -> head %= q -> MaxSize;
	q -> size--;
	
	return ans;//不为空，返回队头，因为是[head, tail)的区间，所以自增在后面 
}
int head(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队头，是非法的 ，返回一个错误信息 
		return -1;
	}
	
	return q -> data[q -> head];//队列不为空，返回队列头的元素，返回队头元素不用特判，因为是[head, tail)，那么head必定是有效的下标，所以直接返回 
}
int tail(Queue q)
{
	if (isQueueEmpty(q)) {//如果队列为空，没有队尾，是非法的 ，返回一个错误信息 
		return -1;
	}
	
	return q -> tail - 1 < 0? q -> data[q -> MaxSize - 1]: q -> data[q -> tail - 1];//如果q -> tail - 1 < 0，代表是从MaxSize - 1下标过来的
	//然后tial变成0了，所以队尾元素实际在MaxSize - 1位置，其他位置不用特判 
	//因为是[head, tail)所以队尾元素在tail - 1位置，但因为是环形数组，可能是从MaxSize下标过来的
	//所以tail == 0是减一，数组越界了，因此要特判 
}
int queueSize(Queue q)
{
	return q -> size;//因为是[head, tail)的区间所以，直接相减就是队列的元素个数 
}
void FreeQueue(Queue q)
{
	free(q -> data);//先释放掉元素的内存空间 
	free(q);//再释放掉队列的内存空间 
}

Stack createStack(int MaxSize)
{
	Stack s = (Stack)malloc(sizeof(SNode));//开辟一个栈空间 
	
	s -> MaxSize = MaxSize; 
	s -> size = 0;//让栈的大小为0 
	s -> data = (ELEMENT*)malloc(sizeof(ELEMENT) * MaxSize);//开辟空间用来存放元素 
	
	return s;
}
bool isStackFull(Stack ptrS) { 
	return ptrS -> size == ptrS -> MaxSize;//如果栈中的元素等于栈能容纳的最大元素代表栈满了 
}

bool push(Stack ptrS, ELEMENT item) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackFull(ptrS)) {//如果栈满了就不能进行压栈了 
		return false; 
	}
	else {
		ptrS -> data[ptrS -> size++] = item;//就是先把item压入到栈里面去，size的大小再加一 
		return true;
	}
}

ELEMENT pop(Stack ptrS) {//用指针可以改变ptrS所指向的栈,因为要改变所对应的栈顶位置 
	if (isStackEmpty(ptrS)) {//如果栈为空，那么没有元素可以弹出，所以是犯法操作，返回一个特定的值 
		pr("栈已经空了\n");
		return ERROR; 
	}
	
	return ptrS -> data[--ptrS -> size];//是先减一，再弹出栈顶元素 
}

bool isStackEmpty(Stack ptrS) {
	return ptrS -> size == 0;//如果栈里面没有元素，那么栈就是空的
}

int stackSize(Stack ptrS)
{
	return ptrS -> size;//直接返回size
}
ELEMENT peek(Stack ptrS)
{
	if (isStackEmpty(ptrS)) {//如果栈是空的返回栈顶元素违法，返回一个特定的值，即ERROR 
		pr("栈已经空了\n");
		return ERROR; 
	}
	 
	ELEMENT ans = pop(ptrS);//使用pop函数 
	
	push(ptrS, ans);//因为已经弹出ans元素，所以在压入栈中 
	
	return ans;
}
void FreeStack(Stack ptrS)
{
	free(ptrS -> data);//先释放数据域的内存空间 
	free(ptrS);//再释放ptrS所指向的空间 
}

 

标签：return,int,元素,ptrS,Queue,队列,算法,数据结构,---------
From： https://www.cnblogs.com/lwj1239/p/17891040.html

相关文章

  • UVM Primer OOP前置部分（Chapter 4-5）
    资料：-UVMPrimer（英文原版）-UVMPrimer（中译版）前言：-本部分将包括UVMPrimer的第4章-第9章，仅整理OOP特性，不会涉及DUT及验证平台构建的相关内容。正文：本书的4-9章以一个动物园为例，讲述了OOP的不同特性，包括：-类-继承-多态-静态变量和方法-factory模式第四章：OOP概述OOP的优点......
  • 常用算法
    最长递增子序列长度给你一个整数数组nums，找到其中最长严格递增子序列的长度。 子序列 是由数组派生而来的序列，删除（或不删除）数组中的元素而不改变其余元素的顺序。例如，[3,6,2,7]是数组[0,3,1,6,2,2,7]的子序列。 解题思路：找出序列中最长子序列的长度1.动态规划法 ......
  • 2024-2-18 数论学习笔记
    zak讲数论专题，好难，听不懂，整理一下。借鉴了zak的课件。还没写完呐，还会更新的。目录一、线性筛二、Dirichlet前缀和三、整除分块四、莫比乌斯函数例一一、线性筛筛出\(n\)以内的所有质数。\(n≤10^8\)。直接埃氏筛是\(O(n\ln\lnn)\)的，但是一个合数会被筛多次，......
  • 二机制安装Kubernetes 1.29 高可用集群(5)--node节点配置
    1.1所有k8s-node节点安装cri-dockerrpm-ivhcri-dockerd-0.3.10-3.el8.x86_64.rpm1.2修改cri-docker启动文件，将默认的pod启动镜像地址修改为国内仓库源#vi/usr/lib/systemd/system/cri-docker.service将如下部分ExecStart=/usr/bin/cri-dockerd--container-runtime-en......
  • 二机制安装Kubernetes 1.29 高可用集群(4)--master节点配置
    1.1在k8s-master01上解压kubernetes可执行文件到/usr/local/bin目录tar-zxfkubernetes-server-linux-amd64.tar.gz--strip-components=3-C/usr/local/binkubernetes/server/bin/kube{let,ctl,-apiserver,-controller-manager,-scheduler,-proxy}注：--strip-components=3......
  • 二机制安装Kubernetes 1.29 高可用集群(3)--etcd集群配置
    1.在所有etcd节点解压安装包tar-zxfetcd-v3.5.12-linux-amd64.tar.gzcpetcd-v3.5.12-linux-amd64/etcd/usr/local/bin/&&cpetcd-v3.5.12-linux-amd64/etcdctl/usr/local/bin/#查看版本信息#etcdctlversionetcdctlversion:3.5.12APIversion:3.52.1在所有et......
  • 二机制安装Kubernetes 1.29 高可用集群(2)--haproxy节点配置
    1.1在所有haproxy节点安装haproxyyum-yinstallhaproxy1.2在所有haproxy节点创建haproxy配置文件cat>/etc/haproxy/haproxy.cfg<<EOFglobalmaxconn3000ulimit-n16384log127.0.0.1local0errstatstimeout30sde......
  • 二机制安装Kubernetes 1.29 高可用集群(1)--系统初始配置
    软件环境描述说明：OS：openEuler22.03LTSSP3kubernetes：1.29.2etcd：3.5.12calico：3.27.0cri-docker：0.3.10cfssl/cfssljson/cfssl-certinfo：1.64haproxy：2.2.6keepalived：2.2.4网段规划：物理主机：192.168.83.0/24      ServiceIP：10.66.0.0/16   PodIP：172.31.0.0......
  • 二机制安装Kubernetes 1.29 高可用集群(6)--calico网络组件和CoreDNS配置
    1.部署Calico网络组件1.1k8s-master节点上下载calico的创建文件下载地址：https://docs.tigera.io/calico/latest/getting-started/kubernetes/quickstartwgethttps://raw.githubusercontent.com/projectcalico/calico/v3.27.2/manifests/tigera-operator.yamlwgethttps://ra......
  • .NET周刊【2月第1期 2024-02-04】
    祝大家新年快乐，龙年大吉~国内文章C#/.NET/.NETCore优秀项目和框架2024年1月简报https://www.cnblogs.com/Can-daydayup/p/18000401本文介绍了公众号“追逐时光者”定期分享的C#/.NET/.NETCore优秀项目和框架，包括项目介绍、功能特点、使用方式和功能截图，并提供了源码地址。文......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99