国外教程 网站,广告设计公司薪酬体系设计方案,网站建设考核指标,肥城做网站tahmwlkj性质
树 上面的性质因为两个结点由一条边连成
结点数目越多#xff0c;算法复杂度越高 二叉树 结构 层次遍历
利用队列#xff0c;弹一个#xff0c;加N个#xff08;队列里弹出一个元素#xff0c;就把这个元素的所有孩子加进去#xff09;
具体来说#xff1a;指…性质
树 上面的性质因为两个结点由一条边连成
结点数目越多算法复杂度越高 二叉树 结构 层次遍历
利用队列弹一个加N个队列里弹出一个元素就把这个元素的所有孩子加进去
具体来说指针先指树根加入队列里后弹出队列把他的孩子都加入再弹再加
二叉查找树BST
比root小的放左边大的放右边
中序遍历会得到递增的有序序列
结构 // 定义二叉树节点的类
class Node {int val;Node lchild; // 左子树Node rchild; // 右子树// 构造函数初始化节点的值和子树Node(int val) {this.val val;this.lchild null;this.rchild null;}
}// 定义二叉搜索树的类
public class BST {private Node root; // 根节点private int size; // 节点个数// 构造函数初始化根节点为nullpublic BST() {this.root null;this.size 0;}// 判断二叉搜索树是否为空public boolean isEmpty() {return root null;}// 获取二叉搜索树的节点个数public int size() {return size;}// 清空二叉搜索树public void clear() {this.root null;}
} BST类里的方法
只要有修改了树的方法就会有返回节点每次返回都要更新树也就是node.rchild method(……
eg
删除需要改变树 if (val root.val) { root.lchild BSTDelete(root.lchild, val); } else if (val root.val) { root.rchild BSTDelete(root.rchild, val); } else {
添加需要改变树
if (val node.val) { node.lchild addNode(node.lchild, val); } else if (val node.val) { node.rchild addNode(node.rchild, val); }
搜索不需要改变树
} else if (val root.val) { return BSTSearch(root.lchild, val); } else { return BSTSearch(root.rchild, val);
添加
都添加成树叶不会在中间添加
// 添加节点的方法public void addNode(int val) {this.root addNode(this.root, val);this.size;}// 递归插入节点的方法private Node addNode(Node node, int val) {if (node null) {return new Node(val);}if (val node.val) {node.lchild addNode(node.lchild, val);} else if (val node.val) {node.rchild addNode(node.rchild, val);}return node;}删除
需要考虑三种情况
要删除的节点是叶子节点直接删除该节点。要删除的节点只有一个子节点用该子节点替换要删除的节点。要删除的节点有两个子节点找到该节点右子树中的最小节点即右子树中最左边的节点用这个最小节点的值替换要删除节点的值然后删除右子树中的最小节点。
public void BSTDelete(int val) {int originalSize this.size;this.root BSTDelete(this.root, val);
//因为会有树为空删除失败的情况所以不能直接size--if (originalSize this.size) {this.size--;}}public Node BSTDelete(Node root, int val) {if (root null) {return null;}
// 递归地在左子树中查找要删除的节点if (val root.val) {root.lchild BSTDelete(root.lchild, val);} else if (val root.val) {
// 递归地在右子树中查找要删除的节点root.rchild BSTDelete(root.rchild, val);}
// 找到要删除的节点else {// 情况 1: 要删除的节点没有子节点或只有一个子节点if (root.lchild null) {return root.rchild;} else if (root.rchild null) {return root.lchild;}// 情况 2: 要删除的节点有两个子节点// 找到右子树中的最小节点root.val Min(root.rchild);// 删除右子树中的最小节点root.rchild BSTDelete(root.rchild, root.val);}return root;}搜索
public Node BSTSearch(Node root, int val) {if (root null) {return null;}if (val root.val) {return root;} else if (val root.val) {return BSTSearch(root.lchild, val);} else {return BSTSearch(root.rchild, val);}}创建
这里没有维护size
public Node BSTBuild(int[] nums) {if (nums null || nums.length 0) {return null;}this.root new Node(nums[0]);for (int i 1; i nums.length; i) {addNode(nums[i]);}return this.root;}最大值
最右边的值最大
所以我们可以用一个指针p指向root而后一直移动指针直到p.right null
或者用递归 // 找最大,树的最右节点public int Max(){if (root null){return -100000;}TreeNode node findMax(root);return node.val;}private TreeNode findMax(TreeNode root){if(root.right null){return root;}return findMax(root.right);}
最小值
最左边的值最小
同上 // 找最小树的最左节点public int Min(){if (root null){return 100000;}TreeNode node findMin(root);return node.val;}private TreeNode findMin(TreeNode root){if(root.left null){return root;}return findMin(root.left);}
contains public boolean contains(TreeNode root, int val) {if(root null){return false;}if(root.val val){return true;} else if (root.val val) {return contains(root.left,val);} else {return contains(root.right,val);}}
某节点的前驱
指的是中序遍历后的那个序列某节点的前驱
就是比这个节点小的第一个节点
两种情况1、是其左子树的最大值 2、没有左子树则向上追溯直到某个祖先节点是右孩子那么这个祖先节点的父节点就是所求
某节点的后继
指的是中序遍历后的那个序列某节点的后继
就是比这个节点大的第一个节点
两种情况1、是其右子树的最小值 2、没有右子树则向上追溯直到某个祖先节点是左孩子那么这个祖先节点的父节点就是所求
某节点高度
递归得到左右子树的高度取较高的一方1就是某节点的高度
public int getHeight(Node node) {if (node null) return 0;int l getHeight(node.left);int r getHeight(node.right);return 1 Math.max(l, r);}
层次遍历
与树的层次遍历思路一致只不过孩子列表明确成了左右孩子
平衡二叉树AVL
左右子树的高度差平衡因子不大于1
AVL也是BST只不过多了一个高度差的特点所以基本操作实现思路按BST进行就行同时考虑不同点即可这里我们直接复用BST的操作
平衡因子
public int getHeight(Node node) {if (node null) return 0;return 1 Math.max(getHeight(node.lchild), getHeight(node.rchild));}
public int getBalanceFactor(Node node) {if (node null) {return 0;}int leftHeight getHeight(node.left);int rightHeight getHeight(node.right);return leftHeight - rightHeight;}
如果节点结构里有height则可以直接调用
但是如果这个节点是改变后的想要更新height就只能用上面的不能用下面这个方法记录过的height //获取当前节点的高度public int getHeight(Node node){if (nodenull){return 0;}return node.height;}//获取当前节点的平衡因子public int getBalanceFactor(Node node){if (nodenull){return 0;}return getHeight(node.left)-getHeight(node.right);}
添加
先复用BST的插入再调整平衡 // AVL 插入操作public void insert(int val) {root bstInsert(root, val);root balanceTree(root);}删除
// AVL 删除操作public void delete(int val) {root bstDelete(root, val);root balanceTree(root);}
调整平衡
判断不平衡类型的关键在于当前不平衡节点平衡因子为 -2 或 2 的节点及其子节点的平衡因子。
1. LL 型
判断条件当前不平衡节点的平衡因子为 2且其左子节点的平衡因子为 1。调整方法右旋
2. LR 型
判断条件当前不平衡节点的平衡因子为 2且其左子节点的平衡因子为 -1。调整方法左旋右旋
3. RR 型
判断条件当前不平衡节点的平衡因子为 -2且其右子节点的平衡因子为 -1。调整方法左旋
4. RL 型
判断条件当前不平衡节点的平衡因子为 -2且其右子节点的平衡因子为 1。调整方法右旋左旋
检查每个节点用递归来实现是否平衡不平衡就调整
/ 调整树的平衡public Node balanceTree(Node node) {if (node null) {return node;}node.height 1 Math.max(getHeight(node.left), getHeight(node.right));int balance getBalanceFactor(node);// LL 型if (balance 1 getBalanceFactor(node.left) 0) {return rightRotate(node);}// LR 型if (balance 1 getBalanceFactor(node.left) 0) {node.left leftRotate(node.left);return rightRotate(node);}// RR 型if (balance -1 getBalanceFactor(node.right) 0) {return leftRotate(node);}// RL 型if (balance -1 getBalanceFactor(node.right) 0) {node.right rightRotate(node.right);return leftRotate(node);}return node;}
右旋和左旋
// 右旋操作private Node rightRotate(Node y) {
// 实际上就是x和y的位置要改变
// 让x成为y的父节点
// 没改变前y是x的父节点Node x y.left;
// 如果有T2就连给y没有的话T2就是nully的左孩子就是nullNode T2 x.right;x.right y;y.left T2;
// 更新高度y.height Math.max(getHeight(y.left), getHeight(y.right)) 1;x.height Math.max(getHeight(x.left), getHeight(x.right)) 1;return x;}// 左旋操作private Node leftRotate(Node x) {Node y x.right;Node T2 y.left;y.left x;x.right T2;x.height Math.max(getHeight(x.left), getHeight(x.right)) 1;y.height Math.max(getHeight(y.left), getHeight(y.right)) 1;return y;}
带parent的AVL
方法具体实现看这篇文章https://blog.csdn.net/jarvan5/article/details/112428036
题未完待续
叶子节点的个数
public int count(Node root) {if (root null) {return 0;} else if (root.left null root.right null) {return 1;}return count(root.left) count((root.right));}
第k层的节点数
一个节点的孩子节点的上一层就是这个节点所在层
所以计算第k层所有节点的孩子节点的上一层结点数即为所求
public int countK(Node root,int k) {if (root null) {return 0;}if(k 1) {return 1;}return countK(root.left , k-1) countK(root.right , k-1);}
是否是完全二叉树
是否相同
要判断两棵树是否相同必须同时满足以下两个条件 结构相同两棵树的节点位置和父子关系必须一致。 节点值相同对应位置的节点值必须相等。
递归
public boolean isSameTree(Node p, Node q) {// 如果两个节点都为空则相同if (p null q null) {return true;}// 如果一个节点为空另一个不为空则不同if (p null || q null) {return false;}// 比较当前节点的值if (p.val ! q.val) {return false;}// 递归比较左右子树return isSameTree(p.left, q.left) isSameTree(p.right, q.right);}
迭代
public boolean isSameTree(Node p, Node q) {// 使用栈来存储需要比较的节点对StackNode[] stack new Stack();stack.push(new Node[]{p, q});while (!stack.isEmpty()) {Node[] nodes stack.pop();Node node1 nodes[0];Node node2 nodes[1];// 如果两个节点都为空继续比较下一对节点if (node1 null node2 null) {continue;}// 如果一个节点为空另一个不为空则不同if (node1 null || node2 null) {return false;}// 比较当前节点的值if (node1.val ! node2.val) {return false;}// 将左右子节点对压入栈中stack.push(new Node[]{node1.left, node2.left});stack.push(new Node[]{node1.right, node2.right});}return true;}
注意
中序遍历的结果不能唯一确定一棵树的结构因此不能直接用来判断两棵树是否相同
反例 但中序遍历搭配前序或者后序遍历即可唯一确定一棵树
所以可以比较两种遍历的结果是否一致一致就相同
但这样需要开辟空间存遍历结果所以这种方法不太好ListInteger存结果return pPreOrder.equals(qPreOrder) pInOrder.equals(qInOrder); 比较
存结果
是否镜像
判断相同是left和left比right和right比
判断镜像是left和right比right和left比
public boolean isMirrorTree(Node p, Node q) {// 如果两个节点都为空则相同if (p null q null) {return true;}// 如果一个节点为空另一个不为空则不同if (p null || q null) {return false;}// 比较当前节点的值if (p.val ! q.val) {return false;}// 递归比较左右子树return isMirrorTree(p.left, q.right) isMirrorTree(p.right, q.left);
}
翻转二叉树二叉树的镜像
左右反转二叉树的节点 public Node reverseTree(Node root) {
// 从下到上翻转if (root null) {return null;}// 交换当前节点的左右子节点Node temp root.left;root.left root.right;root.right temp;// 递归地反转左子树reverseTree(root.left);// 递归地反转右子树reverseTree(root.right);return root;}
前序遍历
public void pre(Node root) {if (root null) {return;}System.out.print(root.val );pre(root.left);pre(root.right);}
后序遍历
public void post(Node root) {if (root null) {return;}post(root.left);post(root.right);System.out.print(root.val );}
BST区间搜索
给定一个区间范围返回所有在这个区间的值
