网站不备案可以么,成都市温江区建设局网站,安徽网站开发哪家好,台州 做网站目录
一、二叉树的定义
1、二叉树的定义
2、二叉树的五种形态 二叉树的子树 #xff1a;
3、满二叉树与完全二叉树
4、二叉树的性质
5、二叉树的存储结构
1、顺序存储
编辑
2、链式存储 二、二叉树的遍历
按照前序序列构建二叉树
1、前 (先) 序遍历(Preorder …目录
一、二叉树的定义
1、二叉树的定义
2、二叉树的五种形态 二叉树的子树
3、满二叉树与完全二叉树
4、二叉树的性质
5、二叉树的存储结构
1、顺序存储
编辑
2、链式存储 二、二叉树的遍历
按照前序序列构建二叉树
1、前 (先) 序遍历(Preorder Traversal )
前序遍历动态过程图 下面是前序遍历的递归图解
前序遍历代码及注释
2. 中序遍历(Inorder Traversal)
中序遍历动态过程图
中序遍历代码及注释
3. 后序遍历(Postorder Traversal)
后序遍历动态过程图
后序遍历代码及注释
4、层序遍历
层序遍历代码及注释 一、二叉树的定义
1、二叉树的定义
二叉树Binary Tree是有nn≥0个结点的有限集合 1) 该集合或者为空n0) 2或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树 3左子树和右子树同样又都是二叉树。 在一棵非空的二叉树中每个结点至多只有两棵子树分别称为左子树和右子树且左右子树的次序不能任意交换。所以二叉树是特殊的有序树。值得注意的是由于二叉树上任结点的子树有左、右之分因此即使一个结点只有一棵非空子树仍须区别它是该结点的左子树还是右子树这是与树不同的。 2、二叉树的五种形态 二叉树的子树 在二叉树中一个子树是指由二叉树中的某个节点及其后代节点组成的树。换句话说对于一个给定的二叉树可以选择其中的一个节点作为子树的根节点并且包含该节点的所有后代节点形成一个新的子树。
具体定义如下 在一个二叉树中每个节点最多只有两个子节点分别为左子节点和右子节点。对于任意一个节点在它的左子节点和右子节点上又可以分别构成两个独立的子树这样就形成了一个递归的结构。 3、满二叉树与完全二叉树
1. 满二叉树一个二叉树如果每一个层的结点数都达到最大值则这个二叉树就是满二叉树。也就是说如果一个二叉树的层数为K且结点总数是 则它就是满二叉树。 2. 完全二叉树完全二叉树是效率很高的数据结构完全二叉树是由满二叉树而引出来的。对于深度为K的有n个结点的二叉树当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。特点树高为h时前h-1层节点为满。 要注意的是满二叉树是一种特殊的完全二叉树。 4、二叉树的性质
若规定根节点的层数为1则一棵非空二叉树的第i层上最多有2^(i-1)个结点。若规定根节点的层数为1则深度为h的二叉树的最大结点数是2^h-1。对任何一棵二叉树, 如果度为0的叶结点个数为n0度为2的分支结点个数为n2则有 n0 n2 1。若规定根节点的层数为1具有n个结点的满二叉树的深度h log2(n1)。这里的log是以2为底的对数对于具有n个结点的完全二叉树如果按照从上至下从左至右的数组顺序对所有节点从0开始编号则对于序号为i的结点有 a. 若i 0i位置节点的双亲序号为(i-1)/2若i 0则i为根节点编号无双亲节点。 b. 若2i1 n左孩子序号为2i1若2i1 n则无左孩子。 c. 若2i2 n右孩子序号为2i2若2i2 n则无右孩子。 5、二叉树的存储结构
二叉树一般可以使用两种结构存储一种顺序结构一种链式结构。
1、顺序存储
顺序结构存储就是使用数组来存储一般使用数组只适合表示完全二叉树因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储关于堆我们后面的博客会专门讲解。二叉树顺序存储在物理上是一个数组在逻辑上是一颗二叉树。 2、链式存储 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链本节内容我们主要讲解二叉链式存储结构。
链式二叉树结点定义如下
typedef char BTDataType; // 使用typedef关键字给char类型取了一个别名BTDataTypetypedef struct BTNode // 使用struct关键字定义了一个名为BTNode的结构体
{BTDataType data; // 二叉树节点的数据域用于存储具体的数据值struct BTNode* left; // 二叉树节点的左子节点指针指向左子节点struct BTNode* right; // 二叉树节点的右子节点指针指向右子节点
} BTNode; // 使用BTNode作为该结构体类型的别名 二、二叉树的遍历
按照前序序列构建二叉树
在对二叉树进行遍历之前我们先对通过前序遍历的数组ABD##E#H##CF##G##构建一颗二叉树。注意# 字符代表该节点为空。
// 前序建立二叉树的函数
BTNode* CreateBinaryTreePre(BTDataType* a, int n, int* pi)
{// 如果数组索引超出数组长度返回空指针if (*pi n){return NULL;}// 如果当前位置的值为 #表示当前位置为空节点将数组索引向后移动并返回空指针if (a[*pi] #){(*pi);return NULL;}// 动态分配一个新的二叉树节点BTNode* root (BTNode*)malloc(sizeof(BTNode));// 如果内存分配成功if (root){// 将当前位置的值存储到新节点的数据域中root-data a[(*pi)];// 递归调用CreateBinaryTreePre函数构建新节点的左子树root-left CreateBinaryTreePre(a, n, pi);// 递归调用CreateBinaryTreePre函数构建新节点的右子树root-right CreateBinaryTreePre(a, n, pi);}else{// 如果内存分配失败打印错误信息并退出程序perror(malloc fail!);exit(-1);}return root; // 返回根节点
}// 主函数
int main()
{BTNode* root; // 定义二叉树的根节点指针BTDataType a[] { A,B,D,#,#,E,#,H,#,#,C,F,#,#,G,#,# ,\0 };int n strlen(a);int pi 0; // 定义一个变量用于追踪数组的索引位置// 调用CreateBinaryTreePre函数传入数组a、数组长度n和索引位置的指针pi//生成二叉树并返回根节点指针root CreateBinaryTreePre(a, n, pi);return 0;
} 1、前 (先) 序遍历(Preorder Traversal ) 访问根结点的操作发生在遍历其左右子树之前——即 根节点 - 左子树 - 右子树。 前序遍历二叉树的算法可以按照如下的步骤实现
如果二叉树为空直接返回。访问当前节点即输出当前节点的值。对当前节点的左子树进行前序遍历。对当前节点的右子树进行前序遍历。 我们如何理解遍历顺序呢博主在这里分享一下自己的方法 对于一棵二叉树我们先找到其根节点打印出根结点的值后我们对其左子树进行遍历。由于一颗二叉树可以划分出许多子树那么遍历左子树时我们即可将当前节点即根结点的左孩子结点看作左子树的根结点然后对当前子树再进行根节点 - 左子树 - 右子树 的遍历方法如果当前结点为空返回上一层递归。在当前根节点的左子树遍历完成时我们再对右子树进行遍历如此循环往复直至遍历完整棵树停止。 简而言之就是当遍历到一个新结点时把当前结点当作根节点接着去遍历当前结点的左右子树。进入下一个子树遍历时继续把当前结点当作根节点如此循环往复下去直至遇到空结点递归开始回溯。 前序遍历动态过程图 下面是前序遍历的递归图解 前序遍历代码及注释
// 前序遍历二叉树
void PrintPreOrder(BTNode* root)
{// 如果当前节点为空返回if (!root){return;}// 打印当前节点的值printf(%c , root-data);// 递归遍历左子树PrintPreOrder(root-left);// 递归遍历右子树PrintPreOrder(root-right);
} 2. 中序遍历(Inorder Traversal)
访问根结点的操作发生在遍历其左右子树之中间——即 左子树 -- 根节点 -- 右子树。
中序遍历二叉树的算法可以按照如下步骤实现
如果二叉树为空直接返回。对当前节点的左子树进行中序遍历。访问当前节点即输出当前节点的值。对当前节点的右子树进行中序遍历。 对于中序遍历我们采取类似的方法。当我们遍历时将当前结点当作子树的根节点先去寻找该根节点有没有左孩子如果有我们就向左进行遍历当到达新结点时我们依旧将其看作根节点去寻找该结点的左孩子如果当前结点为空再回溯到其父结点打印数据再去寻找它的右孩子。当当前子树遍历完成时我们回溯到此子树根节点的上一层的节点打印节点数据之后再去找该结点的右孩子。如此循环往复直至遍历完整棵树停止。 中序遍历动态过程图 中序遍历代码及注释
// 中序遍历
void PrintInOrder(BTNode* root)
{// 如果当前节点为空即已经到达叶子节点或者是空树的情况直接返回if (!root){return;}// 递归调用中序遍历函数遍历左子树PrintInOrder(root-left);// 打印当前节点的数据printf(%c , root-data);// 递归调用中序遍历函数遍历右子树PrintInOrder(root-right);
} 3. 后序遍历(Postorder Traversal)
访问根结点的操作发生在遍历其左右子树之后——即 左子树 --右子树 -- 根节点 。
后序遍历二叉树的算法可以按照如下的步骤实现
如果二叉树为空直接返回。对当前节点的左子树进行后序遍历。对当前节点的右子树进行后序遍历。访问当前节点即输出当前节点的值。 对于后序遍历我们依然按照之前的方法。当我们遍历时将当前结点当作子树的根节点先去寻找该根节点有没有左孩子如果有我们就向左进行遍历直至树的底部如果当前结点为空返回上一层递归再去判断当前节点有没有右孩子如果有我们再向右遍历重复上面的过程。当当前子树左右孩子遍历完后我们回退至子树的根结点打印数据。如此循环往复直至遍历完整棵树停止。 后序遍历动态过程图 后序遍历代码及注释
// 后序遍历
void PrintPostOrder(BTNode* root)
{// 如果当前节点为空直接返回if (!root){return;}// 递归调用后序遍历函数遍历左子树PrintPostOrder(root-left);// 递归调用后序遍历函数遍历右子树PrintPostOrder(root-right);// 打印当前节点的数据printf(%c , root-data);
} 4、层序遍历
层序遍历是二叉树中最常用的遍历方法之一它依次按层遍历二叉树中的结点。 具体实现思路如下
创建一个队列将根节点插入队列中。取出队列的首个节点访问该节点。若该节点有左子节点将左子节点插入队列中。若该节点有右子节点将右子节点插入队列中。重复步骤 2 ~ 4直到队列为空为止。 层序遍历代码及注释
typedef char BTDataType; // 二叉树中每个节点所存储的数据类型为 chartypedef struct BTNode
{BTDataType data; // 节点存储的数据struct BTNode* left; // 左子节点struct BTNode* right; // 右子节点
}BTNode; // 定义二叉树结构体typedef BTNode* QueueDataType; // 队列中每个节点所存储的数据类型为 BTNode 指针typedef struct QNode
{QueueDataType val; // 节点存储的数据struct QNode* next; // 指向下一个节点的指针
}QNode; // 定义队列节点结构体typedef struct Queue
{QNode* front; // 队头指针QNode* rear; // 队尾指针int size; // 队列中元素的个数
}Queue; // 定义队列结构体// 初始化队列
void QueueInit(Queue* q)
{assert(q);q-front NULL;q-rear NULL;q-size 0;
}// 入队
void QueuePush(Queue* q, QueueDataType x)
{assert(q);QNode* temp (QNode*)malloc(sizeof(QNode));if (temp NULL){perror(malloc fail!);exit(-1);}temp-val x;temp-next NULL;if (q-front NULL){q-front q-rear temp; // 队列为空时新元素既是队头也是队尾}else{q-rear-next temp; // 把新元素连接到队尾后q-rear temp; // 更新队尾指针为新的元素}q-size; // 队列元素个数加1
}// 判断队列是否为空
bool QueueEmpty(Queue* q)
{assert(q);if (q-front NULL){return true; // 队列为空}return false; // 队列不为空
}// 获取队头元素
QueueDataType QueueTop(Queue* q)
{assert(q);if (!QueueEmpty(q)){return q-front-val; // 返回队头元素的值}else{printf(队空无法获取队头元素\n);exit(-1);}
}// 出队
void QueuePop(Queue* q)
{assert(q);if (!QueueEmpty(q)){QNode* temp q-front; // 保存队头指针q-front q-front-next; // 移动队头指针到下一个元素free(temp); // 释放原队头节点的内存空间q-size--; // 队列元素个数减1}else{printf(队空无法删除队头元素\n);exit(-1);}
}// 获取队列元素个数
int QueueSize(Queue* q)
{assert(q);return q-size; // 返回队列元素个数
}// 二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{assert(root);Queue q;QueueInit(q); // 初始化队列QueuePush(q, root); // 将根节点入队int TSize 1;while (!QueueEmpty(q)){// 遍历当前层级的结点while (TSize 0){BTNode* cur QueueTop(q); // 获取队头元素QueuePop(q); // 出队printf(%c , cur-data); // 输出当前结点的数据if (cur-left){QueuePush(q, cur-left); // 左子节点入队}if (cur-right){QueuePush(q, cur-right); // 右子节点入队}TSize--; // 减少当前层级元素个数}printf(\n); // 输出换行符表示当前层级遍历结束TSize QueueSize(q); // 更新当前层级元素个数}
}
