2.4学习总结

洛谷1305代码

#include<stdio.h>
#include<stdlib.h>
struct treenode {
	char val;
	struct treenode* left;
	struct treenode* right;
};
struct treenode* createnode(char val) {
	struct treenode* node = (struct treenode*)malloc(sizeof(struct treenode));
	node->val = val;
	node->left = NULL;
	node->right = NULL;
	return node;
}
struct treenode* buildtree(int n, char nodes[][4]) {
	struct treenode* root = NULL;
	struct treenode* nodesarray[26] = { NULL };
	for (int i = 0;i < n;i++) {
		char val = nodes[i][0];
		char left = nodes[i][1];
		char right = nodes[i][2];
		if (nodesarray[val - 'a'] == NULL) {
			nodesarray[val - 'a'] = createnode(val);
		}
		if (left != '*') {
			if (nodesarray[left - 'a'] == NULL) {
				nodesarray[left - 'a'] = createnode(left);
			}
			nodesarray[val - 'a']->right = nodesarray[right - 'a'];
		}
		if (i == 0) {
			root = nodesarray[val - 'a'];
		}
	}
	return root;
}
void preorderTraversal(struct treenode* root) {
	if (root == NULL) {
		return;
	}
	printf("%c", root->val);
	preorderTraversal(root->left);
	preorderTraversal(root->right);
}
int main() {
	int n;
	scanf("%d", & n);
	char nodes[n][4];
	for (int i = 0;i < n;i++) {
		scanf("%s", nodes[i]);
	}
	struct treenode* root = buildtree(n, nodes);
	preorderTraversal(root);
	printf("\n");
	return 0;
}

前序遍历方法（dfs）二叉树

struct MyStruct
{
	char l, r;
}tree[200];
void dfs(char pos)
{
	cout << pos;
	if (tree[pos].l != '*') dfs(tree[pos].l);
	if (tree[pos].r != '*') dfs(tree[pos].r);
}

前序遍历

void preorderTraversal(struct treenode* root) {
	if (root == NULL) {
		return;
	}
	printf("%c", root->val);
	preorderTraversal(root->left);
	preorderTraversal(root->right);
}

洛谷1160代码

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
    int id;
    struct Node* prev;
    struct Node* next;
} Node;
Node* createNode(int id) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->id = id;
    newNode->prev = NULL;
    newNode->next = NULL;
    return newNode;
}
//左插
void insertLeft(Node* target, Node* newNode) {
    newNode->next = target;
    newNode->prev = target->prev;
    if (target->prev != NULL) {
        target->prev->next = newNode;
    }
    target->prev = newNode;
}
//右插
void insertRight(Node* target, Node* newNode) {
    newNode->prev = target;
    newNode->next = target->next;
    if (target->next != NULL) {
        target->next->prev = newNode;
    }
    target->next = newNode;
}
//去掉
void removeNode(Node* node) {
    if (node->prev != NULL) {
        node->prev->next = node->next;
    }
    if (node->next != NULL) {
        node->next->prev = node->prev;
    }
    free(node);
}
int main() {
    int N, M;
    scanf("%d", &N);

    Node* head = createNode(1);
    Node* nodes[N+1];
    nodes[1] = head;

    for (int i = 2; i <= N; i++) {
        int k, p;
        scanf("%d %d", &k, &p);
        Node* newNode = createNode(i);
        nodes[i] = newNode;
        if (p == 0) {
            insertLeft(nodes[k], newNode);
        } else {
            insertRight(nodes[k], newNode);
        }
    }
    scanf("%d", &M);
    for (int i = 0; i < M; i++) {
        int x;
        scanf("%d", &x);
        if (nodes[x] != NULL) {
            removeNode(nodes[x]);
            nodes[x] = NULL;
        }
    }
    Node* current = head;
    while (current->prev != NULL) {
        current = current->prev;
    }

    while (current != NULL) {
        printf("%d ", current->id);
        current = current->next;
    }

    return 0;
}