摘要:当集合为空时,称该二叉树为空二叉树。也就是说,如果一个二叉树的层数为,且结点总数是,则它就是满二叉树。完全二叉树完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。
在数据结构中什么是树呢?我们有如下定义和性质:
定义: 树是一种非线性的数据结构,它是由n(n>=0)个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的。
性质:
1、 有一个特殊的结点,称为根结点,根节点没有前驱结点。
2、 除根节点外,其余结点被分成M(M>0)个互不相交的集合T1、T2、……、Tm,其中每一个集合Ti(1<= i<= m)又是一棵结构与树类似的子树。每棵子树的根结点有且只有一个前驱,可以有0个或多个后继结点。
3、 因此,树是递归定义的。
注意: 树形结构中,子树之间不能有交集,否则就不是树形结构
树结构相对线性表就比较复杂了,要存储表示起来就比较麻烦了,既然保存值域,也要保存结点和结点之间的关系,实际中树有很多种表示方式如:双亲表示法,孩子表示法、孩子双亲表示法以及孩子兄弟表示法等。
我们这里就简单的了解其中最常用的孩子兄弟表示法:
typedef int DataType;struct Node{struct Node* leftChild1; // 第一个孩子结点struct Node* rightBrother; // 指向其下一个兄弟结点DataType data; // 结点中的数据域};
二叉树是n个有限元素的集合,该集合或者为空、或者由一个称为根(root)的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成,是有序树。
当集合为空时,称该二叉树为空二叉树。在二叉树中,一个元素也称作一个结点。
根据上图可以分析出:
二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。
在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作;但是用C语言实现是非常麻烦和不容易理解的,所以下面我们都是手动来创建一颗简单树,来学习二叉树的精华。
和其它数据结构一样,创建二叉树得先创建一个二叉树类型的数据,代码如下:
typedef char BTDataType; //对char类型重新起个名字叫BTDataType//创建一个二叉树类型typedef struct BinaryTreeNode{ BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;}BTNode;
创建代码如下:
typedef char BTDataType; //对char类型重新起个名字叫BTDataType//创建一个二叉树类型typedef struct BinaryTreeNode{ BTDataType data; struct BinaryTreeNode* left; struct BinaryTreeNode* right;}BTNode;//开辟一个结点函数BTNode* BuyNode(BTDataType x){ BTNode* tmp = (BTNode*)malloc(sizeof(BTNode)); if (tmp == NULL) { perror("erron "); exit(-1); } tmp->data = x; tmp->left = NULL; tmp->right = NULL; return tmp;}//创建一个树的函数BTNode* CreatBinaryTree(){ //先依次开辟多个结点 BTNode* a = BuyNode("A"); BTNode* b = BuyNode("B"); BTNode* c = BuyNode("C"); BTNode* d = BuyNode("D"); BTNode* e = BuyNode("E"); BTNode* f = BuyNode("F"); BTNode* g = BuyNode("G"); //然后把结点连接成一棵树 a->left = b; a->right = c; b->left = d; c->left = e; c->right = f; return a;}int main(){ //创建一棵树,用变量root来接收树的根 BTNode* root = CreatBinaryTree();}
问题来了,我们创建一棵二叉树有什么价值呢?要研究二叉树的什么呢?下面我们慢慢分析关于二叉树的经典问题。
我们先来分析二叉树的前中后遍历,关于前中后遍历的定义如下:
二叉树的前中后遍历的结果如下图分析:
我们了解这棵树的前序遍历,那怎么用代码实现出来呢?
代码如下:
//前序遍历void PrevOrder(BTNode* root){ if (root == NULL){ printf("NULL "); return; } //先访问根节点 printf("%c ", root->data); //再访问左右子树 PrevOrder(root->left); PrevOrder(root->right);}int main(){ //手动连接结点创建一棵树 BTNode* root = CreatBinaryTree(); //前序遍历 PrevOrder(root); printf("/n");}
可能大家一看,这是个递归呀!它是这么做到前序遍历的呢?怎么看都看不出来呀。其实这和C语言的函数栈帧这块知识点连续起来了,如果还没有了解函数栈帧这块可以先看看我的这两篇博客,里面介绍了递归和函数栈帧,点击即可跳转==> 【递归的快速掌握】 【函数栈帧的创建与销毁】
好了,那既然看得有点迷迷糊糊的,拿我们来画一下递归的展开图,图片如下:
这个二叉树的中序遍历是先访问左子树,再访问根结点,最后再访问右子树
代码实现如下:
//中序遍历void InOrder(BTNode* root){ if (root == NULL) { printf("NULL "); return; } //先访问左子树 InOrder(root->left); //再访问根 printf("%c ", root->data); //再访问右子树 InOrder(root->right);}int main(){ //手动连接结点创建一棵树 BTNode* root = CreatBinaryTree(); //中序遍历 InOrder(root); printf("/n");}
这个和前序遍历都是用递归实现的,我们脑海里可能构想不出来递归的全部路径,我们还是画出递归展开图来分析,图片如下:
二叉树的后序遍历是先访问左子树,再访右子树,最后访问根。
代码实现如下:
//后序遍历void PostOrder(BTNode* root){ if (root == NULL) { printf("NULL "); return; } //先访问左子树 PostOrder(root->left); //再访问右子树 PostOrder(root->right); //再访问根 printf("%c ", root->data);}int main(){ //手动连接结点创建一棵树 BTNode* root = CreatBinaryTree(); //后序遍历 PostOrder(root); printf("/n");}
这个二叉树销毁我们要注意不能先销毁根,再销毁左右子树,因为先释放根就找不到左右子树的地址了。所以我们先销毁左右子树最后再销毁根,和后序遍历相似。
代码如下:
//二叉树的销毁void DestroyTree(BTNode* root){ if (root == NULL) { return; } //先释放左右子树再释放根 DestroyTree(root->left); DestroyTree(root->right); free(root);}int main(){ //手动连接结点创建一棵树 BTNode* root = CreatBinaryTree(); //前序遍历 PrevOrder(root); printf("/n"); //中序遍历 InOrder(root); printf("/n"); //后序遍历 PostOrder(root); printf("/n"); //销毁二叉树 DestroyTree(root);}
二叉树的销毁和后序遍历是差不多的,都是先处理左右子树再处理根,感觉不够理解的小伙伴可以按我前面前序和中序遍历一样把递归展开图一个一个地画出来,能大大增加我们对递归的理解。
要想求二叉树结点的个数我们还是转化成子问题去解决。求二叉树总的结点个数,那我可以先求左右子树的结点个数再加上1自己就是总的个数了;而左右子树又可以细分左右子树一层层的递归下去再返回来就可以了。
代码如下:
int BinaryTreeSize(BTNode* root){ if (root == NULL) { return 0 ; } //先求左右子树的个树再加上根结点就是总的结点个数 return BinaryTreeSize(root->left) + BinaryTreeSize(root->right) + 1;}int main(){ //手动连接节点创建一棵树 BTNode* root = CreatBinaryTree(); //统计二叉树的结点个数 int ret=BinaryTreeSize(root); printf("二叉树结点的个数为%d/n", ret);}
我们如果看起来感觉还是心里不踏实,总感觉不对劲,我们可以用老方法画递归展开图来分析分析,递归展开图如下:
这个求的是叶子节点个数,而叶子节点的定义是左右子树都为空才是叶子节点,所以我们还是用递归分而治之的思想,统计左子树的叶子结点个数加上右子树的叶子结点个数即可,这样左右子树分别递归下去,最后返回的就是总的叶子结点个数。
代码如下:
//统计叶子结点的个数int BinaryTreeLeafSize(BTNode* root){ if (root == NULL) { return 0; } //当左右子树都为空才是叶子,就返回1 if (root->left == NULL && root->right == NULL) { return 1; } //分别统计左右子树的叶子结点个数,加起来就是总数 return BinaryTreeLeafSize(root->left) + BinaryTreeLeafSize(root->right);}
递归展开图如下:
这个也是要用递归的分而治之思想,统计第K层结点个数,我们先统计K - 1层的结点个数,一直递归分下去到k等于1的时候,结点如果不为空就是1个结点。
比如求第4层结点的个数,我们可以转化为求第3层左子树结点的个数 + 右子树结点的个数;而第3层又可以转化为第二层左右子树的结点个数,一直递归下去。
代码实现如下:
// 二叉树第k层节点个数int BinaryTreeLevelKSize(BTNode* root, int k){ if (root == NULL) { return 0; } //当结点不为空,且k==1结点个数就为1 if (k == 1) { return 1; } //转化为求第k-1层的左右子树结点个数,一直分治下去,直到遇到NULL或者k==1 return BinaryTreeLevelKSize(root->left, k - 1) + BinaryTreeLevelKSize(root->right, k - 1);}
递归展开图如下:
这个还是采用递归的分而治之思想,我们先求出左子树的高度,再求出右子树的高度,然后二者相比较,大的加1就是二叉树的高度;而左右子树再递归下去求高度,最后就可以得到二叉树的高度。代码实现如下:
//求二叉树的高度int BinaryTreeDepth(BTNode* root){ if (root == NULL) { return 0; } //先求出左右子树的高度 int leftDepth = BinaryTreeDepth(root->left); int rightDepth = BinaryTreeDepth(root->right); //比较左右子树的高度,大的加1就是树的高度 return leftDepth > rightDepth ? leftDepth + 1 : rightDepth + 1;}
题目意思是在二叉树中找和一个X值相等的结点,如果找到了就返回该结点的地址,如果没有找到就返回空指针NULL;
我们还是用分而治之来解决,先在左子树中找,如果找到了就返回该结点地址,如果左子树没有找到那就去右子树里面找,找到了就返回地址。如果左右子树都没有找到就返回空指针NULL。
代码实现如下:
//在二叉树中找值为X的结点BTNode* BinaryTreeFind(BTNode* root, BTDataType x){ if (root == NULL) { return NULL; } //找到了就直接返回该结点地址 if (root->data == x) { return root; } //先在左子树中找 BTNode* left = BinaryTreeFind(root->left,x); if (left != NULL) { return left; } //左子树中没有找到就往右子树中找 BTNode* right = BinaryTreeFind(root->right, x); if (right != NULL) { return right; } //如果左右子树都没有找到就返回空指针 return NULL;}
我们学了二叉树的前、中、后序遍历,还剩下最后一个就是层序遍历;顾名思义就是要一层层地往下面遍历,我们可以利用前面学过的队列来解决。
第一步,先判断二叉树是否为空,为空就直接返回
第二步,把二叉树的根入队列,然后取队头的元素,再出队列
第三步,判断队头元素的左右子树是否为空,不为空就入队列,为空就不入队列
第四步,判断队列是否为空,不为空就继续取队头的元素,再出队列,循环第三、四步即可,这样就做到了一层层遍历
图片分析如下:
因为C语言中没有队列,所以我们需要手动实现一个队列,在前面的博客中详细地介绍并实现了队列,点击即可跳转==>【队列的模拟实现】,所以下面代码中直接引用即可,
代码实现如下:
void BinaryTreeOrder(BTNode* root){ if (root == NULL) { return; } Queue q; QueueInit(&q); //把根入队列 QueuePush(&q, root); while (!QueueEmpty(&q)) { //取队头的元素 BTNode* front = QueueFront(&q); printf("%c", front->data); QueuePop(&q); //出队列 if (front->left != NULL) { QueuePush(&q, front->left); } if (front->right != NULL) { QueuePush(&q, front->right); } } //销毁队列 QueueDestroy(&q);}
我们知道完全二叉树最后一层的叶子结点一定都是连续的,如果叶子结点没有连续中间有空指针的话就不是完全二叉树了;所以我们利用这个特点和利用队列解决,
首先我们把不为空的根先入队列,然后取队头的元素,接着出队列
然后不管队头的元素左右子树是否为空我们都入队列;
接着就不断取队头的元素,取到空指针就不再入队列,判断队列剩下的元素是否都为空指针,如果都为空指针代表叶子结点都是连续的,是完全二叉树;如果不都为空指针,代表叶子结点是不连续的不是完全二叉树。
代码实现如下:
//判断二叉树是否为完全二叉树bool BinaryTreeComplete(BTNode* root){ if (root == NULL) { return false; } Queue q; QueueInit(&q); QueuePush(&q, root); while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); QueuePop(&q); //如果队头元素不为空就入队头元素的左右子树 //如果队头元素为空就退出 if (front != NULL) { QueuePush(&q, front->left); QueuePush(&q, front->right); } else { break; } } //判断队列剩下的元素是否都为空指针 //都为空指针就是完全二叉树 while (!QueueEmpty(&q)) { BTNode* front = QueueFront(&q); if (front != NULL) { QueueDestroy(&q); return false; } QueuePop(&q); } return true;
文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。
转载请注明本文地址:https://www.ucloud.cn/yun/124780.html
阅读 1761·2021-11-24 09:39
阅读 2410·2021-10-14 09:43
阅读 3285·2021-10-08 10:10
阅读 2185·2021-09-22 15:54
阅读 2307·2019-08-29 17:20
阅读 1540·2019-08-28 18:14
阅读 2346·2019-08-26 13:28
阅读 1073·2019-08-26 12:16