#1.创建单链表

#include<iostream>
using namespace std;
typedef int Elemtype;
typedef struct n {
	Elemtype data;
	struct n* next;

}Node,*Linklist;

void create(Linklist &L) {
	Node* p = L;
	Elemtype data;
	while (true) {
		cin >> data;
		if (data == -1)
			break;
		else {
			p->next = new Node;
			p = p->next;
			p->data = data;
			p->next = NULL;
		}
	}

}

void search(Linklist& L, Elemtype i) {
	Node* p = L->next;
	int n = 1;
	while (p) {
		if (p->data == i)
			cout << n<<" ";
		
		n++;
		p = p->next;
	}

}

void insert(Linklist& L, int i, Elemtype data) {
	Node* p = L;
	for (int m = 0; m < i - 1; m++)
		p = p->next;
	Node* node = new Node;
	node->data = data;
	node->next = p->next;
	p->next = node;

}

void delete_(Linklist& L, Elemtype i) {
	Node* p = L;
	while (p->next) {
		if (p->next->data == i) {
			Node* pr = p->next;
			p->next = p->next->next;
			delete pr;
		}
		else
			p = p->next;
	}
}

void display(Linklist& L) {
	Node* p = L->next;
	while (p) {
		cout << p->data<<" ";
		p = p->next;
	}
}

int main() {
	Linklist L;
	L = new Node;
	L->data = 0;
	L->next = NULL;

	create(L);
	search(L,8);
	insert(L,3,8);
	delete_(L, 8);
	display(L);


}

#2.链栈

#include<iostream>
using namespace std;

typedef struct node {
	int data;
	struct node* next;
}Node,*Stack;

//入栈
void put(Stack &S) {
	int data;
	while (1) {
		cin >> data;
		if (data == -1)
			break;
		Node* p = new Node;
		p->data = data;
		p->next = S;
		S = p;
	}
}

//出栈
void out(Stack &S) {
	Node *pr,* p = S;
	while (p)
	{
		pr = p;
		cout << p->data<<" ";
		S = p->next;
		p = p->next;
		delete(pr);
	}
}

//遍历输出栈存储数据
void display(Stack& S) {
	Node* p = S;
	while (p) {
		cout << p->data<<" ";
		p = p->next;
	}
}

int main() {
	Stack S=NULL;
	put(S);
	out(S);
	
	
}

#3.循环队列

#include<iostream>
#define MAX 10
using namespace std;

typedef struct node {
	int *queue;
	int front;
	int rear;
}Queue;

//入队
void push(Queue& Q) {
	int data;
	for (int i = 0; i < MAX; i++) {
		cin >> data;
		if (Q.front == (Q.rear + 1) % MAX) {
			cout << "队列已满";
			return;
		}
		Q.queue[Q.rear] = data;
		Q.rear = (Q.rear + 1) % MAX;
	} 

}
//出队
void gettop(Queue& Q) {
	while (Q.front!=Q.rear) {
		cout << Q.queue[Q.front];
		Q.front = (Q.front + 1) % MAX;
		
	}
}

int main() {
	Queue Q;
	Q.queue = new int[MAX];
	Q.front = Q.rear = 0;
	push(Q);
	gettop(Q);
}

#4.链队

#include<iostream>
using namespace std;

typedef struct node {
	int data;
	struct node* next;
}*Queueptr,Node;

typedef struct {
	Queueptr front;
	Queueptr rear;
}LinkQueue;

//入队
void push(LinkQueue& Q) {
	int data;
	while (1) {
		cin >> data;
		if (data == -1)
			return;
		Node* node = new Node;
		node->data = data;
		node->next = NULL;
		Q.rear->next = node;
		Q.rear = node;
	}
}

//出队
void pop(LinkQueue &Q) {
	Node* p = NULL;
	while (Q.front != Q.rear) {
		p = Q.front->next;
		cout << p->data;
		Q.front->next = p->next;
		if (p == Q.rear) //若尾指针指向的为最后将删除的结点，下一次队列为空
			Q.rear = Q.front;
		delete(p);
	}
}

int main() {
	LinkQueue Q;
	Q.front = Q.rear = new Node;
	push(Q);
	pop(Q);
}

#5.二叉树的遍历

#include<iostream>
using namespace std;

typedef char ElemType;
typedef  struct  BiNode
{
    ElemType  data;
    struct  BiNode* lchild, * rchild;
}BiNode, * BiTree;

void Add(BiTree& T) {
    ElemType data;
    cin >> data;
    if (data == '#') {
        T = NULL;
        
    }
    else {
        T = new BiNode;
        T->data = data;
        Add(T->lchild);
        Add(T->rchild);

    }

}

void preorder(BiTree& T) {
    if (!T)
        return;
    cout << T->data;
    preorder(T ->lchild);
    preorder(T ->rchild);
}

void inorder(BiTree& T) {
    if (!T)
        return;
    inorder(T->lchild);
    cout << T->data;
    inorder(T->rchild);
}

void postorder(BiTree& T) {
    if (!T)
        return;
    postorder(T->lchild);
    postorder(T->rchild);
    cout << T->data;
}

int depth(BiTree& T,int count) {
    if (!T)
        return count;
    return depth(T->lchild, count + 1)>depth(T->rchild,count+1)? depth(T->lchild, count + 1) :depth(T->rchild, count + 1);
}

int leaf(BiTree& T, int count) {
    if (!T)
        return count;
    if (!T->lchild && !T->rchild)
        return count + 1;
    count=leaf(T->lchild, count);
    count=leaf(T->rchild, count);
}

int main() {
    BiTree T;
    Add(T);
    cout << "PreOrder:";
    preorder(T); 
    cout << "\n";
    cout << "InOrder:";
    inorder(T); 
    cout << "\n";
    cout << "PostOrder:";
    postorder(T);
    cout << "\n";
    cout << "Depth:" << depth(T, 0);
    cout << "\n";
    cout << "Leaf:" << leaf(T, 0);
}