网站上怎么做微信支付接口,电子贺卡怎么制作,网站制作技术支持,网页设计与制作教程第三版张兵义前言
我们在前面学习了使用数组来实现二叉树#xff0c;但是数组实现二叉树仅适用于完全二叉树#xff08;非完全二叉树会有空间浪费#xff09;#xff0c;所以我们本章讲解的是链式二叉树#xff0c;但由于学习二叉树的操作需要有一颗树#xff0c;才能学习相关的基本…前言
我们在前面学习了使用数组来实现二叉树但是数组实现二叉树仅适用于完全二叉树非完全二叉树会有空间浪费所以我们本章讲解的是链式二叉树但由于学习二叉树的操作需要有一颗树才能学习相关的基本操作由于这只是开头为了降低学习的成本所以我们手动的来创建一颗普通的二叉树等到本文的后面再讲解真正的创建
二叉树的基本结构
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType _data;struct BinaryTreeNode* _left;struct BinaryTreeNode* _right;
}BTNode;创建新结点
BTNode*BuyNode(BTDataType x)
{BTNode* Node (BTNode*)malloc(sizeof(BTNode));if (Node NULL){perror(malloc fail:);exit(1);}Node-_data x;Node-_left Node-_right NULL;
}创造树
BTNode* CreateBinaryTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);BTNode* node7 BuyNode(7);BTNode* node8 BuyNode(8);node1-_left node2;node2-_left node3;node3-_right node4;node1-_right node5;node5-_right node6;node6-_left node7;node6-_right node8;return node1;
}int main()
{BTNode* root CreateBinaryTree();return 0;
}最后效果如图
在完成二叉树的基本操作之前我们先在这里简单的回顾一下二叉树的基本概念。 二叉树只有两个状态
空树非空由根结点根节点的左子树根结点的右子树组成
从图中可以看出二叉树定义是递归形式的根结点的左孩子也能看作根其左右孩子以及对于的联系也能看成左右子树根的右孩子同理所以我们下面的操作都是通过递归来实现。
以下所有的操作都会使用上面手搓的树
二叉树的遍历
所谓前中后序的遍历就是根结点的先后访问顺序所以前中后序遍历也叫前根、中根、后根遍历。
前序前根的访问顺序根、左子树、右子树中序中根的访问顺序左子树、根、右子树后序后根的访问顺序左子树、右子树、根
这里先将遍历的原因是后续的操作都会用到遍历的思路。
前序遍历
一般说这个树的前序遍历是[1, 2, 3, 4, 5, 6, 7, 8] 但这不是最详细的表达最详细的表达是[1, 2, 3, NULL, 4, NULL, NULL, NULL, 5, NULL, 6, 7, NULL, NULL, 8, NULL, NULL]。 3 后面的NULL其实是 3 的左孩子4 后面俩个NULL代表的是 4 的左孩子和右孩子而 5 前面的NULL代表的是 2 的右孩子5 后面的NULL代表 5 的左孩子7 和 8 后面的NULL都是代表他们的左右孩子。 中序
一般说这个树的中序遍历是[3, 4, 2, 1, 5, 7, 6, 8 ]; 实际则是[N, 3, N, 4, N, 2, N, 1, N, 5, N, 7, N, 6, N, 8, N]N代替NULL 由于是先访问左子树所以第一个真正被遍历的一定是NULL。 3 前面的N就是 3 的左孩子4 前后的 N则代表的是 4 的左右孩子2 后面的N代表的是 2 的右孩子5 前面的N代表 5 的左孩子7 和 8 前后的N都代表他们的左右孩子。 后序
一般[4, 3, 2, 7, 8, 6, 5, 1] 实际则是[N, N, N, 4, 3, N, 2, N, N, N, 7, N, N, 8, 6, 5, 1]N代替NULL 第一个N是 3 的左孩子第二第三个N是 4 的左右孩子3 后面的N是 2 的右孩子而 2 后面的第一个N是 5 的左孩子7 和 8 的前俩个N都是代表他们的左右孩子 注意无论是哪种遍历孩子之间的顺序一定是先左孩子再是右孩子。
层序遍历
就是我们正常的思维一层一层、从左到右的依次遍历这种遍历方式叫广度优先遍历BFS而前三种遍历方式叫深度优先遍历DFS。
层序遍历需要依靠队列来实现。
代码实现
前中后序的遍历的大体相同只是打印的位置不同
// 二叉树前序遍历
void BinaryTreePrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}前序时printf的位置在前面printf(%d , root-_data);BinaryTreePrevOrder(root-_left);中序时printf的位置在中间printf(%d , root-_data);BinaryTreePrevOrder(root-_right);后续时printf的位置在末尾printf(%d , root-_data)
}用图像讲解递归过程 右子树的递归过程大体相同注意实际情况并不会开那么多的空间而是当你使用完返回再使用的时候是将原来的空间给重新利用了。
层序遍历的实现
在完成层序遍历之前我们需要有队列这个数据结构我们可以直接将以前的代码拿过来具体代码在数据结构【队列】
具体思路是先创建一个队列将二叉树的根结点存放到队列里每遍历一个结点就删掉这个在队列里的结点删掉的同时将该结点的左右孩子存放到队列内部这样依次往复。
这里的类型是结点的类型并且存放的是指针所以要带个*号
typedef struct BinaryTreeNode* QUEUEDATA;typedef struct QNode
{QUEUEDATA _val;struct QNode* _next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;层序遍历代码
// 层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{Queue* q (Queue*)malloc(sizeof(Queue));QueueInit(q);//先把root入到队列QueuePush(q, root);//当队列尾空时就代表以及打印完了while (!QueueEmpty(q)){//取队头数据BTNode*tmp QueueFirst(q);//然后删除数据我只是操作队列内部并没有动原来的二叉树QueuePop(q);//当为空时不加数据这就能应对根结点是空时的情况就不需要在外面再做一次判断if (tmp NULL){printf(N );}//非空将左右孩子添加到队列else{printf(%d , tmp-_data);QueuePush(q,tmp-_left);QueuePush(q,tmp-_right);}}
}二叉树的计算
本文计算关于树的计算有四个
计算树结点的个数计算树的叶子结点个数计算第k层的节点个数计算树的高度
计算节点个数
这就很简单了就是左右子树加自己但每个孩子又可以分为根左子树右子树当根等于空时返回0就可以了。
// 二叉树节点个数
int BinaryTreeSize(BTNode* root)
{if (root NULL){return 0;}return BinaryTreeSize(root-_left) BinaryTreeSize(root-_right) 1;
}这里的1就是加自己当你来到下面那个return时就代表该节点并不是空节点。
计算叶子节点个数
简单的回顾一下叶子节点就是左右孩子都为空的节点。 所以就可以判断当左右孩子都为空时就返回 1。
// 二叉树叶子节点个数
int BinaryTreeLeafSize(BTNode* root)
{if (root NULL){return 0;}if (root-_left NULL root-_right NULL){return 1;}return BinaryTreeLeafSize(root-_left) BinaryTreeLeafSize(root-_right);
}计算第k层节点个数
这个也能很好的用递归来解决第k层是对于根节点来说的但对于根节点的下一层来说第k层其实是第k-1层所以可以一直减下去直到当k1时return 1。
// 二叉树第k层节点个数
int BinaryTreeLevelKSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BinaryTreeLevelKSize(root-_left, k - 1) BinaryTreeLevelKSize(root-_right, k - 1);
}计算树的高度
那我就比较左子树和右子树的高度比较出结果后再加自身的高度比较出的高度1 结束递归的条件就是当我的子树为空返回0。
// 二叉树的高度
int BinaryHeight(BTNode* root)
{if (root NULL){return 0;}return BinaryHight(root-_left) BinaryHight(root-_right) ? BinaryHight(root-_left) 1: BinaryHight(root-_right) 1;
}这样也可以但是如果用这个去做利扣的题是无法通过的并不是因为程序结果错误而是因为栈溢出。 看看为什么会栈溢出我要比较出两个子树的长度就一定会运行 return BinaryHight(root-_left) BinaryHight(root-_right) ? BinaryHight(root-_left) 1: BinaryHight(root-_right) 1; 这有没有发现我并没有记录比较高的值我辛辛苦苦递归很多次才得到的左右子树中较高的子树当我要返回高度的时候诶我前面的数是啥所以我就又要进行 BinaryHight(root-_left) 1或者BinaryHight(root-_right) 1这样我又会进行递归再递归比较然后再递归返回值-递归比较这样一直下去直到最低层root NULL。
所以我们需要变量来记录两颗子树的高度这样我们再比较的时候就不会重复递归了。 // 二叉树的高度
int BinaryHeight(BTNode* root)
{if (root NULL){return 0;}//记录左树的高度int L BinaryHight(root-_left);//记录右树的高度int R BinaryHight(root-_right);//比较出较高的加上自己这一层的高度return (L R ? L : R) 1;
}二叉树的创建和销毁
二叉树的创建前序
这题是使用前序来创建二叉树
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi);#号代表空a是数组n是长度pi是下标 先创建父亲节点然后左子树 - 创建左子树当中的父亲节点然后创建左子树 —直到这时的数据是#返回NULL创建右子树右子树创建完函数自然结束回到上一层让上一层来创建右子树。 当pi等于n的时候就代表已经遍历完该数组了这条数组里的数据已经被我创建成一个二叉树了这时候就返回NULL这个判断放在函数的开头。
// 通过前序遍历的数组ABD##E#H##CF##G##构建二叉树
BTNode* BinaryTreeCreate(BTDataType* a, int n, int* pi)
{
//当下标与长度相等返回NULLif (*pi n){return NULL;}if (a[*pi] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));//先创建根节点再创建左子树再创建右子树root-_data a[(*pi)];root-_left BinaryTreeCreate(a, n, pi);//先创建左子树root-_right BinaryTreeCreate(a, n, pi);//再创建右子树return root;//返回根节点
}二叉树的销毁后序
这题我们采用后序来删除是因为后续并不需要记录节点是从底层一点一点销毁节点当我左右子树的节点都销毁了或者都为NULL才销毁我的根节点。
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)既然是销毁那么就会修改原来的值所以我们就传二叉树根节点的地址。
// 二叉树销毁
void BinaryTreeDestory(BTNode** root)
{if (root NULL || *root NULL){return;}BinaryTreeDestory((*root)-_left);//先销毁左子树BinaryTreeDestory((*root)-_right);//再销毁右子树//当左右节点都被销毁或者都为NULLfree(*root);//最后再销毁根节点
}结语
到这里二叉树的基本函数就讲完啦。
最后感谢您能阅读完此片文章如果有任何建议或纠正欢迎在评论区留言也可以前往我的主页看更多好文哦(点击此处跳转到主页)。 如果您认为这篇文章对您有所收获点一个小小的赞就是我创作的巨大动力谢谢
