怎样做好网站用户体验,申请网站空间,织梦网站更改网站的导航,建立网站需要注册公司吗前言 在前面我们学习了一些二叉树的基本知识#xff0c;了解了它的结构以及一些性质#xff0c;我们还用数组来模拟二叉树建立了堆#xff0c;并学习了堆排序#xff0c;可是数组结构的二叉树有很大的局限性#xff0c;平常我们用的最多树结构的还是链式二叉树#xff0c…前言 在前面我们学习了一些二叉树的基本知识了解了它的结构以及一些性质我们还用数组来模拟二叉树建立了堆并学习了堆排序可是数组结构的二叉树有很大的局限性平常我们用的最多树结构的还是链式二叉树因此本章我们来学习一些链式二叉树的相关知识。 普通的链式二叉树作用不大同时二叉树也不是经常用来存储数据因为存储数据用顺序表或链表就已经够了链式二叉树通常是为了后续更加高级的树结构做铺垫就如同单链表一样。不过基础不牢地动山摇本章的学习还是很重要的。 关于本章的代码可以访问这里获取 链式二叉树结构的实现一、创建一颗二叉树1、节点的定义2、节点的创建3、节点链接成树二、二叉树的遍历1、前序、中序以及后序遍历介绍2、前序、中序以及后序遍历的代码实现三、二叉树的层序遍历四、二叉树的节点个数以及高度1、二叉树的节点个数2、二叉树叶子节点的个数3、二叉树第k层节点个数4、树的高度5、二叉树查找值为x的节点五、二叉树的创建和销毁1、二叉树的创建2、二叉树的销毁3、判断一棵树是不是完全二叉树一、创建一颗二叉树
在学习二叉树的基本操作前需先要创建一棵二叉树然后才能学习其相关的基本操作。由于现在各位对二叉树结构掌握还不够深入为了降低大家学习成本此处手动快速创建一棵简单的二叉树快速进入二叉树操作学习等二叉树结构了解的差不多时我们反过头再来研究二叉树真正的创建方式。
我们来手动创建下面的二叉树
首先这里的二叉树每个节点都有一个数据域两个指针域于是我们可以用结构体去构建它们。
1、节点的定义
typedef int BTDataType;
typedef struct BinaryTreeNode
{BTDataType val;struct BinaryTreeNode* leftTree;struct BinaryTreeNode* rightTree;
}BTNode;结构体有了接下来我们就要去创建节点了把一个个节点创建出来然后我们挨个手动链接就能完成我们想要的二叉树了
2、节点的创建
//创建节点
BTNode* BuyNode(BTDataType val)
{BTNode* tmp (BTNode*)malloc(sizeof(BTNode));if (NULL tmp){perror(malloc fail:);return;}tmp-val val;tmp-leftTree tmp-rightTree NULL;return tmp;
}3、节点链接成树
int main()
{BTNode* n1 BuyNode(1);BTNode* n2 BuyNode(2);BTNode* n3 BuyNode(3);BTNode* n4 BuyNode(4);BTNode* n5 BuyNode(5);BTNode* n6 BuyNode(6);n1-leftTree n2;n2-leftTree n3;n1-rightTree n4;n4-leftTree n5;n4-rightTree n6;}这样上面的树我们就构建好了 注意上述代码并不是创建二叉树的方式真正创建二叉树方式后序详解重点讲解。
二、二叉树的遍历
1、前序、中序以及后序遍历介绍
学习二叉树结构最简单的方式就是遍历。所谓二叉树遍历(Traversal)是按照某种特定的规则依次对二叉树中的节点进行相应的操作并且每个节点只操作一次。访问结点所做的操作依赖于具体的应用问题。 遍历是二叉树上最重要的运算之一也是二叉树上进行其它运算的基础。
按照规则二叉树的遍历有前序/中序/后序的递归结构遍历
前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中间。后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后。
由于被访问的结点必是某子树的根所以N(Node、L(Left subtree和R(Right subtree又可解释为根、根的左子树和根的右子树。NLR、LNR和LRN分别又称为先根遍历、中根遍历和后根遍历。
我们来看对于上面的树其前序遍历的顺序 按照前序遍历的定义我们应该先遍历根再遍历左子树再遍历右子树。
我们从根节点开始遍历按照前序遍历的规则我们应该先访问根1然后访问左子树同时左子树2又是一个树按照前序遍历的规则我们应该先访问根节点再访问左子树于是我们要去访问3节点3节点访问完毕后我们又要去访问3节点的左子树3节点的左子树是是空树于是返回这时对于节点3这个树我们已经访问完了根节点与左子树了接下来就要去访问3的右子树了3节点的右子树是是空树于是返回。此时3节点已经访问完毕了。于是返回给2节点此时2节点等到3节点返回后2节点已经访问过了左子树接下来就要去访问2的右子树了2节点的右子树是是空树于是返回。
就这样层层递归对于这颗树的前半部分遍历顺序就是 1 2 3 NULL NULL NULL
对于右边的右子树按照同样的规则先遍历根再遍历左子树再遍历右子树。
我们便可以得到这颗树的前序遍历顺序是 1 2 3 NULL NULL NULL 4 5 NULL NULL 6 NULL NULL
我们来看对于上面的树其中序遍历的顺序 我们进入这颗树看到了1但是我们不能访问我们应该先访问左子树2进入这颗树看到了2但是我们不能访问我们应该先访问左子树3进入这颗树看到了3但是我们不能访问我们应该先访问左子树NULL左子树是NULL于是返回到3节点进行访问根根访问完毕于是访问访问3的右子树右子树是NULL于是返回到3节点3节点中序遍历完毕返回给2节点…
就这样层层递归,我们便可以得到这颗树的中序序遍历顺序是
NULL 3 NULL 2 NULL 1 NULL 5 NULL 4 NULL 6 NULL
我们来看对于上面的树其后序遍历的顺序
同理层层递归,我们便可以得到这颗树的后序序遍历顺序是 NULL NULL 3 NULL 2 NULL NULL 5 NULL NULL 6 4 1
2、前序、中序以及后序遍历的代码实现
//二叉树的前序遍历
void PrevOrder(BTNode* root)
{//判断是否为空空直接返回if (NULL root){return;}//前序遍历先遍历根printf(%d , root-val);//遍历完根再遍历左子树PrevOrder(root-leftTree);//遍历完左子树再遍历右子树PrevOrder(root-rightTree);
}对于上面的树遍历结果为 可以画出递归图帮助理解 中序遍历与前序遍历一样只不过打印的位置发生了变化。
//二叉树的中序遍历
void InOrder(BTNode* root)
{if (NULL root){return;}InOrder(root-leftTree);printf(%d , root-val);InOrder(root-rightTree);
}同理后续遍历只不过打印的位置发生了变化。
//二叉树的后续遍历
void PostOrder(BTNode* root)
{if (NULL root){return;}PostOrder(root-leftTree);PostOrder(root-rightTree);printf(%d , root-val);
}三、二叉树的层序遍历
二叉树的遍历方式有很多种除了先序遍历、中序遍历、后序遍历外还可以对二叉树进行层序遍历。
设二叉树的根节点所在层数为1层序遍历就是从所在二叉树的根节点出发首先访问第一层的树根节点然后从左到右访问第2层上的节点接着是第三层的节点以此类推自上而下自左至右逐层访问树的结点的过程就是层序遍历。
其流程图如下 对于二叉树的前序遍历中序遍历以及后续遍历我们都采用了递归的方式那是因为它们的遍历都可以将大问题分为小问题进而递归解决可是显然二叉树的层序遍历并不能用递归解决因为同一层内的节点都没有办法直接访问到彼此但是我们可以借助队列的特性来帮我们进行解决这个问题。
层序遍历的算法 首先我们可以先判断根节点是否为NULL如果为NULL就结束程序不为空先创建一个队列将根节点的地址存入队列里面然后获取队列里面的第一个元素利用这个元素将此元素的左右孩子节点也带入队列里面如果为空就不带入队列然后删除队头元素让队列里面的元素一个一个输出就行了。
//二叉树的层序遍历
void LevelOrder(BTNode* root)
{if (root NULL){return;}Queue q;QueueInit(q);QueuePush(q, root);int KLevel 1;while (!QueueEmpty(q)){BTNode* front QueueFront(q);printf(%d , front-val);QueuePop(q);if (front-leftTree ! NULL){QueuePush(q, front-leftTree);}if (front-rightTree ! NULL){QueuePush(q, front-rightTree);}}printf(\n);QueueDestroy(q);
}还有的二叉树层序遍历要求层序打印也不难办多加一个变量控制每一层的层数就行了。
//二叉树的层序遍历及层序打印
void LevelOrder2(BTNode* root)
{if (root NULL){return;}Queue q;QueueInit(q);QueuePush(q, root);int KLevel 1; //每一层的个数while (!QueueEmpty(q)){while (KLevel--){BTNode* front QueueFront(q);printf(%d , front-val);QueuePop(q);if (front-leftTree ! NULL){QueuePush(q, front-leftTree);}if (front-rightTree ! NULL){QueuePush(q, front-rightTree);}}//运行到这里说明上一层以经打印完了队列中的数据就是下一层要打印的个数。printf(\n);KLevel QueueSize(q);}QueueDestroy(q);
}四、二叉树的节点个数以及高度
1、二叉树的节点个数
利用递归思想二叉树的节点个数 根 左子树的节点个数 右节点的节点个数
// 二叉树节点个数
int TreeNodeSide(BTNode*root)
{if (NULL root){return 0;}return TreeNodeSide(root-leftTree) TreeNodeSide(root-rightTree) 1;
}2、二叉树叶子节点的个数
利用递归思想二叉树叶子节点的个数 左子树叶子节点的个数 右子树叶子节点的个数
判断是否是叶子节点的条件是左孩子 右孩子 NULL
//求叶子节点
int TreeLeftSize(BTNode*root)
{if (root NULL){return 0;}if (root-leftTree NULL root-rightTree NULL){return 1;}return TreeLeftSize(root-leftTree) TreeLeftSize(root-rightTree);
}3、二叉树第k层节点个数
利用递归思想 二叉树第k层节点个数 左子树第k-1层个数右子树的第k-1层个数 ①k 1 根的第k层左子树第k-1层个数右子树的第k-1层个数
②k 1 不为NULL就返回1为NULL就返回0。
//求第K层节点的个数
int TreeKLevelSize(BTNode* root, int k)
{if (NULL root){return 0;}if (k 1){return 1;}return TreeKLevelSize(root-leftTree, k-1) TreeKLevelSize(root-rightTree, k-1);
}4、树的高度
利用递归思想 树的高度 左子树的高度 与 右子树的高度 的较大者 1
//求树的高度
int TreeHeight(BTNode* root)
{if (NULL root){return 0;}int left_height TreeHeight(root-leftTree);int right_heigntTreeHeight(root-rightTree);return left_height right_heignt ?left_height 1 : right_heignt 1;
}5、二叉树查找值为x的节点
利用递归思想 二叉树查找值为x的节点 判断根节点是否是值为x的节点不是就去左子树去找再找不到就去右子树去找直到找不到。
// 二叉树查找值为x的节点
BTNode* TreeFind(BTNode* root, int x)
{if (NULL root){return NULL;}if (root-val x){return root;}BTNode* ret1 TreeFind(root-leftTree, x);if (ret1 ! NULL){return ret1;}BTNode* ret2 TreeFind(root-rightTree, x);if (ret2 ! NULL){return ret2;}return NULL;}五、二叉树的创建和销毁
通过前面的学习相信你对与递归解决二叉树的相关问题已经有了一定的理解二叉树本身就是递归定义的所以对于二叉树创建与销毁也应该是递归的。
1、二叉树的创建
给我们一个序列通过前序遍历的数组ABD##E#H##CF##G##构建二叉树 其中“#”表示的是空格空格字符代表空树。
算法我们可以判断二叉树的值是否应该为空来判断要不要创建一个节点来存储相应的值如果创建完节点我们可以递归创建根的左子树左子树创建完毕我们可以递归的去创建右子树左右子树都创建完毕了我们的树也就创建完毕了然后我们返回根节点的地址就行了。
//这里的pi是外面的int i0;的地址这里必须用为了让每一层递归中的i不一样
BTNode* TreeCreat(char* str, int* pi)
{if(str[(*pi)] #){(*pi);return NULL;}BTNode* root (BTNode*)malloc(sizeof(BTNode));root-ch str[(*pi)];(*pi);root-left TreeCreat(str, pi) ;root-right TreeCreat(str, pi);return root;
}2、二叉树的销毁
二叉树的销毁我们最好采用后序遍历的方式因为采用前序遍历我们会先销毁根节点根节点被销毁了我们就很难找到左右节点了这样就会导致内存泄漏同理如果采用中序遍历中间销毁根就会很难找到右节点了。
算法采用递归要销毁一个树就先销毁这棵树的左子树再销毁右子树最后再销毁根。
//二叉树的销毁
void TreeDestory(BTNode* root)
{if (root NULL){return;}TreeDestory(root-leftTree);TreeDestory(root-rightTree);free(root);//root NULL; 可以不写这里root只是形参,改变root不会影响外面原本的指针
}这里的是BTNode* root销毁完了还要在外面手动将root置空。如果我们传递BTNode** root就可以解决这个问题你可以实现一下。
3、判断一棵树是不是完全二叉树
判断一棵树是不是完全二叉树利用递归好像并不能解决问题但是我们遍历一棵树的方式并不是只有递归的前中后序我们可以利用层序遍历的方式来判断一棵树是不是完全二叉树。
算法我们可以层序遍历整个树并将所有节点的地址都存放到队列里面NULL也放然后从队列里面取数据拿到第一个NULL后判断后面的节点是不是都是NULL,如果都是NULL说明是完全二叉树。
//判断一棵树是不是完全二叉树
bool TreeComplete(BTNode* root)
{Queue q;QueueInit(q);if (root){QueuePush(q, root);}while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//遇到NULL,跳出去进行进一步判断。if (front NULL){break;}else{QueuePush(q, front-leftTree);QueuePush(q, front-rightTree);}}//判断while (!QueueEmpty(q)){BTNode* front QueueFront(q);QueuePop(q);//如果队列里面还有非NULL元素说明非完全二叉树if (front ! NULL){QueueDestory(q);return false;}}QueueDestory(q);return true;
}
