天蝎网站建设,浙江省住房和城乡建设厅官网证件查询,wordpress后台seo优化教程,wordpress分类页获取分类名称数据结构第九讲#xff1a;二叉树 1.实现链式结构二叉树1.1二叉树的节点结构1.2创建二叉树节点1.3前中后序遍历1.3.1前序遍历1.3.2中序遍历1.3.3后序遍历1.3.4总结 1.4二叉树结点的个数1.4.1错误示范1.4.2实现方法 1.5二叉树叶子结点的个数1.6二叉树第k层结点的个数1.7二叉树的… 数据结构第九讲二叉树 1.实现链式结构二叉树1.1二叉树的节点结构1.2创建二叉树节点1.3前中后序遍历1.3.1前序遍历1.3.2中序遍历1.3.3后序遍历1.3.4总结 1.4二叉树结点的个数1.4.1错误示范1.4.2实现方法 1.5二叉树叶子结点的个数1.6二叉树第k层结点的个数1.7二叉树的深度/高度1.8二叉树查找值为x的结点1.9二叉树的销毁 2.二叉树的层序遍历2.1什么是层序遍历2.2层序遍历的实现2.2.1实现思路2.2.2先创建一个队列2.2.3代码的实现 3.判断是否为完全二叉树3.1解题思路3.2代码实现 这一讲我们要实现二叉树的链式结构二叉树结构体中包含了数据、指向左孩子节点的指针和指向右孩子节点的指针在这一讲中我们将要体会的递归的暴力 1.实现链式结构二叉树
1.1二叉树的节点结构
//二叉树的节点结构
typedef int BinaryTreeDataType;typedef struct BinaryTreeNode
{BinaryTreeDataType data;//保存数据struct BinaryTreeNode* left;//指向左孩子节点struct BinaryTreeNode* right;//指向右孩子节点
}BTNode;1.2创建二叉树节点 也就是为二叉树创建节点并将节点进行初始化 //创建二叉树节点
BTNode* BuyBTNode(int val)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL){perror(malloc fail!);return NULL;}newnode-data val;newnode-left newnode-right NULL;return newnode;
}1.3前中后序遍历 接下来我们要实现的是二叉树的遍历 二叉树的遍历操作分为三种前序遍历、中序遍历、后序遍历 可以看出这里区分的前中后其实就是根节点遍历的顺序 我们先总体看三种遍历的不同
接下来我们来实现三种遍历注意三种遍历方法的代码实现非常简单主要是思路的体会三种方法都是使用的递归的思想
1.3.1前序遍历
//前序遍历
//函数传入的是树的根节点
void PreOrder(BTNode* root)
{if (root NULL){return;}//将节点的数据进行打印printf(%d , root-data);PreOrder(root-left);PreOrder(root-right);
}对于递归return之后只是一个递归函数终止然而形参的值不变函数会继续向下执行形成一个全新的递归函数 1.3.2中序遍历
//中序遍历
void InOrder(BTNode* root)
{//也就是左根右进行遍历if (root NULL){return;}//先对左边的数据进行读取其实就是将左边的节点当成是根节点进行传入InOrder(root-left);//先打印根节点的值然后再检查右节点是否为空printf(%d , root-data);//当右节点不为空时它会按照从上向下的顺序一直走到右节点的尽头//当然当有右节点中存在左节点时会先走左节点的循环因为左节点的循环在上//而且会一下走到左节点的尽头然后从下往上遍历左节点InOrder(root-right);
}1.3.3后序遍历
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){return;}//仍然是先走到最后一个左节点PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}1.3.4总结 1.4二叉树结点的个数
1.4.1错误示范 根据我们之前所讲那么我们应该会有一个初步的思路我们先实现一下 //二叉树结点个数
//先定义一个变量sz
int sz 0;
int BTSize(BTNode* root)
{if (root NULL){return 0;}//每循环一次那么就将sz一次sz;BTSize(root-left);BTSize(root-right);return sz;
}这时打印的结果也是非常beautiful啊和预想的一样但是当我们这样时
//二叉树结点个数
int size BTSize(n1);
printf(%d , size);//6
size BTSize(n1);
printf(%d , size);//12我们就会惊奇地发现结点的次数竟然会随着函数调用次数的增加而成倍地增长原因就是使用了全局变量全局变量在函数使用后不会销毁那么我们就要进行更改了
1.4.2实现方法
//二叉树结点个数
int BTSize(BTNode* root)
{if (root NULL){return 0;}//返回左节点的个数和右节点的个数return 1 BTSize(root-left) BTSize(root-right);
}1.5二叉树叶子结点的个数
//二叉树叶子结点个数
int BTLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}//这里的返回值也会参与加法运算所以会呈现出累加的效果//也就是说返回值会存储到BTLeafSize(root-left)或另一个函数中然后再进入加法运算//返回左边的树的叶子节点个数 右边的树的叶子结点个数return BTLeafSize(root-left) BTLeafSize(root-right);
}对于递归先搞清总体思路如上边的返回左边的树的叶子节点个数 右边的树的叶子结点个数然后再想清楚结束条件如当左节点和右节点都为0时返回1此时会发现递归已经写完了 1.6二叉树第k层结点的个数
//二叉树第k层结点的个数
int BTLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}//返回条件当k 1时if (k 1){return 1;}//返回左边的二叉树第k层的节点个数和右边二叉树第k层的结点个数return BTLevelKSize(root-left, k - 1) BTLevelKSize(root-right, k - 1);
}1.7二叉树的深度/高度
要想在递归的过程中对数据逐渐进行增大必须要让return返回的值被接收而且参与递归运算这里是创建变量进行存储还可以使用递归函数进行存储如1BTDeapth(root-right)这里是瞎写仅代表一个格式
//二叉树的深度/高度
int BTDepth(BTNode* root)
{if (root NULL){return 0;}int leftdepth BTDepth(root-left);int rightdepth BTDepth(root-right);//要想在递归的过程中对数据逐渐进行增大必须要让return返回的值被接收而且参与递归运算//这里是创建变量进行存储//还可以使用递归函数进行存储如1BTDeapth(root-right)这里是瞎写仅代表一个格式return leftdepth rightdepth ? leftdepth 1 : rightdepth 1;
}1.8二叉树查找值为x的结点
//二叉树查找值为x的结点
BTNode* BTFind(BTNode* root, BinaryTreeDataType x)
{if (root NULL){return NULL;}//返回条件当数据是我们想要的数据时就进行返回if (root-data x){return root;}BTNode* left BTFind(root-left, x);if (left){//这里要十分注意的是//这里的return表示的是整个函数的返回上面的return代表的是递归函数的返回//原因就在于使用了一个值来接受递归函数的返回值使得递归函数结束递归了//如果这里不适用变量来接受的话函数将会错误返回return left;}BTNode* right BTFind(root-right, x);if (right){return right;}return NULL;
}1.9二叉树的销毁
//二叉树的销毁
//因为销毁要改变指针的指针的指向所以这里传的是二级指针
void BTDestory(BTNode** root)
{if (*root NULL){return;}//这里的传参要注意因为是二级指针接收所以传入的应该是一级指针的地址//直接遍历所有结点然后一一删除即可BTDestory((*root)-left);BTDestory((*root)-right);free(*root);*root NULL;
}2.二叉树的层序遍历
2.1什么是层序遍历
层序遍历就是按照层数从左到右一次对数据进行遍历
2.2层序遍历的实现
2.2.1实现思路 对于递归它会一直执行下去直到遇到结束条件然而这个算法中并不支持递归的使用因为我们想不出来什么结束条件能够成立所以这时我们就想到了其它的方法队列 下面我们来看实现方法
2.2.2先创建一个队列 恰巧我们刚刚学过了队列所以我们完全可以将之前写的队列代码拿过来但是要注意的是之前我们所实现的队列中保存的值为int类型但是现在因为插入的值为BTNode*类型所以还要将类别进行更改 //结点结构体
//尽管我们之前已经使用typedef将结构体的名字改变成了BTNode*
//这里仍然需要加上struct否则编译器会识别不出来万一是一个变量名呢对不对
typedef struct BTNode* QueueDataType;typedef struct QueueNode
{//和链表一样也需要结点进行链接QueueDataType val;struct QueueNode* next;
}QueueNode;2.2.3代码的实现
//二叉树层序遍历
void LevelOrder(BTNode* root)
{//先创建一个队列Queue q;//队列初始化Init(q);//将二叉树链表入队列QueuePush(q, root);//循环当队列为空时结束循环,当队列不为空时进行循环while (!QueueEmpty(q)){//将一个结点出队列BTNode* ret QueueFront(q);printf(%d , ret-data);QueuePop(q);//如果有左右结点的话按顺序入队列if (ret-left){QueuePush(q, ret-left);}if (ret-right){QueuePush(q, ret-right);}}Destory(q);
}3.判断是否为完全二叉树
3.1解题思路
这一道题目仍然是应用队列的知识
3.2代码实现
//判断是否为完全二叉树
bool BinaryTreeComplete(BTNode* n1)
{//先创建一个队列Queue q;Init(q);//先将二叉树中的数据全部插入到队列中//先将对头元素插入到队列中QueuePush(q, n1);while (!QueueEmpty(q)){BTNode* top QueueFront(q);QueuePop(q);if (top NULL){break;}//如果top不为空将top的左孩子结点和右孩子结点入队这样就保障了NULL结点的入队QueuePush(q, top-left);QueuePush(q, top-right);}//入队完成之后检查队列中的数据不能够存在一个NULL数据while (!QueueEmpty(q)){BTNode* top QueueFront(q);QueuePop(q);//如果存在不为空的数据返回falseif (top){Destory(q);return false;}}Destory(q);return true;
}
