数据结构常用代码模板--树，图，排序
时间：2022-11-02 10:30:00
文章目录
- 树
-
- 二叉树遍历
-
- 先序遍历
- 中序遍历
- 后序遍历
- 层次遍历
- 例题
- 线索二叉树的构建和经验
-
- 构造(中序为例)
- 遍历
- 二叉排序树
-
- 插入
- 查找
- 删除
- 例题
- 图
-
- 广度遍历
- 深度遍历
- Dijstra(单源最短路径)
- Floyd(多源最短路径)
- 排序
-
- 1. 插入排序
-
- 1.1 直接插入排序
- 1.2 半插入排序
- 1.3 希尔排序
- 2. 交换排序
-
- 2.1冒泡排序
- 2.2 快速排序
- 3. 选择排序
-
- 3.简单选择排序
- 3.2 堆排序
- 4.归并排序(nlogn)
- 5. 比较
树
二叉树遍历
先序遍历
//递归版 void PreOrder(BiTree T) {
if(T != null) {
visit(T); PreOrder(T.left); PreOrder(T.right); } } //非递归1 void PreOrder1(BiTree T) {
Stack s = new Stack(); BiTree cur = T; // 可以判断T \= null while(cur != null || !s.isEmpty()) {
if(cur != null) {
visit(cur); s.push(cur); cur = cur.left; } else {
cur = s.pop(); cur = cur.right; } } } //非递归2 void PreOrder2(BiTree T) {
Stack s = new Stack(); BiTree cur = T; if(T != null) {
s.push(T); while(!T.isEmpty()) {
cur = s.pop(); visit(cur); //先序是NLR，出栈与入栈逆序，所以R先入栈L后入栈 if(cur.right != null) s.push(cur.right); if(cur.left != null) s.push(cur.left); } } } //非递归java List<Integer> PreOrder(TreeNode root){
List<Integer> nodes = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); TreeNode cur = root; while(cur != null || !stack.isEmpty()){
while(cur != null){
nodes.add(cur.val); stack.push(cur); cur = cur.left; } cur = stack.pop(); cur = cur.right; } return nodes; } 中序遍历
//递归
void InOrder(BiTree T) {
if(T != null) {
InOrder(T.left);
visit(T);
InOrder(T.right);
}
}
//非递归
void InOrder(BiTree T) {
Stack s = new Stack();
Bitree cur = T;
while(cur != null || !s.isEmpty()){
if(cur != null) {
s.push(cur);
cur = cur.left;
} else {
cur = s.pop();
visit(cur);
cur = cur.right;
}
}
}
//非递归java
List<Integer> InOrder(TreeNode root){
List<Integer> nodes = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.pop();
nodes.add(cur.val);
cur = cur.right;
}
return nodes;
}
后序遍历
//递归
void PostOrder(BiTree T) {
if(T != null) {
PostOrder(T.left);
PostOrder(T.right);
visit(T);
}
}
//非递归
void PostOrder1(BiTree T) {
Stack s1 = new Stack();
Stack s2 = new Stack();
//先序，NLR， 后序 LRN
s1.push(T);
while(!s1.isEmpty()) {
BiTree tmp = s1.pop();
s2.push(tmp);
//先序非递归是先入栈右子树后左子树，后序非递归先左子树后右子树是因为把中间结果
//存在中间栈中，最后还要出栈顺序再次相反所以要先左后右入栈S2
//入栈前需要的遍历顺序是NLR
//入s2的顺序是NRL
if(tmp.left != null) s1.push(tmp.left);
if(tmp.right !=null) s1.push(tmp.right);
}
//出s2的顺序LRN
while(!s2.isEmpty()) {
visit(s2.pop());
}
}
//非递归2
void PostOrder2(BiTree T) {
Stack s = new Stack();
BiTree cur = T;
Bitree visited = null;
while(cur != null || !s.isEmpty()) {
if(cur != null) {
s.push(cur);
cur = cur.left;
} else {
//没有左孩子时出现在栈顶的结点，此时不能将其出栈并访问，
//因其右孩子还没被访问。应按相同的规则对其右子树进行遍历，
//当访问完其右孩子时，该结点又出现在栈顶，此时可以将其出栈并访问
cur = s.peek();
//if(cur != null && cur != visited) {
//到这步是s一定不为空，所以上面的if没必要判断cur是否为空
if(cur != visited) {
//第一次出现，从左子树返回来的
cur = cur.right;
//s.push(cur);
//cur = cur.left;
} else {
cur = s.pop();
visit(cur);
visited = cur;
cur = null; //置空当前节点，以防下一轮判断时重新入栈
}
}
}
}
//非递归java
List<Integer> PostOrder(TreeNode root){
List<Integer> nodes = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
TreeNode pre = null;
while(cur != null || !stack.isEmpty()){
while(cur != null){
stack.push(cur);
cur = cur.left;
}
cur = stack.peek();
if(cur.right != null && cur.right != pre){
cur = cur.right;
} else {
stack.pop();
nodes.add(cur.val);
pre = cur;
cur = null;
}
}
return nodes;
}
层次遍历
void LevelOrder(BiTree T) {
Queue queue = new Queue();
queue.add(T);
while(!queue.isEmpty()) {
BiTree cur = queue.poll();
visit(cur);
if(cur.left != null) queue.add(cur.left);
if(cur.right != null) queue.add(cur.right);
}
}
例题
- 设计非递归算法求二叉树的高度，递归算法呢
//非递归
int getHight(BiTree root) {
int depth = 0;
if(root != null) {
Queue queue = new Queue();
queue.add(root);
BiTree last = root; //mask the last element of each layer
while(!queue.isEmpty()) {
BiTree cur = queue.poll();
if(cur.left != null) cur.add(cur.left);
if(cur.right != null) cur.add(cur.right);
if(cur == last) {
//按照层序遍历，当上一层的最后一个元素出对时，下一层的所有元素都刚好入队
depth++;
last = queue.lastElement();
}
}
}
return depth;
}
//递归
int getDepth(BiTree root) {
if(root == null) return 0;
int left = getDepth(root.left);
int right= getDepth(root.right);
return max(left, right) + 1;
}
- 判断二叉树是完全二叉树的算法
//完全二叉树中n个结点与满二叉树前n个结点是完全对应的
boolean isComplete(BiTree root) {
//层序遍历，把子节点为空的情况也入队，完全二叉树的层序遍历中队里不能有空
if(root != null) {
Queue queue = new Queue();
queue.add(root);
while(!queue.isEmpty()) {
BiTree cur = queue.poll();
if(cur != null) {
//入队时不判断是否为空
queue.add(cur.left);
queue.add(cur.right);
} else {
//完全二叉树只有叶结点会引入空指针且遇到空结点后队中不能再有非空结点
while(!queue.isEmpty()){
if(queue.poll() != null)
return false;
}//end while
}//end else
}//end while
}//end if
return true;
}
- 计算二叉树的所有双分支结点数
int dsonNode(BiTree root) {
if(root == null) return 0;
if(root.left != null && root.right != null)
return dsonNode(root.left) + dsonNode(root.right) + 1;
else return dsonNode(root.left) + dsonNode(root.right);
}
- 设计算法交换二叉树中所有结点的左右子树
void exchange(BiTree root) {
if(root == null) return;
exchange(root.left);
exchange(root.right);
BiTree tmp = root.left;
root.left = root.right;
root.right= tmp;
}
- 对于二叉树中每个值为x的元素，删除以他为根的子树
//java与c++不同，c需要手动释放内存
void delete(BiTree root, Type value){
if(root.val == value) {
root = null;
return;
}
delete(root.left, value);
delete(root.right, value);
}
- 查找二叉树中值为x的结点并打印其所有祖先，假设x不多于一个
//可以使用非递归后续遍历，当找到节点时，栈中的元素就是所有祖先节点 void PrintAncestors(BiTree root, Typer value) { Stack s = new Stack(); BiTree cur = T; Bitree visited = null; while(cur != null || !s.isEmpty()) { if(cur != null) { s.push(cur); cur = cur.left; } else { cur = s.peek(); if(cur.val = value){ while(!s.isEmpty()) print(s.pop().val); return; } if(cur != visited) { //第一次出现，从左子树返回来的 cur = cur.right; } else { cur = s.pop(); visit(cur); visited = cur; cur = null; //置空当前节点，以防下一轮判断时重新入栈 } } } } //方式1 int flag = 0; //定义一个全局变量来判断是否查找到了值 void PrintAncestors(bittree* BT, int x) { if (!BT) return; if (BT->data == x) { flag = 1; //查询到值的时候 改变标志位 return; } if (flag == 0) { PrintAncestors(BT->LChild, x); //若没有查找到往节点的左侧查找 } if (flag == 0) PrintAncestors(BT->RChild, x);//若没有查找到往节点的右侧查找 if (flag == 1) {
