购物网站主页模版,深圳网站建设toolcat,江门桂城网站建设,旅游公司网页设计目录 1.链式二叉树概念
2.链式二叉树的实现
3.先序遍历
4.中序遍历
5.后序遍历
6.求链式二叉树的结点个数
7.链式二叉树的叶子结点个数
8.求二叉树的k层的结点个数
9.链式二叉树求深度
10.求值为x的结点
11.链式二叉树的销毁
12.二叉树的层序遍历
13.判断二叉树是否…
目录 1.链式二叉树概念
2.链式二叉树的实现
3.先序遍历
4.中序遍历
5.后序遍历
6.求链式二叉树的结点个数
7.链式二叉树的叶子结点个数
8.求二叉树的k层的结点个数
9.链式二叉树求深度
10.求值为x的结点
11.链式二叉树的销毁
12.二叉树的层序遍历
13.判断二叉树是否为完全二叉树 1.链式二叉树概念 链式二叉树和名字一样是使用链式结构实现的二叉树结点之间使用指针连接起来的。之前的二叉树是使用顺序结构进行存储的不同于顺序存储链式结构可以将各结点之间的关系表示清晰。
2.链式二叉树的实现
二叉树首先肯定要有根节点的然后是左右两个孩子结点分别叫做left和right即可通过一个结构体来实现链式二叉树。 如图所示一个链式二叉树的结点就是实现好了。 我们要自己手动将结点连接起来这就实现了一个完全二叉树。
3.先序遍历 简单的几行代码就实现好了这就是递归的魅力所在。
接下来分析一下
递归是一定要有终止条件的如果没有终止条件的话递归就会陷入死循环并且占用的大量的函数栈帧先序遍历的终止条件就是根节点为NULL此时就结束递归不会进入到后面的步骤如果这个根结点不是空指针那就打印这个结点的data然后进入左子树进行先序遍历如果左子树的根节点不是空指针那就打印左子树的根结点的值然后继续进入左子树的左子树一直走到左子树为空然后此时就遍历右子树进而就实现了链式二叉树的先序遍历。
4.中序遍历 过程同先序遍历一样只是打印的结点不同这里不过多讲解。
5.后序遍历 同上。
6.求链式二叉树的结点个数
同样这里也是用到了递归的思想仅仅需要简单的几行代码就实现了结点的计算。 终止条件还是rootNULL根结点是空结点之后说明此时就已经走到了一个结点的空指针的位置没有必要计算的直接返回0即可下面的return1是为了算上开始的结点需要1然后就加上这个结点的左子树和右子树就实现了递归来求的链式二叉树的结点个数。
7.链式二叉树的叶子结点个数
叶子结点就是有一个父节点然后他的左结点是空指针他的又结点也是空指针那这个结点就是叶子结点要求的叶子结点个数也是通过递归实现的。 终止条件是有两个的一个是rootNULL,另一个就是左右结点都是空指针。
分析一下这两个终止条件rootNULL,这个结点已经是空指针了没有加上去的意义那肯定会有人有疑问了根结点的左右结点是空指针了怎么会向下递归呢那就大错特错了如果一个结点只有一个子结点的话两个结点都进入空结点返回0非空返回1这是其中一个终止条件的意义另一个就很明显了就是左右结点是空就返回1没有什么过多需要解释的如果这个结点不符合上述两个终止条件的话就返回他的左子树他的右子树。
8.求二叉树的k层的结点个数 k是层数第一个终止条件就不用说了重点是k1时返回1k不等于1就返回左子树的k-1加上右子树的k-1,比如第二层我们传入k2不会终止然后进入左子树左子树的k1右子树的k也等于1加起来就是2.
9.链式二叉树求深度 求深度肯定不可能只求一边的深度就返回要进行比较的所以将左子树和右子树进行比较才能返回。
10.求值为x的结点 如果root的data等于x就直接返回这个data的地址了不等于的就看左子树寻找左子树是否有等于这个值的结点然后判断如果不是空指针那一定是找到了直接返回地址右子树同理。
11.链式二叉树的销毁 需要修改指针的值那就要取出指针的地址下面的同样是递归不过多讲述。
12.二叉树的层序遍历 需要进行层序遍历这里需要借助队列来实现了首先肯定是要创建一个队列的然后队列进行初始化写一个循环只要队列不为空就一直入队列队列是先入先出的特点入队列之后直接打印然后队列删除队头然后左子树右子树入队列接着打印一直到队列为空此时就实现了队列的层序遍历。
13.判断二叉树是否为完全二叉树 还需借助队列来完场创建队列将root入队获取队列队头然后队头删除然后就一直入队如果此时队头是空指针就直接跳出循环了因为已经是空指针了肯定没办法获取他的左右孩子。那么就进入下一个循环循环条件是队列非空因为如果是二叉树在取完最后一个结点之后队列中剩下的都是空结点如果不是完全二叉树的话里面就会剩下非空的一直取到队列为空如果取到了非空就直接返回false一直走完循环结束到最后没有找到那就直接返回true,说明这是一个完全二叉树。
