2014

2014 二叉樹（鏈式存儲）

#include<iostream>
#include<bits/stdc++.h>
using namespace std;typedef struct Node{struct Node *left;struct Node *right;int high=0;double weight; 
}node;double sum=0;void visit(node *t){int lop=0;if(t->left != NULL){t->left->high = t->high+1;lop = 1;}if(t->right != NULL){t->right->high = t->high+1;lop = 1;}if(lop == 0){sum += t->weight * t->high;}
}void dfs(node *t){if(t != NULL){cout << t->weight << endl;visit(t);dfs(t->left);dfs(t->right);}
}node* buildnode(int w){node* tmp = (node *)malloc(sizeof(node));
//	tmp->high = 0;tmp->weight = w;tmp->left = tmp->right = NULL;return tmp;
}void first(node *t){if(t != NULL){//	visit(t);cout << t->weight << "  " << t->high << endl;first(t->left);first(t->right);}// also 
//	if(t == NULL)  return; 
//	//	visit(t);
//	cout << t->weight << endl;
//		
//	first(t->left);
//	
//	first(t->right);
//	
}int main(){node* n1 = buildnode(1);node* n2 = buildnode(2);node* n3 = buildnode(3);node* n4 = buildnode(4);node* n5 = buildnode(5);node* n6 = buildnode(6);node* n7 = buildnode(7);n1->left = n2;n1->right = n3; n2->left = n4;n2->right = n5;n3->right = n6;n4->right = n7;dfs(n1);cout << "sum = " <<  sum << endl; first(n1);return 0;
} 

2017

2015 單鏈表（帶頭結點）

#include<iostream>
#include<cstring>
using namespace std;typedef struct Node{int data;struct Node *next; 
}node,*list;const int N = 100010;
int a[N];
void func(Node *head){node *p;node *r;p = head;while(1){int x = p->next->data;if(x < 0) x = -1*x;if(a[x] == 0){a[x] = 1;p = p->next;}else{r = p->next;p->next = r->next;free(r);}if(p->next == NULL) break;}
}node* create(int n){node* p;p = (node*)malloc(sizeof(node));p->data = n;p->next = NULL;
}void func2(Node *head){node *p;p = head;while(p->next != NULL){cout << p->next->data << " ";p = p->next;}return;
}int main(){node *head;node *s1;node *s2;node *s3;node *s4;head = create(-1);s1 = create(2);s2 = create(2);s3 = create(1);s4 = create(1);head->next = s1;s1->next = s2;s2->next = s3;s3->next = s4;// bianlifunc2(head); func(head);cout << endl;func2(head);return 0;
}

2017

2017 二叉樹中序遍歷

#include<iostream>using namespace std;typedef struct Node{char data;struct Node *left, *right;
}node;void visit(node *t){cout << t->data << " ";
}void bianli(node *t,int h){if(t != NULL){// 根 和 葉子 if(h > 0 && t->left!=NULL && t->right!=NULL) cout << "(";bianli(t->left,h+1);visit(t);bianli(t->right,h+1);if(h > 0 && t->left!=NULL && t->right!=NULL) cout << ")";}	
}node* create(char data){node* s;s = (node *)malloc(sizeof(node));s->data = data;s->right = NULL;s->left = NULL;return s;
}int main(){node *s1 = create('*');node *s2 = create('+');node *s3 = create('4');node *s4 = create('-');node *s5 = create('3');node *s6 = create('2');node *s7 = create('1');s1->left = s2;s1->right = s3;s2->left = s4;s2->right = s5;s4->right = s6;s4->left = s7;bianli(s1,0);return 0;	
} 

2019

2019 鏈表（快慢指針、反轉鏈表、鏈表重排）

#include<iostream>
#include<cstring>using namespace std;typedef struct Node{int data;Node *next;
}node;node* create(int data){node *n = (node *)malloc(sizeof(node));n->data = data;n->next = NULL;return n;
}void print(node *head){node* p;p = head;while(p->next != NULL){cout << p->next->data << " ";p = p->next;}cout << endl;
}void reverse(node *head){node *p;p = head->next;head->next = NULL;while(p != NULL){node *t = p->next;p->next = head->next;head->next = p;p = t;}
}void change(node *head){node *q, *p;// 1. 快慢指針 來確定中間位置q = head;p = head;while(q->next != NULL){p = p->next;q = q->next;if(q->next != NULL) q = q->next;} //	cout << "## " << q->data << " " << p->data << endl;// 2. 反轉鏈表// 頭插法 頭就是 preverse(p);//	cout << "p:  " << p->data << endl;//	node *h;
//	h = p;
//	h->next = NULL;
//	p = p->next;
//	while(p!=NULL){
//		node *t = p->next;
//		p->next = head->next;
//		h->next = p;
//		p = t;
//	}//	cout << "T: ";
//	print(head);// 3. 按題目要求進行插入node *f = head->next;node *r = p->next;p->next = NULL;//	r = r->next;
//	if(r->next == NULL)  cout << "!!!!!!!!!!!!!!!!!!";
//	cout << "r:  " << r->data << endl;while(r!=NULL){node* t2 = r->next;r->next = f->next;f->next = r;f = r->next; r = t2;} }int main(){node* head = create(-1);node* n1 = create(1);node* n2 = create(2);node* n3 = create(3);node* n4 = create(4);node* n5 = create(5);head->next = n1;n1->next = n2;n2->next = n3;n3->next = n4;n4->next = n5;n5->next = NULL;// n1->n2->n3->n4->n5print(head);//	reverse(head);//	print(head);change(head);print(head);return 0;
}

模擬題1

輸出二叉樹任意節點到根節點的路徑（鏈式存儲）

#include<iostream>
#include<cstring>using namespace std;typedef struct Node{int num;struct Node *left, *right;struct Node *front;
}node;void visit(node *t){if(t->left != NULL){t->left->front = t;}if(t->right != NULL){t->right->front = t;}
}void first(node* t){if(t!=NULL){visit(t);cout << t->num << endl;first(t->left);first(t->right);}
}void print(node *t){cout << "the route is ";while(1){cout << t->num << " ";t = t->front;if(t == NULL) break;}cout << endl;
}node* create(int num){node* s;s = (node *)malloc(sizeof(node));s->num = num;s->front = NULL;s->right = NULL;s->left = NULL;return s;
}int main(){node *s1 = create(1);node *s2 = create(2);node *s3 = create(3);node *s4 = create(4);node *s5 = create(5);node *s6 = create(6);node *s7 = create(7);s1->left = s2;s1->right = s3;s2->left = s4;s2->right = s5;s3->left = s6;s4->left = s7;first(s1);print(s7);return 0;	
}