crm管理系统哪个好用_郴州微游网络科技有限公司_seo任务_推广点击器

数据结构中的树：概念、操作与实战

第一部分树分类及常见形式

树是一种非线性的分层数据结构，由节点和边组成。以下是常见的树结构分类：

1. 二叉树

每个节点最多有两个子节点的树结构

typedef struct TreeNode {int val;struct TreeNode *left;struct TreeNode *right;
} TreeNode;

2. 二叉搜索树(BST)

左子树所有节点值小于根节点，右子树所有节点值大于根节点

// 同二叉树结构，但遵循BST规则

3. 平衡二叉树(AVL树)

任何节点的两个子树高度差不超过1的BST

typedef struct AVLNode {int val;int height;struct AVLNode *left;struct AVLNode *right;
} AVLNode;

4. 红黑树

自平衡二叉搜索树，通过对节点着色保持平衡

typedef struct RBNode {int val;enum {RED, BLACK} color;struct RBNode *left;struct RBNode *right;struct RBNode *parent;
} RBNode;

5. B树/B+树

多路平衡查找树，用于数据库和文件系统

#define M 4 // B树的阶typedef struct BTreeNode {int keys[M-1];struct BTreeNode *children[M];int numKeys;int isLeaf;
} BTreeNode;

6. 堆（完全二叉树形式）

父节点值总是大于/小于子节点值

typedef struct {int *arr;int capacity;int size;
} MaxHeap;

7. Trie树（前缀树）

用于字符串检索的多叉树结构

#define ALPHABET_SIZE 26typedef struct TrieNode {struct TrieNode *children[ALPHABET_SIZE];int isEndOfWord;
} TrieNode;

第二部分树常见操作

1. 树的遍历

// 递归前序遍历
void preorder(TreeNode *root) {if(root == NULL) return;printf("%d ", root->val);preorder(root->left);preorder(root->right);
}// 迭代中序遍历（使用栈）
void inorder(TreeNode *root) {TreeNode *stack[100];int top = -1;TreeNode *curr = root;while(curr != NULL || top != -1) {while(curr != NULL) {stack[++top] = curr;curr = curr->left;}curr = stack[top--];printf("%d ", curr->val);curr = curr->right;}
}// 层序遍历（使用队列）
void levelOrder(TreeNode *root) {if(root == NULL) return;TreeNode *queue[100];int front = 0, rear = 0;queue[rear++] = root;while(front < rear) {TreeNode *node = queue[front++];printf("%d ", node->val);if(node->left) queue[rear++] = node->left;if(node->right) queue[rear++] = node->right;}
}

2. 二叉搜索树操作

// BST插入
TreeNode* insertBST(TreeNode *root, int val) {if(root == NULL) {TreeNode *node = (TreeNode*)malloc(sizeof(TreeNode));node->val = val;node->left = node->right = NULL;return node;}if(val < root->val) {root->left = insertBST(root->left, val);} else {root->right = insertBST(root->right, val);}return root;
}// BST查找
TreeNode* searchBST(TreeNode *root, int val) {if(root == NULL || root->val == val) {return root;}return val < root->val ? searchBST(root->left, val) : searchBST(root->right, val);
}

3. AVL树平衡操作

// 获取节点高度
int height(AVLNode *node) {return node == NULL ? 0 : node->height;
}// 右旋转
AVLNode* rightRotate(AVLNode *y) {AVLNode *x = y->left;AVLNode *T2 = x->right;x->right = y;y->left = T2;y->height = 1 + max(height(y->left), height(y->right));x->height = 1 + max(height(x->left), height(x->right));return x;
}// 左旋转
AVLNode* leftRotate(AVLNode *x) {AVLNode *y = x->right;AVLNode *T2 = y->left;y->left = x;x->right = T2;x->height = 1 + max(height(x->left), height(x->right));y->height = 1 + max(height(y->left), height(y->right));return y;
}

4. 堆操作

// 堆插入
void insertMaxHeap(MaxHeap *heap, int val) {if(heap->size == heap->capacity) {printf("Heap is full\n");return;}int i = heap->size++;heap->arr[i] = val;// 上浮调整while(i != 0 && heap->arr[parent(i)] < heap->arr[i]) {swap(&heap->arr[i], &heap->arr[parent(i)]);i = parent(i);}
}// 堆删除最大元素
int extractMax(MaxHeap *heap) {if(heap->size <= 0) return INT_MIN;if(heap->size == 1) return heap->arr[--heap->size];int root = heap->arr[0];heap->arr[0] = heap->arr[--heap->size];maxHeapify(heap, 0);return root;
}

5. Trie树操作

// Trie插入
void insertTrie(TrieNode *root, const char *word) {TrieNode *curr = root;for(int i = 0; word[i] != '\0'; i++) {int index = word[i] - 'a';if(!curr->children[index]) {curr->children[index] = createTrieNode();}curr = curr->children[index];}curr->isEndOfWord = 1;
}// Trie搜索
int searchTrie(TrieNode *root, const char *word) {TrieNode *curr = root;for(int i = 0; word[i] != '\0'; i++) {int index = word[i] - 'a';if(!curr->children[index]) {return 0;}curr = curr->children[index];}return curr != NULL && curr->isEndOfWord;
}

第三部分树编程题例子

1. 二叉树的最大深度

int maxDepth(TreeNode* root) {if(root == NULL) return 0;int left = maxDepth(root->left);int right = maxDepth(root->right);return 1 + (left > right ? left : right);
}

2. 验证二叉搜索树

int isValidBSTHelper(TreeNode* root, long min, long max) {if(root == NULL) return 1;if(root->val <= min || root->val >= max) return 0;return isValidBSTHelper(root->left, min, root->val) && isValidBSTHelper(root->right, root->val, max);
}int isValidBST(TreeNode* root) {return isValidBSTHelper(root, LONG_MIN, LONG_MAX);
}

3. 二叉树的最近公共祖先

TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {if(root == NULL || root == p || root == q) return root;TreeNode *left = lowestCommonAncestor(root->left, p, q);TreeNode *right = lowestCommonAncestor(root->right, p, q);if(left && right) return root;return left ? left : right;
}

4. 二叉树层序遍历（返回二维数组）

int** levelOrder(TreeNode* root, int* returnSize, int** returnColumnSizes) {if(root == NULL) {*returnSize = 0;return NULL;}TreeNode *queue[2000];int front = 0, rear = 0;queue[rear++] = root;int **result = (int**)malloc(1000 * sizeof(int*));*returnColumnSizes = (int*)malloc(1000 * sizeof(int));*returnSize = 0;while(front < rear) {int levelSize = rear - front;(*returnColumnSizes)[*returnSize] = levelSize;result[*returnSize] = (int*)malloc(levelSize * sizeof(int));for(int i = 0; i < levelSize; i++) {TreeNode *node = queue[front++];result[*returnSize][i] = node->val;if(node->left) queue[rear++] = node->left;if(node->right) queue[rear++] = node->right;}(*returnSize)++;}return result;
}

5. 从前序与中序遍历序列构造二叉树

TreeNode* buildTreeHelper(int* preorder, int preStart, int preEnd, int* inorder, int inStart, int inEnd, int* inorderMap) {if(preStart > preEnd || inStart > inEnd) return NULL;TreeNode *root = (TreeNode*)malloc(sizeof(TreeNode));root->val = preorder[preStart];int inRoot = inorderMap[root->val];int numsLeft = inRoot - inStart;root->left = buildTreeHelper(preorder, preStart+1, preStart+numsLeft,inorder, inStart, inRoot-1, inorderMap);root->right = buildTreeHelper(preorder, preStart+numsLeft+1, preEnd,inorder, inRoot+1, inEnd, inorderMap);return root;
}TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize) {int inorderMap[6001] = {0}; // 假设节点值范围在-3000到3000for(int i = 0; i < inorderSize; i++) {inorderMap[inorder[i]+3000] = i; // 处理负值}return buildTreeHelper(preorder, 0, preorderSize-1, inorder, 0, inorderSize-1, inorderMap);
}

6. 实现Trie（前缀树）

typedef struct Trie {struct Trie *children[26];int isEnd;
} Trie;Trie* trieCreate() {Trie *node = (Trie*)malloc(sizeof(Trie));for(int i = 0; i < 26; i++) {node->children[i] = NULL;}node->isEnd = 0;return node;
}void trieInsert(Trie* obj, char * word) {Trie *curr = obj;for(int i = 0; word[i]; i++) {int index = word[i] - 'a';if(!curr->children[index]) {curr->children[index] = trieCreate();}curr = curr->children[index];}curr->isEnd = 1;
}int trieSearch(Trie* obj, char * word) {Trie *curr = obj;for(int i = 0; word[i]; i++) {int index = word[i] - 'a';if(!curr->children[index]) {return 0;}curr = curr->children[index];}return curr->isEnd;
}int trieStartsWith(Trie* obj, char * prefix) {Trie *curr = obj;for(int i = 0; prefix[i]; i++) {int index = prefix[i] - 'a';if(!curr->children[index]) {return 0;}curr = curr->children[index];}return 1;
}void trieFree(Trie* obj) {if(!obj) return;for(int i = 0; i < 26; i++) {if(obj->children[i]) {trieFree(obj->children[i]);}}free(obj);
}