二叉树遍历的递归和非递归算法
一.二叉树的遍历:
按照一定规律对二叉树的每个结点进行访问且仅访问一次;
这里的访问:可以是计算二叉树中的结点数据,打印该结点的信息,也可以是对结点进行的任何其它操作!
为什么需要遍历二叉树?
从过遍历可以得到访问结点的顺序序列,遍历操作就是将二叉树的结点按一定的规律线性化,目的就在于将非线性化的结构变成线性化的访问序列。
二.3种遍历方式:
1.先序遍历:(DLR)根——左——右
若二叉树非空:
首先访问根结点,其次按先序遍历左子树,最后按先序遍历右子树
下面我们给出一个例子:
如图所示的二叉树:根据先序遍历的特点,我们先访问根结点:A,再访问其左子树,而其左子树又可以看成一个二叉树,我们依然用先序遍历A的左子树,此时B为这个左子树的根结点,于是我们访问B,A的左子树此时还没有访问完成,因此我们继续访问,此时B已经访问过,那么我们接着访问B的左孩子,而B没有左孩子,所以我们接着访问B的右孩子,D作为右孩子的根结点,直接访问,对于D来说,接着访问D的左孩子F,最后访问D的右孩子G;此时A的左孩子遍历完成;
那么我们接着遍历A的右孩子,C作为右子树的根结点直接访问,C没有左孩子,接着访问C的右孩子,E作为C的右孩子的根节点,直接访问,E没有左孩子,访问E的右孩子H;
综上所述:上述二叉树的先序遍历的顺序就为:A-B-D-F-G-C-E-H
2.中序遍历:LDR(左——根——右)
我们仍然以上述二叉树为例来看:
根据 中序遍历的特点:首先按中序遍历左子树:此时首先访问A的左子树,我们将二叉树的左子树单独拿出来看:如图:B作为左子树的根节点,我们要找此时这个二叉树的左孩子,而此时这个二叉树没有左孩子,因此我们直接访问这个二叉树的根节点B,之后访问这个二叉树的右孩子:同样把这个二叉树的右孩子单独拿出来:此时我们依然以中序遍历:首先访问这个二叉树的左孩子,即F,接着访问这个二叉树的根节点D,最后访问这个二叉树的右孩子G;
那么此时整个二叉树的左孩子访问完成,继续访问整个二叉树的根节点A;
接着访问整个二叉树的右孩子:
此时C作为整个二叉树的右孩子的根节点,我们首先访问这个二叉树的左孩子,显然这个二叉树没有左孩子,因此我们先访问根结点C;
此时:E作为二叉树的根结点,此时该二叉树没有左孩子,直接访问根节点E,最后访问右孩子H
综上所述:按照中序遍历访问上述二叉树的顺序:B-F-D-G-A-C-E-H
3.后序遍历:LRD(左——右——根)
仍然以上述二叉树作为例子来看:首先访问整个二叉树的左子树:
按照后序遍历访问:B作为根结点,访问这个二叉树的左子树,左子树为空,接着访问这个二叉树的右孩子:
此时D作为根结点,先访问其左孩子F,接着访问其右孩子G,最后访问根节点D;
那么经过上述过程,该二叉树的右孩子访问完成,接着访问根节点B,此时整个二叉树的左子树遍历完成;
那么我们接着访问整个二叉树的右子树:
C作为此时这个二叉树的根结点,先访问这个二叉树的左子树,但是左子树为空,接着访问右孩子:
E为此时这个二叉树的根结点,此时这个二叉树没有左子树,那么我们访问其右孩子H,接着访问根节点E;
此时这个二叉树的右孩子也访问完成,所以我们访问根结点C;
整个二叉树的左右子树均已遍历完成,于是我们最后访问根结点A;
综上所述:按照后续遍历访问上述二叉树的顺序为:F-G-D-B-H-E-C-A
总结:
看了以上三种方式遍历二叉树的例子,应该就能明白三种遍历方式的本质与区别,其实我们可以看出,无论以何种方式,我们只要把握好访问的顺序,并且将每一个根结点下的子树都看成一个新树,再按照某种遍历方式访问这个这个新树即可!
例子:中缀表达式转后缀表达式;(前缀表达式:波兰表达式;后缀表达式:逆波兰表达式)
前缀表达式:-+a*bc/de(也就是以先序遍历访问上述二叉树的顺序)
中缀表达式:a+b*c-d/e(也就是以中序遍历访问上述二叉树的顺序)
后缀表达式:abc*+de/-(也就是以后序遍历访问上述二叉树的顺序)
我们其实可以看出:中缀表达式是我们在数学计算中的习惯顺序,但是其实在计算机种,后缀表达式才是计算机能理解的表达式;
(关于中缀表达式转后缀表达式的例题:
有兴趣的读者可以自行尝试:下面给出利用栈来解决逆波兰表达式的代码:
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MaxSize 1010
typedef struct
{
char* ch;
int top;
}CharStack;
typedef struct
{
double* num;
int top;
}NumStack;
CharStack S;
NumStack St;
void InitCharStack(CharStack& S);
void InitNumStack(NumStack& St);
void PushCharStack(CharStack& S, char c);
void PushNumStack(NumStack& St, double num);
char PopCharStack(CharStack& S);
double PopNumStack(NumStack& St);
char GetStackTop(CharStack& S);
bool PriorJudge(char c1, char c2);//priority优先级 judge判断
char* InfixToSuffex(char* a, char* b);//infix前缀 suffex后缀
double CaculatValue(char* b, NumStack& St);
int main()
{
InitCharStack(S);
char a[MaxSize] = { 0 };
char b[MaxSize] = { 0 };
InfixToSuffex(a, b);
double ans = CaculatValue(b, St);
printf("%.2f\n", ans);
return 0;
}
void InitCharStack(CharStack& S)
{
S.ch = (char*)malloc(MaxSize * sizeof(char));
if (S.ch == NULL)
{
printf("内存分配失败!");
return;
}
S.top = -1;
return;
}
void PushCharStack(CharStack& S, char c)
{
if (S.top == MaxSize)
{
printf("栈已满");
return;
}
S.top++;
*++S.ch = c;
return;
}
char PopCharStack(CharStack& S)
{
if (S.top == -1)
{
printf("栈为空");;
exit(1);
}
S.top--;
char c = *S.ch--;
return c;
}
char GetStackTop(CharStack& S)
{
char c = *S.ch;
return c;
}
bool PriorJudge(char c1, char c2)//priority优先级 judge判断
{
if (c1 == '*' || c1 == '/')
if (c2 == '+' || c2 == '-' || c2 == '(')
return true;
if (c1 == '+' || c1 == '-')
if (c2 == '(') return true;
return false;
}
char* InfixToSuffex(char* a, char* b)//infix中缀 suffex后缀
{
fgets(a, MaxSize - 1, stdin);//从输入流中读取字符串
int t = strlen(a);
int k = 0;
// 12.25 + 25.02 / 2.36 + 8 * 2.01 =
for (int i = 0; i < t; ++i)
{
if (a[i] >= '0' && a[i] <= '9')
{
b[k++] = a[i];
if (a[i + 1] == '.') b[k++] = '.', ++i;
else if (a[i + 1] < '0' || a[i + 1] > '9')
b[k++] = '#';
}
else if (a[i] == ' ' || a[i] == '=') continue;
else
{
if (S.top == -1 || a[i] == '(')
PushCharStack(S, a[i]);
else if (a[i] == ')')
{
while (S.top != -1 && GetStackTop(S) != '(')
b[k++] = PopCharStack(S);
if (S.top != -1) PopCharStack(S);
}
else
{
while (S.top != -1 && !PriorJudge(a[i], GetStackTop(S)))
b[k++] = PopCharStack(S);
PushCharStack(S, a[i]);
}
}
}
b[k] = '\0';//这句话加不加应该无所谓,因为该字符数组已初始化为0
return b;
}
void InitNumStack(NumStack& St)
{
St.num = (double*)malloc(MaxSize * sizeof(double));
St.top = -1;
return;
}
void PushNumStack(NumStack& St, double n)
{
if (St.top == MaxSize)
{
printf("栈已满");
return;
}
St.top++;
*++St.num = n;
return;
}
double PopNumStack(NumStack& St)
{
if (St.top == -1)
{
printf("栈为空");
exit(1);
}
St.top--;
double num = *St.num--;
return num;
}
double CaculatValue(char* b, NumStack& St)
{
InitNumStack(St);
int t = strlen(b);
char str[MaxSize] = { 0 };
for (int i = 0, k = 0; i < t; ++i)
{
if (b[i] == '.' || (b[i] >= '0' && b[i] <= '9'))
{
str[k++] = b[i];
if (b[i + 1] == '#')
{
str[k] = '\0';
double num = atof(str);
PushNumStack(St, num);
k = 0;
}
}
else
{
if (b[i] == '#') continue;
double n = PopNumStack(St);
double m = PopNumStack(St);
if (b[i] == '+') PushNumStack(St, m + n);
else if (b[i] == '-') PushNumStack(St, m - n);
else if (b[i] == '*') PushNumStack(St, m * n);
else PushNumStack(St, m / n);
}
}
return PopNumStack(St);
}
三.二叉树的遍历算法:
在理解了上述所说的遍历过程之后,我们来看二叉树的遍历算法,可以分为递归算法与非递归算法
1.递归算法:
(1)先序遍历的递归算法
首先定义二叉树的链表结点结构:
#define DataType int
//首先定义二叉树:
typedef struct Node
{
DataType data;
struct Node* LChild;
struct Node* RChild;
}BiTNode,*BiTree;
//先序遍历二叉树的递归算法
void PreOrder(BiTree root)
{
//root为指向二叉树或者其某一子树的根结点的指针
if (root != NULL)
{
printf("%d", root->data);//访问根结点;//文章开头就已经说过,二叉树的遍历可以是多种形式
PreOrder(root->LChild);//按照先序遍历访问左子树
PreOrder(root->RChild);//按照先序遍历访问右子树
}
}
(2)中序遍历递归算法
void InOrder(BiTree root)
{
if (root != NULL)
{
InOrder(root->LChild);//首先按中序遍历左子树
printf("%d", root->data);//访问根结点
InOrder(root->RChild);//中序遍历右子树
}
}
(3)后续遍历递归算法
void PostOrder(BiTree root)
{
if (root != NULL)
{
PostOrder(root->LChild);//首先按照后序遍历左子树
PostOrder(root->RChild);//按照后序遍历右子树
printf("%d", root->data);//访问根结点
}
}
递归:把复杂问题变成相同性质的子问题,因此递归算法表面上看上去很简单,其实整个的逻辑十分复杂;
比如:当访问到的结点不为空时,我们先访问其左子树,再访问其右子树;但是当根结点为空时,就不需要参与递归运算,那此时访问的为空,应该返回什么值?在这里程序就会自动设置堆栈来保存本层地址(涉及到堆栈的知识:当递归函数调用时,应按照“后调用先返回”(因为大问题一直在分解成小问题,当分解为基问题时,才会返回一个值,因此最后调用的先返回)的原则处理调用过程,因此函数之间的信息传递和控制转移必须通过栈来实现(符合栈的特点:last in first out)
整个递归过程其实与上述所描述的遍历算法类似,读者可尝试分析;
递归算法的时间复杂度分析:
假设二叉树有n个结点,对每个结点都要进行一次入栈和出栈的操作,即入栈和出栈均执行了n此,对结点的访问也是n次,这些二叉树的递归遍历算法的时间复杂度就为O(n);
A.递归遍历算法的应用:
a.输出二叉树中的结点:
//输出二叉树的结点
void PreOrder(BiTree root)
{
if (root != NULL)
{
printf("%d",root->data);
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
输出二叉树的结点并没有次序要求,因此三种次序均可以使用
b.输出二叉树中的叶子结点:
相比于上述应用,叶子节点:无后继,因此有条件限制
//输出叶子结点数
void PreOrder(BiTree root)
{
if (root != NULL)
{
if (root->LChild == NULL && root->RChild == NULL)
{
printf("%d", root->data);
}
PreOrder(root->LChild);
PreOrder(root->RChild);
}
}
c.统计叶子结点数目
(1)一般的后序遍历
void leaf(BiTree root)
{
if (root != NULL)
{
leaf(root->LChild);
leaf(root->RChild);
if (root->LChild == NULL && root->RChild == NULL)
{
leafCount++;//保存叶子结点数目的全局变量,调用之前的初始化为0;别忘了在main函数中先调用初始化函数
}
}
}
在这里:根据文章开头所说的,究竟什么才是对根结点进行访问?在这里leafCount++就可以是,因此在这里,我们使用的是后续遍历;
(2)分治算法:
如果二叉树为空树,返回0,如果二叉树只有一个根结点,返回1,否则返回左子树和右子树的叶子节点数之和(也是递归算法)
int leaf1(BiTree root)
{
int leafCount;
if (root == NULL)
{
leafCount = 0;
}
else if (root->LChild == NULL && root->RChild == NULL)
{
leafCount = 1;
}
else
{
leafCount = leaf1(root->LChild) + leaf1(root->RChild);
}
return leafCount;
}
在这里也是后序遍历:根据表达式:C=A+B,在C语言中是先计算A,再计算B,最后计算A+B,赋值给C,因此依然是先遍历左子树,再遍历右子树,最后访问根;
(关于求二叉树的高度:读者可尝试)
int PostTreeDepth(BiTree bt)
{
int hl, hr,max;
if (bt != NULL)
{
hl=PostTreeDepth(bt->LChild);
hr=PostTreeDepth(bt->RChild);
max = hl > hr ? hl : hr;
return(max + 1);//还要加上第一个根结点
}
else
{
return 0;
}
}
d:按横向树形显示二叉树:
其实就是按照“逆中序”的方式来遍历整个二叉树(所谓的逆中序,就是先访问右子树,再访问根,最后访问右子树,与正常的中序遍历相反)
(在这里只给出思路,具体代码实现,读者可以自行尝试,有问题欢迎在评论区交流!)
2.非递归算法:
基于栈的递归消除:
关于递归的消除:我们可以将这些递归问题,转化为重复的循环问题,即用循环代替递归,但是在工作量大,复杂的情况下,就不适宜采用循环,因此我们可以采用工作栈的方式来消除递归。
(1)中序遍历二叉树的非递归算法
下面我们以中序遍历二叉树的非递归算法为例来看:
整个过程都依据在上述框图下进行:
(以此二叉树为例)
首先:A:A不为空——进栈;p=A的LChild,到B;B不为空——进栈;p指向B的左子树,到C;C不为空,C进栈;p指向C的左子树;C的左子树为空,判断栈是否为空,栈此时非空,C出栈,p指向C的右子树,D,C的右子树不为空,D入栈,p指向D的左子树,p为空,那么判断栈是否为空,栈非空,D退栈,p指向D的右子树,D的右子树为空,栈非空,退栈到B,p指向B的右子树,为E,不是空,那么E进栈,E的左子树为空,栈非空,那么E出栈,p指向E的右子树,E的右子树为空,栈非空,A出栈,A的右子树为F,不为空F进栈,p指向F的左子树,F的左子树为G不为空,G进栈,p指向G的左子树,G的左子树为空,栈非空,G出栈,p指向G的右子树,G的右子树为空,栈非空,F出栈,p指向F的右子树,F的右子树为空,栈为空,那么遍历结束;(出栈的同时访问根结点,在这里我省略了,注意一下!!!)(可能有点长,可以耐心看一下)
此时:我们需要自己设置栈来保存结点的信息;为什么能够实现中序?基于栈的一些特点,我们可以直到,先进栈的后出栈,因此左子树先进栈后,一直保存在栈中,而到退栈的地步时,说明左子树一定为空,所以此时来访问右子树;并且在结点判断为非空时,其一直保存在栈中,并没有对其进行访问,所以一定是先访问左子树的,直到判断左子树为空时,我们才将左子树对应的根结点出栈,先访问根结点,再去访问右子树。
在这里其实进栈的一直都是根结点!
上述便是中序遍历的非递归算法;(极大地利用了栈的特点!!!)
(先序遍历的非递归算法与中序类似,与中序遍历的不同之处在于,中序保存根结点,而先序遍历我们可以保存右孩子的地址,这样比较简单,我们不再赘述;)
(2)后序遍历二叉树的非递归算法
我们首先说明一下:中序遍历的非递归与后序遍历的非递归算法的异同:
(1)相同点:根结点进栈
(2)而后序遍历在p=NULL时,不能直接出栈访问根结点,因为此时我们不能判断右孩子是否已经访问;
那我们该在什么时候访问?
(1)根的右子树为空;(2)根有右孩子,但是根的右子树已经访问过了;
对于第二中情况,我们如何判断根的右子树是否已经访问?那我们就可以多设置一个指针,记忆之前已经访问的结点;
(以此二叉树为例)
我们初始时设置p,q两个指针,p用于移动,q用于记忆已访问过的结点,q初始值设置为NULL
首先:根结点A不为空,入栈,p指向A的左子树:
此时p为B,B不为空,那么B入栈,p指向B的左子树,那么p为空,栈非空,并且此时B的右子树不为空,并且q=NULL,并不等于B的右子树,说明B的右子树还没有访问过,那么我们不访问根结点,p指向B的右子树;
p此时指向D,D的左子树不为空D入栈,p指向D的左子树,此时p指向E,E不为空,E入栈,p指向E的左子树,p此时为空,栈非空,读取栈顶元素E,并且q指向E的右子树,E的右子树为空,那么满足可以访问根结点的条件,因此我们访问E,E出栈,此时设置q为E,上面已经判断E的右子树为空,p为空,栈非空,那么读取栈顶元素D,此时D的右子树不为空,并且q也不等于D的右子树,那么说明D的右子树没有访问过,此时p=D的右子树F,p的右子树不为空,F入栈,p指向F的左子树,F的左子树为空,栈非空,读取栈顶元素F,p指向F的右子树,且F的右子树为空,那么我们访问结点F,F出栈,并且令q=F,并且由于p为空,栈非空,读取栈顶元素D,此时q=D的右子树F,满足访问条件,访问D,并且令q=D,D出栈;(下面分析:出栈之后读取栈顶元素)读取栈顶元素,B,此时q=B的右子树,满足访问的条件,我们访问B,并将q=B,B出栈(分析:访问完就出栈),读取栈顶元素,A,此时A的右子树不为空,并且q不等于A的右子树,不满足访问根的条件,因此我们访问A的右子树。
此时p=C,不为空,C入栈,p指向C的左子树,C的左子树为空,p=NULL,栈非空,且C的右子树不为空,q也不等于C的右子树G,那么不满足访问的条件,令p=C的右子树G,G不为空,G入栈,p=G的左子树,G的左子树为空,栈非空,G的右子树为空,满足访问的条件,因此访问G,令q=G,G出栈;再读取栈顶元素C,此时q=C的右子树G,满足访问的条件,访问C,并且令q=C,C出栈;读取栈顶元素A,此时q=A的右子树,那么满足访问的条件,访问A,令q=A,A出栈,此时栈为空且q=A,说明已经访问到最后一个结点处。遍历结束!
经过以上过程的分析:我们其实可以发现,每次在有元素出栈后,我们就开始读取栈顶元素;而在我们访问完成结点后,就进行出栈操作!
综上所述:就是后续遍历二叉树的非递归算法,与中序遍历不同的是:
加了一个起到记忆的作用的指针q,用于记忆已经访问过的结点;
加了一个读取栈顶元素的操作:因为不能立即访问根结点,出栈,所以要先确定访问之后,再出栈,所以我们先读取,不出栈即可。
除了上述区别之外,中序遍历与后序遍历大同小异!(后续遍历更为复杂!!!)读者可以跟着上述内容,自己走一遍这个二叉树的遍历的过程,就能够理解上述思想!
以上就是我对于二叉树的遍历的递归与非递归算法的一些个人总结与理解,欢迎读者有更好的方法再评论区交流!
下一篇: rsync+inotify
推荐阅读
-
二叉树遍历的递归和非递归算法
-
组合数算法的非递归实现
-
[姿势估计] 实践记录:使用 Dlib 和 mediapipe 进行人脸姿势估计 - 本文重点介绍方法 2):方法 1:基于深度学习的方法:。 基于深度学习的方法:基于深度学习的方法利用深度学习模型,如卷积神经网络(CNN)或递归神经网络(RNN),直接从人脸图像中学习姿势估计。这些方法能够学习更复杂的特征表征,并在大规模数据集上取得优异的性能。方法二:基于二维校准信息估计三维姿态信息(计算机视觉 PnP 问题)。 特征点定位:人脸姿态估计的第一步是通过特征点定位来检测和定位人脸的关键点,如眼睛、鼻子和嘴巴。这些关键点提供了人脸的局部结构信息,可用于后续的姿势估计。 旋转表示:常见的旋转表示方法包括欧拉角和旋转矩阵。欧拉角通过三个旋转角度(通常是俯仰、偏航和滚动)描述头部的旋转姿态。旋转矩阵是一个 3x3 矩阵,表示头部从一个坐标系到另一个坐标系的变换。 三维模型重建:根据特征点的定位结果,三维人脸模型可用于姿势估计。通过将人脸的二维图像映射到三维模型上,可以估算出人脸的旋转和平移信息。这就需要建立人脸的三维模型,然后通过优化方法将模型与特征点对齐,从而获得姿势估计结果。 特征点定位 特征点定位是用于检测人脸关键部位的五官基础部分,还有其他更多的特征点表示方法,大家可以参考我上一篇文章中介绍的特征点检测方案实践:人脸校正二次定位操作来解决人脸校正的问题,客户在检测关键点的代码上略有修改,坐标转换部分客户见上图 def get_face_info(image). img_copy = image.copy image.flags.writeable = False image = cv2.cvtColor(image, cv2.COLOR_BGR2RGB) results = face_detection.process(image) # 在图像上绘制人脸检测注释。 image.flags.writeable = True image = cv2.cvtColor(image, cv2.COLOR_RGB2BGR) box_info, facial = None, None if results.detections: for detection in results. for detection in results.detections: mp_drawing.Drawing.detection = 无 mp_drawing.draw_detection(image, detection) 面部 = detection.location_data.relative_keypoints 返回面部 在上述代码中,返回的数据是五官(6 个关键点的坐标),这是用 mediapipe 库实现的,下面我们可以尝试用另一个库:dlib 来实现。 使用 dlib 使用 Dlib 库在 Python 中实现人脸关键点检测的步骤如下: 确保已安装 Dlib 库,可使用以下命令: pip install dlib 导入必要的库: 加载 Dlib 的人脸检测器和关键点检测器模型: 读取图像并将其灰度化: 使用人脸检测器检测图像中的人脸: 对检测到的人脸进行遍历,并使用关键点检测器检测人脸关键点: 显示绘制了关键点的图像: 以下代码将参数 landmarks_part 添加到要返回的关键点坐标中。
-
数据结构与算法] 归并排序(详情:递归和非递归归并排序 | Free: 泡泡排序和选择排序)
-
算法 - 深度优先搜索和广度优先搜索 - 深度优先 - 非递归
-
反传销网8月30日发布:视频区块链里的骗子,币里的韭菜,杜子建骂人了!金融大V周召说区块链!——“一小帮骗子玩一大帮小白,被割韭菜,小白还轮流被割,割的就是你!” 什么区块链,统统是骗子 作者:周召(知乎金融领域大V,毕业于上海财经大学,目前任职上海某股权投资基金合伙人) 有人问我,区块链现在这么火,到底是不是骗局? 我的回答是: 是骗局。而且我并不是说数字货币是骗局,而是说所有搞区块链的都是骗局。 -01- 区块链是一种鸡肋技术 人类社会任何技术的发明应用,本质都是为了提高社会的生产效率。而所谓区块链技术本质不过是几种早已成熟的技术的大杂烩,冗余且十分低效,除了提高了洗钱和诈骗的效率以外,对人类社会的进步毫无贡献。 真正意义上的区块链得包含三个要素:分布式系统(包括记账和存储),无法篡改的数据结构,以及共识算法,三者互为基础和因果,就像三体世界一样。看上去挺让人不明觉厉的,而经过几年的瞎折腾,稍微懂点区块链的碰了几次壁后都已经渐渐明白区块链其实并没有什么卵用,区块链技术已经名存实亡,沦为了营销工具和传销组织的画皮。 因为符合上述定义的、以比特币为代表的原教旨区块链技术,是反效率的,从经济学角度来说,不但不是一种帕累托改进,甚至还可以说是一种帕累托倒退。 原教旨区块链技术的效率十分低下,因为要遍历所有节点,只能做非常轻量级的数据应用,一旦涉及到大量的数据传输与更新,区块链就瞎了。 一方面整条链交易速度会极慢,另一方面数据库容量极速膨胀,考虑到人手一份的存储机制,区块链其实是对存储资源和能源的一种极大的浪费。 这里还没有加上为了取得所谓的共识和挖矿消耗的巨大的能源,如果说区块链技术是屎,那么这波区块链投机浪潮可谓人类历史上最大规模的搅屎运动。 区块链也验证不了任何东西。 所谓的智能合约,即不智能,也非合约。我看有人还说,如果有了智能合约,就可以跟老板签一份放区块链上,如果明年销售业绩提升30%,就加薪10%,由于区块链不能篡改,不能抵赖,所以老板必须得执行,说得有板有眼,不懂行的愣一看,好像还真是那么回事。 但仔细一想,问题就来了。首先,在区块链上如何证明你真的达到了30%业绩提升?即便真的达到老板耍赖如何执行? 也就是说,如果区块链真这么厉害,要法院和仲裁干什么。 人类社会真正的符合成本效益原则的是代理制度。之前有人说要用区块链改造注册会计师行业,我不知道他准备怎么设计,我猜想他思路大概是这样的,首先肯定搞去中心化,让所有会计师到链上来,然后一个新人要成为注册会计师就要所有会计师同意并记录在链上。 那我就请问了,我每天上班累死累活,为什么还要花时间去验证一个跟我无关的的人的专业能力?最优做法当然是组织一个委员会,让专门的人来负责,这不就是现在注册会师协会干的事儿吗?区块链的逻辑相当于什么事情都要拿出来公投,这个绝对是扯淡的。 当然这么说都有点抬举区块链了,区块链技术本身根本没有判断是非能力,如果这么高级的人工智能,靠一个无脑分布式记账就能实现的话,我们早就进入共产主义社会了。 虽然EOS等数字货币采用了超级节点,通过再中心化的方式提高效率,有点行业协会的意思,是对区块链原教旨主义的一种修正,但是依然无法突破区块链技术最本质的局限性。有人说,私有链和联盟链是区块链技术的未来,也是扯淡,因为区块链技术没有未来。如果有,说明他是包装成区块链的伪区块链技术。 区块链所涉及的所有底层技术,不管是分布式数据库技术,加密技术,还是点对点传输技术等,基本都是早已存在没什么秘密可言的技术。 比特币系统最重要的特性是封闭性和自洽性,他验证不了任何系统自身以外产生的信息的真实性。 所谓系统自身产生的信息,就是数据库数据的变动信息,有价值的基本上有且只有交易信息。所以说比特币最初不过是中本聪一种炫技的产物,来证明自己对几种技术的掌握,你看我多牛逼,设计出了一个像三体一样的系统。因此,数字货币很有可能是区块链从始至终唯一的杀手应用。 比特币和区块链概念从诞生到今天已经快10年了,很多人说区块链技术在爆发的前夜,但这个前夜好像是不是有点过长了啊朋友,跟三体里的长夜有一拼啊。都说区块链技术像是90年代初的互联网,可是90年代初的互联网在十年发展后,已经出现了一大批伟大的公司,阿里巴巴在99年都成立了,区块链怎么除了币还是币呢? 正规的数字货币未来发展的形式无外乎几种,要么就是论坛币形式,或者类似股票的权益凭证等。问题是论坛币和股票之前,本来也都电子化了,区块链来了到底改变了什么呢? 所有想把TOKEN和应用场景结合起来的人最后都很痛苦,最后他们会发现区块链技术就是脱裤子放屁,自己辛苦搞半天,干嘛不自己作为中心关心门来收钱?最后这些人都产生了价值的虚无感,最终精神崩溃,只能发币疯狂收割韭菜,一边嘴里还说着我是个好人之类的奇怪的话。 因此,之前币圈链圈还泾渭分明,互相瞧不起,但这两年链圈逐渐坐不住了,想着是不是趁着泡沫没彻底破灭之前赶快收割一波,不然可能什么都捞不着了。 前段时间和一个名校毕业的链圈朋友瞎聊天,他说他们“致力于用区块链技术解决数字版权保护问题”,我就问他一个问题,你们如何保证你链的版权所有权声明是真实的,万一盗版者抢先一步把数据放在链上怎么办。他说他们的解决方案是连入国家数字版权保护中心的数据库进行验证…… 所以说区块链技术就是个鸡肋,研究到最后都会落入效率与真实性的黑洞,很多人一头扎进链圈后才发现,真正意义上的区块链技术,其实什么都干不了。 -02- 不是蠢就是坏的区块链媒体 空气币和区块链的造富神话,让区块链自媒体也开始迎风乱扭。一群群根本不知道区块链为何物的妖魔鬼怪纷纷进驻区块链自媒体战场,开始大放厥词胡编乱造。 任何东西,但凡只要和区块,链,分,分布式,记账,加密,验证,可追溯等等这些个关键词沾到哪怕一点点,这些所谓的区块链媒体人就会像狗闻到了屎了一样疯狂地把区块链概念往上套。 这让我想起曾经一度也是热闹非凡的物联网,我曾经去看过江苏一家号称要改变世界的“物联网”企业,过去一看是生产路由器的,我黑人问号脸,对方解释说没有路由器万物怎么互联,我觉得他说得好有道理,竟无言以对。 好,下面让我们进入奇葩共赏析时间,来看看区城链媒体经常有哪些危言耸听的奇谈怪论 区块链(分布式记账)的典型应用是*?? 正如前面所说,真正意义上的区块链分布式记账,不光包括“记”这个动作,还包括分布式存储和共识机制等。而*诞生远远早于区块链这个词的出现,勉强算是“分布式编辑”吧,就被很多区块链媒体拿来强行充当区块链技术应用的典范。 其实事实恰恰相反,*恰恰是去中心化失败的典范,现在如果没有精英和专业人士的编辑和维护,*早就没法看了。 区块链会促进社会分工?? 罗振宇好像就说过类似的话,虽然罗振宇说过很多没有逻辑的话,但这句话绝对是最没逻辑思维的。很多区块链自媒体也常常用这句话来忽悠老百姓,说分工代表效率提高社会进步,而区块链“无疑”会促进分工,他们的理由仅仅是分工和分布式记账都共用一个“分”字,就强行把他们扯到一起。 实际情况恰恰相反,区块链是逆分工的,区块链精神是号召所有人积极地参与到他不擅长也不想掺合的事情里面去。 区块链不能像上帝一样许诺他的子民死后上天国,只能给他们许诺你们是六度人脉中的第一级,我可以赚后面五级人的钱,你处于金字塔的顶端。
-
实现平衡二叉排序树的各种算法(包括二叉树的递归遍历和非递归遍历)
-
在Python 3的递归函数中:理解全局和非局部变量 - 重点在于你针对同一个可变对象的操作
-
求解二叉树的高度(递归、非递归)
-
深入解析二叉树的递归遍历方法:先序、中序、后序与层次遍历步骤详细讲解