二叉树前序遍历
灌溉渠道-资本市场
2023年2月21日发(作者：各国首都)⼆叉树概念及结构
1.树概念及结构
1.1树概念
树是⼀种⾮线性的数据结构，它是由n（n>=0）个有限结点组成⼀个具有层次关系的集合。把它叫做树是因
为它看起来像⼀棵倒挂的树，也就是说它是根朝上，⽽叶朝下的。
根结点：根节点没有前驱结点。
除根节点外，其余结点被分成是⼀棵结构与树类似的⼦树。每棵⼦树的根结点有且只有⼀个前驱，可以有0个或多个后继。
因此，树是递归定义的。
节点的度：⼀个节点含有的⼦树的个数称为该节点的度；如上图：A的为2
叶节点：度为0的节点称为叶节点；如上图：G、H、I节点为叶节点
⾮终端节点或分⽀节点：度不为0的节点；如上图：B、D、C、E、F节点为分⽀节点
双亲节点或⽗节点：若⼀个节点含有⼦节点，则这个节点称为其⼦节点的⽗节点；如上图：A是B的⽗节点
孩⼦节点或⼦节点：⼀个节点含有的⼦树的根节点称为该节点的⼦节点；如上图：B是A的孩⼦节点
兄弟节点：具有相同⽗节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
兄弟节点：具有相同⽗节点的节点互称为兄弟节点；如上图：B、C是兄弟节点
树的度：⼀棵树中，最⼤的节点的度称为树的度；如上图：树的度为2
节点的层次：从根开始定义起，根为第1层，根的⼦节点为第2层，以此类推；
树的⾼度或深度：树中节点的最⼤层次；如上图：树的⾼度为4
堂兄弟节点：双亲在同⼀层的节点互为堂兄弟；如上图：H、I互为兄弟节点
节点的祖先：从根到该节点所经分⽀上的所有节点；如上图：A是所有节点的祖先
⼦孙：以某节点为根的⼦树中任⼀节点都称为该节点的⼦孙。如上图：所有节点都是A的⼦孙
森林：由m棵互不相交的树的集合称为森林；
1.2树的表⽰
树结构相对线性表就⽐较复杂了，要存储表⽰起来就⽐较⿇烦了，实际中树有很多种表⽰⽅式，如：双亲表
⽰法，孩⼦表⽰法、孩⼦兄弟表⽰法等等。我们这⾥就简单的了解其中最常⽤的孩⼦兄弟表⽰法。
typedefintDataType;
structNode
{
structNode*firstChild1;
structNode*pNextBrother;
DataTypedata;
};
2.⼆叉树概念及结构
2.1概念
⼀棵⼆叉树是结点的⼀个有限集合，该集合或者为空，或者是由⼀个根节点加上两棵别称为左⼦树和右⼦树的⼆叉树组成。
⼆叉树的特点：
每个结点最多有两棵⼦树，即⼆叉树不存在度⼤于2的结点。
⼆叉树的⼦树有左右之分，其⼦树的次序不能颠倒。
2.2数据结构中的⼆叉树
2.3特殊的⼆叉树
满⼆叉树：⼀个⼆叉树，如果每⼀个层的结点数都达到最⼤值，则这个⼆叉树就是满⼆叉树。也就是说，如果⼀个⼆叉树的层数为K，且结
点总数是(2^k)-1，则它就是满⼆叉树。
完全⼆叉树：完全⼆叉树是效率很⾼的数据结构，完全⼆叉树是由满⼆叉树⽽引出来的。对于深度为K的，有n个结点的⼆叉树，当且仅当
其每⼀个结点都与深度为K的满⼆叉树中编号从1⾄n的结点⼀⼀对应时称之为完全⼆叉树。要注意的是满⼆叉树是⼀种特殊的完全⼆叉
树。
2.4⼆叉树的存储结构
⼆叉树⼀般可以使⽤两种存储结构，⼀种顺序结构，⼀种链式结构。
2.4.1顺序存储
顺序结构存储就是使⽤数组来存储，⼀般使⽤数组只适合表⽰完全⼆叉树，因为不是完全⼆叉树会有空间的浪费。⽽现实中使⽤中只有堆才
会使⽤数组来存储。⼆叉树顺序存储在物理上是⼀个数组，在逻辑上是⼀颗⼆叉树。
2.4.2链式存储
⼆叉树的链式存储结构是指，⽤链表来表⽰⼀棵⼆叉树，即⽤链来指⽰元素的逻辑关系。通常的⽅法是链表中每个结点由三个域组成，数
据域和左右指针域，左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。链式结构⼜分为⼆叉链和三叉链，当前我们
学习中⼀般都是⼆叉链，后⾯课程学到⾼阶数据结构如红⿊树等会⽤到三叉链。
//⼆叉链
structBinaryTreeNode
{
structBinTreeNode*_pLeft;//指向当前节点左孩⼦
structBinTreeNode*_pRight;//指向当前节点右孩⼦
BTDataType_data;//当前节点值域
}
//三叉链
structBinaryTreeNode
{
structBinTreeNode*_pParent;//指向当前节点的双亲
structBinTreeNode*_pLeft;//指向当前节点左孩⼦
structBinTreeNode*_pRight;//指向当前节点右孩⼦
BTDataType_data;//当前节点值域
}；
2.5⼆叉树的性质
若规定根节点的层数为1，则⼀棵⾮空⼆叉树的第i层上最多有2^(i-1)个结点.
若规定根节点的层数为1，则深度为h的⼆叉树的最⼤结点数是2^h-1.
对任何⼀棵⼆叉树,如果度为0其叶结点个数为n0,度为2的分⽀结点个数为n2,则有n0＝n2＋1
若规定根节点的层数为1，具有n个结点的满⼆叉树的深度，h=Log2(n+1).(ps：Log2(n+1)是log以2为
底，n+1为对数)
对于具有n个结点的完全⼆叉树，如果按照从上⾄下从左⾄右的数组顺序对所有节点从0开始编号，则对
于序号为i的结点有：
1.若i>0，i位置节点的双亲序号：(i-1)/2；i=0，i为根节点编号，⽆双亲节点
2.若2i+1=n否则⽆左孩⼦
3.若2i+2=n否则⽆右孩⼦
4.⼆叉树顺序结构及概念
3.1⼆叉树的顺序结构
普通的⼆叉树是不适合⽤数组来存储的，因为可能会存在⼤量的空间浪费。⽽完全⼆叉树更适合使⽤顺序结构存储。现实中我们通常
把堆(⼀种⼆叉树)使⽤顺序结构的数组来存储，需要注意的是这⾥的堆和操作系统虚拟进程地址空间中的堆是两回事，⼀个是数据结
构，⼀个是操作系统中管理内存的⼀块区域分段。
3.2堆的概念及结构
如果有⼀个关键码的集合K={k0，k1，k2，…，kn-1}，把它的所有元素按完全⼆叉树的顺序存储⽅式存储在⼀个⼀维数组中，并满⾜：
Ki<=K2i+1且Ki=K2i+1且Ki>=K2i+2)i=0，1，2…，则称为⼩堆(或⼤堆)。将根节点最⼤的堆叫做最⼤堆或⼤根
堆，根节点最⼩的堆叫做最⼩堆或⼩根堆。
堆的性质：
堆中某个节点的值总是不⼤于或不⼩于其⽗节点的值；
堆总是⼀棵完全⼆叉树。
3.3堆的实现
typedefintHPDataType;
typedefstructHeap
{
HPDataType*_a;
int_size;
int_capacity;
}Heap;
voidswap(int*a,int*b);
voidAdjustDown(int*a,intparent,intn);
voidAdjustUp(int*a,intchild,intn);
//堆的构建
voidHeapCreate(Heap*hp,HPDataType*a,intn);
//堆的销毁
voidHeapDestory(Heap*hp);
//堆的插⼊
voidHeapPush(Heap*hp,HPDataTypex);
//堆的删除
voidHeapPop(Heap*hp);
//取堆顶的数据
HPDataTypeHeapTop(Heap*hp);
//堆的数据个数
intHeapSize(Heap*hp);
//堆的判空
intHeapEmpty(Heap*hp);
//对数组进⾏堆排序
voidHeapSort(int*a,intn);
voidswap(int*a,int*b)
{
inttmp=*a;
*a=*b;
*b=tmp;
}
voidAdjustUp(int*a,intchild,intn)
{
intparent=(child-1)/2;
while(child>0)
{
if(a[child]>a[parent])
{
swap(&a[child],&a[parent]);
child=parent;
parent=(child-1)/2;
}
else
{
break;
}
}
}
voidAdjustDown(inta,intparent,intn)
{
intchild=parent*2+1;
while(child { if(child+1 ++child; } if(a[child]>a[parent]) { swap(&a[child],&a[parent]); parent=child; child=(parent*2)+1; } else { break; } } } voidHeapCreate(Heaphp,HPDataType*a,intn) { assert(hp); hp->_a=(HPDataType*)malloc(sizeof(HPDataType)*n); if(hp->_a==NULL) { printf(“mallocfail”); exit(-1); } for(inti=0;i { hp->_a[i]=a[i]; } hp->_size=hp->_capacity=n; for(inti=(n-2)/2;i>=0;--i) { AdjustDown(hp->_a,i,hp->_size); } } //堆的销毁 voidHeapDestory(Heap*hp) { assert(hp); hp->_size=hp->_capacity=0; free(hp); } //堆的插⼊ voidHeapPush(Heap*hp,HPDataTypex) { assert(hp); if(hp->_size==hp->_capacity) { HPDataType*tmp=(HPDataType*)realloc(hp->_a,sizeof(HPDataType)*2*hp->_capacity); if(tmp==NULL) { printf(“reallocfail”); exit(-1); } hp->_a=tmp; hp->_a[hp->_size]=x; ++hp->_size; hp->_capacity*=2; } else { hp->_a[hp->_size]=x; ++hp->_size; } AdjustUp(hp->_a,hp->_size-1,hp->_size); } //堆的删除 voidHeapPop(Heap*hp) { assert(hp); assert(hp->_size>0); swap(&hp->_a[hp->_size-1],&hp->_a[0]); –hp->_size; AdjustDown(hp->_a,0,hp->_size); } //取堆顶的数据 HPDataTypeHeapTop(Heap*hp) { assert(hp); assert(hp->_size>0); returnhp->_a[0]; } //堆的数据个数 intHeapSize(Heap*hp) { assert(hp); returnhp->_size; } //堆的判空 intHeapEmpty(Heap*hp) { assert(hp); returnhp->_size==0?1:0; for(inti=0;i<3;++i)} //对数组进⾏堆排序 voidHeapSort(int*a,intn) { assert(a); for(inti=(n-2)/2;i>=0;--i) { AdjustDown(a,i,n); } intend=n-1; while(end>0) { swap(&a[0],&a[end]); AdjustDown(a,0,end); –end; } } 4.⼆叉树链式结构及实现 4.1⼆叉树链式结构的遍历 所谓遍历(Traversal)是指沿着某条搜索路线，依次对树中每个结点均做⼀次且仅做⼀次访问。访问结点所做的操作依赖于具体的应⽤问 题。遍历是⼆叉树上最重要的运算之⼀，是⼆叉树上进⾏其它运算之基础。 前序/中序/后序的递归结构遍历：是根据访问结点操作发⽣位置命名 NLR：前序遍历(PreorderTraversal亦称先序遍历)——访问根结点的操作发⽣在遍历其左右⼦树之前。 LNR：中序遍历(InorderTraversal)——访问根结点的操作发⽣在遍历其左右⼦树之中（间）。 LRN：后序遍历(PostorderTraversal)——访问根结点的操作发⽣在遍历其左右⼦树之后。 由于被访问的结点必是某⼦树的根，所以N(Node）、L(Leftsubtree）和R(Rightsubtree）⼜可解释为根、根的左⼦树和根的右⼦树。 NLR、LNR和LRN分别⼜称为先根遍历、中根遍历和后根遍历。 层序遍历：除了先序遍历、中序遍历、后序遍历外，还可以对⼆叉树进⾏层序遍历。设⼆叉树的根节点所在层数为1，层序遍历就是从所在 ⼆叉树的根节点出发，⾸先访问第⼀层的树根节点，然后从左到右访问第2层上的节点，接着是第三层的节点，以此类推，⾃上⽽下，⾃左 ⾄右逐层访问树的结点的过程就是层序遍历。 4.2⼆叉树的链式实现 typedefcharBTDataType; typedefstructBinaryTreeNode { BTDataType_data; structBinaryTreeNode*_left; structBinaryTreeNode*_right; }BTNode; typedefBTNode*QDataType; //链式结构：表⽰队列 typedefstructQListNode { structQListNode*_next; QDataType_data; }QNode; //队列的结构 typedefstructQueue { QNode*_front; QNode*_rear; }Queue; BTNode*CreateBTNode(BTDataTypex); //通过前序遍历的数组"ABD##E#H##CF##G##"构建⼆叉树 BTNode*BinaryTreeCreate(BTDataType*a,intn,int*pi); //⼆叉树销毁 voidBinaryTreeDestory(BTNode**root); //⼆叉树节点个数 intBinaryTreeSize(BTNode*root); //⼆叉树叶⼦节点个数 intBinaryTreeLeafSize(BTNode*root); //⼆叉树第k层节点个数 intBinaryTreeLevelKSize(BTNode*root,intk); //⼆叉树查找值为x的节点 BTNode*BinaryTreeFind(BTNode*root,BTDataTypex); //⼆叉树前序遍历 voidBinaryTreePrevOrder(BTNode*root); //⼆叉树中序遍历 voidBinaryTreeInOrder(BTNode*root); //⼆叉树后序遍历 voidBinaryTreePostOrder(BTNode*root); //初始化队列 voidQueueInit(Queue*q); //队尾⼊队列 voidQueuePush(Queue*q,QDataTypedata); //队头出队列 voidQueuePop(Queue*q); //获取队列头部元素 QDataTypeQueueFront(Queue*q); //获取队列队尾元素 QDataTypeQueueBack(Queue*q); //获取队列中有效元素个数 intQueueSize(Queue*q); //检测队列是否为空，如果为空返回⾮零结果，如果⾮空返回0 intQueueEmpty(Queue*q); //销毁队列 voidQueueDestroy(Queue*q); //层序遍历 voidBinaryTreeLevelOrder(BTNode*root); //判断⼆叉树是否是完全⼆叉树 intBinaryTreeComplete(BTNode*root); //初始化队列 voidQueueInit(Queue*q) { assert(q); q->_front=q->_rear=NULL; } //队尾⼊队列 voidQueuePush(Queue*q,QDataTypedata) { assert(q); QNodenewnode=((QNode)malloc(sizeof(QNode))); newnode->_data=data; newnode->_next=NULL; if(q->_rear==NULL) { q->_front=q->_rear=newnode; } else { q->_rear->_next=newnode; //q->_rear=q->_rear->_next; q->_rear=newnode; } } //队头出队列 voidQueuePop(Queue*q) { assert(q); assert(!QueueEmpty(q)); if(q->_front==q->_rear) { free(q->_front); //free(q->_rear); q->_front=q->_rear=NULL; } else { QNodecur=q->_front->_next; free(q->_front); q->_front=cur; } } //获取队列头部元素 QDataTypeQueueFront(Queueq) { assert(q); assert(!QueueEmpty(q)); returnq->_front->_data; } //获取队列队尾元素 QDataTypeQueueBack(Queue*q) { assert(q); assert(!QueueEmpty(q)); returnq->_rear->_data; } //获取队列中有效元素个数 intQueueSize(Queue*q) { assert(q); intsize=0; QNode*cur=q->_front; while(cur) { ++size; cur=cur->_next; } returnsize; } //检测队列是否为空，如果为空返回⾮零结果，如果⾮空返回0 intQueueEmpty(Queue*q) { assert(q); returnq->_front==NULL?1:0; } //销毁队列 voidQueueDestroy(Queue*q) { assert(q); QNodecur=q->_front; while(cur) { QNodenext=cur->_next; free(cur); cur=next; } q->_front=q->_rear=NULL; } BTNodeCreateBTNode(BTDataTypex) { BTNodenode=(BTNode)malloc(sizeof(BTNode)); node->_data=x; node->_left=NULL; node->_right=NULL; returnnode; } //通过前序遍历的数组"ABD##E#H##CF##G##"构建⼆叉树 BTNodeBinaryTreeCreate(BTDataType*a,intn,int*pi) { if(a[*pi]==‘#’) { returnNULL; } BTNodenode=(BTNode)malloc(sizeof(BTNode)); node->_data=a[*pi]; ++pi; node->_left=BinaryTreeCreate(a,n,pi); ++pi; node->_right=BinaryTreeCreate(a,n,pi); returnnode; } //⼆叉树销毁 voidBinaryTreeDestory(BTNoderoot) { if(*root!=NULL) { if((*root)->_left)//有左孩⼦ BinaryTreeDestory(&(*root)->_left);//销毁左孩⼦⼦树 if((*root)->_right)//有右孩⼦ BinaryTreeDestory(&(*root)->_right);//销毁右孩⼦⼦树 free(*root);//释放根结点 *root=NULL;//空指针赋NULL } } //⼆叉树节点个数 intBinaryTreeSize(BTNode*root) { if(root==NULL) { return0; } returnBinaryTreeSize(root->_left)+BinaryTreeSize(root->_right)+1; } //⼆叉树叶⼦节点个数 intBinaryTreeLeafSize(BTNode*root) { if(root==NULL) { return0; } if(root->_left==NULL&&root->_right==NULL) { return1; } returnBinaryTreeLeafSize(root->_left)+BinaryTreeLeafSize(root->_right); } //⼆叉树第k层节点个数 intBinaryTreeLevelKSize(BTNode*root,intk) { if(root==NULL) { return0; } if(k==1) { return1; } returnBinaryTreeLevelKSize(root->_left,k-1)+BinaryTreeLevelKSize(root->_right,k-1); } //⼆叉树查找值为x的节点 BTNode*BinaryTreeFind(BTNode*root,BTDataTypex) { if(root==NULL) { returnNULL; } if(root->_data==x) { returnroot; } BTNode*ret=BinaryTreeFind(root->_left,x); if(ret!=NULL) { returnret; } ret=BinaryTreeFind(root->_right,x); if(ret!=NULL) { returnret; } returnNULL; } //⼆叉树前序遍历 voidBinaryTreePrevOrder(BTNode*root) { if(root==NULL) { //printf("NULL“); return; } printf(”%c",root->_data); BinaryTreePrevOrder(root->_left); BinaryTreePrevOrder(root->_right