AVL树的初步了解

平衡二叉树(AVL树)空树或者,任意左右子树高度差的绝对值不超过1,|BF(1)|<=1平衡二叉树调整因“破坏者”的插入导致某个结点(发现者)不平衡所以需要相对应的旋转,才能达到平衡。右单旋转​ 不平衡的“发现者” 是1号,破坏平衡结点的是3号。3号在“发现者”的左子树的左边,因LL插入,需要(右单旋转)左单旋转“发现者” 为1号 “破坏者”为3号,3号在“发现者”的右子树的右边。因RR插入,需要(左单旋转)LR旋转 “破坏者”在“发现者”的左子树的右边所以需要LR旋转(先左后右旋转)。RL旋转 “破坏者”在“发现者”的右子树的左边所以需要RL旋转(先右后左旋转)。核心代码清单

二叉树非递归遍历

需要注意非递归遍历需要借助栈这个数据结构来完成先序步骤把结点 访问和压入栈。把指针指向左子结点。重复第1步直到没有左子结点为止。再从栈 顶部拿出结点, 把指针指向此结点的右子结点。重复第1步骤 直到栈空或没有结点。代码void PreOrder(struct TreeNode* root) { stack<TreeNode*> S; struct TreeNode* T = root; while (!S.empty()||T) { while (T) { cout << T->val << " "; S.push(T); T = T->left; } if (!S.empty()) { T = S.top(); S.pop(); T = T...

二叉树的性质和遍历

二叉树特征一个二叉树第i层的最大结点数为 2^i-1,当i>=1时深度为K的二叉树最大节结点总数为: (2^k)-1 ,当k>=1时二叉树遍历方法​ 先序 (根 --> 左子树-->右子树)​ 中序 (左子树 --> 根-->右子树)​ 后序 (左子树 --> 右子树-->根)​ 层次遍历 (从上到下、从左到右)序号关系当根节点 i>1时,子节点序号等于 左(i 2) 右(i 2)+1,而父节点的序号等于(i/2)取整存储结构代码typedef struct TreeNode { char val; /*左右节点*/ struct TreeNode *left; struct TreeNode *right; };二叉树遍历代码先序遍历void PreOrder(struct TreeNode* root) { if (root == NULL) { return; } printf("%c", root->...

1215:迷宫

题目描述一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。输入第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的 2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0 输出YES NO 代码:#include<iostream> using name...

扫雷游戏

时间限制:C/C++ 1秒,其他语言2秒空间限制:C/C++ 262144K,其他语言524288K64bit IO Format: %lld题目描述扫雷游戏是一款十分经典的单机小游戏。在n行m列的雷区中有一些格子含有地雷(称之为地雷格),其他格子不含地雷(称之为非地雷格)。玩家翻开一个非地雷格时,该格将会出现一个数字——提示周围格子中有多少个是地雷格。游戏的目标是在不翻出任何地雷格的条件下,找出所有的非地雷格。现在给出n行m列的雷区中的地雷分布,要求计算出每个非地雷格周围的地雷格数。注:一个格子的周围格子包括其上、下、左、右、左上、右上、左下、右下八个方向上与之直接相邻的格子。输入描述:输入文件第一行是用一个空格隔开的两个整数n和m,分别表示雷区的行数和列数。接下来n行,每行m个字符,描述了雷区中的地雷分布情况。字符’*’表示相应格子是地雷格,字符’?’表示相应格子是非地雷格。相邻字符之间无分隔符。输出描述:输出文件包含n行,每行m个字符,描述整个雷区。用’*’表示地雷格,用周围的地雷个数表示非地雷格。相邻字符之间无分隔符。示例1输入3 3 *?? ??? ?*? 输出*10 ...