网站建设sem账户搭建,小程序开发公司十大排名,自己做网站赚钱案例,jekyll做公司网站实现链式结构二叉树
链式结构就是由一个一个的节点组成。 ⽤链表来表⽰⼀棵⼆叉树#xff0c;即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成#xff0c;数据域和左右指针域#xff0c;左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储…实现链式结构二叉树
链式结构就是由一个一个的节点组成。 ⽤链表来表⽰⼀棵⼆叉树即⽤链来指⽰元素的逻辑关系。 通常的⽅法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别⽤来给出该结点左孩⼦和右孩⼦所在的链结点的存储地址。
二叉树节点结构的定义
typedef char BTDataType;
//二叉树结点结构的定义
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
关于二叉树的遍历
想要实现链式结构二叉树就一定要掌握二叉树的遍历相关的知识二叉树的遍历分为前序遍历中序遍历和后序遍历。
前序遍历访问顺序为根结点、左⼦树、右⼦树根左右。
假如我现在有下图二叉树那么前序遍历的顺序就为:
A,B,D,NULL,NULL,NULL,C,E,NULL,NULL,F,NULL,NULL.
我们从A开始遍历A是根他的左孩子是B但在左子树中B也是根继续往下遍历他的左孩子是d,D与B同理我们继续往下遍历NULL为空然后我们就往上走D的左孩子遍历完成后我们遍历D的右孩子也是NULL那么此时对于D这颗左子树我们已经便利完成再继续往上走B这颗子树的左孩子和根节点我们已经遍历完成就剩下它的右孩子NULL此时整个左子树我们都遍历完成了再去遍历右子树。右子树与左子树同理便利的顺序为C,E,BULL,NULL,F,NULL,NULL。如果大家还有不懂可以在评论区问我这里就不再赘述了。 中序遍历访问顺序为左⼦树、根结点、右⼦树左根右。 假如我现在有下图二叉树那么中序遍历的顺序就为:
NULL, D, NULL, B, NULL, A, NULL, E, NULL, C, NULL, F, NULL. 后序遍历访问顺序为左⼦树、右⼦树根结点左右根。 假如我现在有下图二叉树那么后序遍历的顺序就为:
NULL, NULL, D, NULL, B, NULL, NULL, E, NULL, NULL, F, C, A. 了解二叉树的遍历后我来代码实现一下。开启递归的暴力美学
老规矩我们创建三个项目分别是Tree.hTree.ctest.c
首先我们先手动实现一个二叉树
代码test.c
//手动构造一棵二叉树
BTNode* CreateTree()
{BTNode* nodeA buyNode(A);BTNode* nodeB buyNode(B);BTNode* nodeC buyNode(C);BTNode* nodeD buyNode(D);BTNode* nodeE buyNode(E);BTNode* nodeF buyNode(F);nodeA-left nodeB;nodeA-right nodeC;nodeB-left nodeD;nodeC-left nodeE;nodeC-right nodeF;return nodeA;
}
前序遍历代码实现
//前序遍历 根左右
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-data);PreOrder(root-left);PreOrder(root-right);
}
前序遍历的过程
前序遍历的顺序为根左右我们首先要判断根是不是空如果根为空我们就不需要遍历了如果根不为空我们就要先把根打印出来打印完成后我们就又要递归调用root-left,也就是B,B这个节点不为空我们把B的左孩子D打印出来打印完成后继续递归D的左孩子D的左孩子为空就满足rootNULL这个条件打印一下NULL打印完成后returnreturn就意味函数栈帧将会释放也就意味4这个代码执行完了我们回到上一级3D的左孩子打印完了继续递归打印右孩子。此刻D的左右孩子和它自己都已经打印完成就意味着D这个函数已经调用完了我们就要释放函数栈帧继续向上走。回到2继续打印B的右孩子操作6打印完NULL后就要return释放函数栈帧回到2B的左右孩子和它自身已经打印完了释放函数栈帧回到AA的左孩子和它自身打印完了继续打印它的右孩子C所以这里的参数root就是CC不为空我们接下来打印C里面的数据。递归调用C打印C的左孩子EE不为空我们就打印E里面的数据E的左孩子为空我们打印NULL然后return 释放函数栈帧。然后再去递归E的右孩子E的右孩子也是空所以再打印一个NULL。E的左右孩子和它本身都打印成功后释放函数栈帧返回C继续递归C的右孩子F与E同理递归完F后释放函数栈帧回到CC的全部内容也打印完成现在要销毁函数栈帧然后再回到AA的全部内容也打印完成也要销毁函数栈帧。A的函数栈帧销毁就意味着我们的遍历完成了所有通过递归创建的的函数栈帧都销毁完了。 测试结果 中序遍历代码实现
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}
遍历过程
首先这里传过来的根节点A判断A是不是空。不为空就要去递归A。A的左孩子就是是B这个节点所以这里创建了一个B的函数栈帧判断B的函数栈帧为空吗不为空那我们继续去调用。B的left就是D。所以这里我们创建了一个函数栈帧参数为D,D不为空再继续去递归它的左孩子在这里创建新的函数栈帧参数为NULL。在参数为NULL的函数栈帧中参数为空我们就打印空。然后return当前函数栈帧被销毁。销毁之后我们回到根节点DD的函数栈帧的左孩子我们已经递归完了接下来我们要打印一下DD打印完了之后接下来我们要递归调用D的右孩子那么D的右孩子为NULL我们就打印一下NULL。打印完了之后要return也就意味着NULL这个函数栈帧我们已经调用完了。然后我们销毁这个函数栈帧然后再继续回到D这个函数。D这个函数里面所有的代码都已经执行完了那么函数战争要销毁回到了B的函数栈帧。再去递归B的右孩子我们又要去创建一个参数为NULL的函数栈帧然后打印NULL再继续return销毁函数栈帧回到B。那么B所有内容我们已经递归完了也就意味着这一行代码就已经执行完了那么接下来我们要打印当前A节点里的值然后再继续去递归A的右子树那么A的的的右子树在这里创建了一个函数栈帧参数为CC不为空我们就在这个函数栈帧里面继续递归它的左孩子。C的左孩子是E我们就创建参数为E的函数栈帧E不为空再继续递归它的左孩子它的左孩子创建函数栈帧的参数NULL那我们就打印NULL然后再让它return然后销毁NULL这个函数栈帧。在E这个函数栈帧中它的左孩子已经递归完了接下来是要打印根节点E。接下来是右孩子继续递归创建函数栈帧为NULL再打印NULL然后return然后让函数栈帧消毁。E的全部内容递归完了那么就要销毁它的函数栈帧然后回到C接下来递归它的右孩子FF不为空再继续创建函数栈帧参数NULL为NULL我就打印NULL。然后直接return销毁函数栈帧。F的左孩子我已经递归完了接下来我们要打印一下当前节点里的值F F打印完了之后,在F这个函数栈帧中继续递归它的它的右孩子创建一个参数为NULL的函数栈帧然后打印NULL直接return销毁函数栈帧。回到FF的全部内容我已经打印完了再继续往上回溯到C这个函数栈帧C里面的所有内容都已经递归完成再继续回溯到A这个函数栈帧中A的全部内容也处理完了销毁函数栈帧至此整个递归完成。 测试结果: 后序遍历代码实现
后续遍历的过程大家可以自己思考一下有什么问题打在评论区。
//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);
}
测试结果: 求二叉树结点的个数
求整个二叉树节点的个数只需要根节点左子树的节点个数右子树的节点个数。 左子树又是一颗子树也分左右子树所以左子树的节点个数也是 1左子树的节点个数右子树的节点个数。右子树同理。这就又是一个递归问题。 代码
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root) {if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}
测试结果: 求二叉树叶子节点的个数
叶子节点该节点的左孩子和右孩子都为空 我们依然可以把这个二叉树分成左右子树然后依次求左子树叶子结点的个数和右子树叶子结点的个数然后相加。还是使用递归。
代码:
// ⼆叉树叶⼦结点个数
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层结点的个数
假设我们要找的是k2层结点的个数。首先我们要判断根节点为不为空不为空我们继续遍历 我们可以递归让k--找到我们要找的那一层。然后遍历让左子树节点的个数右子树节点的个数就是第k层总的节点的个数。 代码
// ⼆叉树第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);
}
测试结果 求二叉树的深度/高度
注意 不平衡的二叉树 的深度按照最大的深度计算 如下图 二者的深度都为3. 根节点的层次左子树和右子树中最大的层次。 代码
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);return 1 (leftDep rightDep ? leftDep : rightDep);
}
测试结果 二叉树查找值为x的节点
首先我们需要判断根节点是否为空不为空我们就进行遍历使用上述讲过的哪种都可以这里我们使用先序遍历。先遍历左子树如果找到了就直接返回如果没找到就继续遍历右子树。 代码
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryTreeFind(root-right, x);if (rightFind){return rightFind;}return NULL;
}
测试结果: 二叉树的销毁
二叉树是由链表组成而链表是由节点组成所以我们销毁节点即可那么我们用什么方法销毁节点呢
我们可以使用前面讲的后序遍历边遍历边销毁那为什么不使用前序遍历或者后序遍历呢
如果我们的根先被销毁了是不是就不容易找到它的左右孩子啊所以我们使用后序遍历。
代码
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root) {if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}
测试结果 全部代码
Tree.h
#includestdio.h
#includestdlib.h
#includeassert.htypedef char BTDataType;
//二叉树结点结构的定义
typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;
//前序遍历
void PreOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root);
// ⼆叉树叶⼦结点个数
int BinaryTreeLeafSize(BTNode* root);
// ⼆叉树第k层结点个数
int BinaryTreeLevelKSize(BTNode* root, int k);
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root);
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x);
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root); Tree.c
#includeTree.h//前序遍历 根左右
void PreOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}printf(%c , root-data);PreOrder(root-left);PreOrder(root-right);
}
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}InOrder(root-left);printf(%c , root-data);InOrder(root-right);
}
//后序遍历--左右根
void PostOrder(BTNode* root)
{if (root NULL){printf(NULL );return;}PostOrder(root-left);PostOrder(root-right);printf(%c , root-data);
}
// ⼆叉树结点个数
int BinaryTreeSize(BTNode* root) {if (root NULL){return 0;}return 1 BinaryTreeSize(root-left) BinaryTreeSize(root-right);
}
// ⼆叉树叶⼦结点个数
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层结点个数
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);
}
//⼆叉树的深度/⾼度
int BinaryTreeDepth(BTNode* root)
{if (root NULL){return 0;}int leftDep BinaryTreeDepth(root-left);int rightDep BinaryTreeDepth(root-right);return 1 (leftDep rightDep ? leftDep : rightDep);
}
// ⼆叉树查找值为x的结点
BTNode* BinaryTreeFind(BTNode* root, BTDataType x)
{if (root NULL){return NULL;}if (root-data x){return root;}BTNode* leftFind BinaryTreeFind(root-left, x);if (leftFind){return leftFind;}BTNode* rightFind BinaryTreeFind(root-right, x);if (rightFind){return rightFind;}return NULL;
}
// ⼆叉树销毁
void BinaryTreeDestory(BTNode** root) {if (*root NULL){return;}BinaryTreeDestory(((*root)-left));BinaryTreeDestory(((*root)-right));free(*root);*root NULL;
}
tese.c
#includeTree.hBTNode* buyNode(BTDataType x)
{BTNode* node (BTNode*)malloc(sizeof(BTNode));node-data x;node-left node-right NULL;return node;
}
//手动构造一棵二叉树
BTNode* CreateTree()
{BTNode* nodeA buyNode(A);BTNode* nodeB buyNode(B);BTNode* nodeC buyNode(C);BTNode* nodeD buyNode(D);BTNode* nodeE buyNode(E);BTNode* nodeF buyNode(F);nodeA-left nodeB;nodeA-right nodeC;nodeB-left nodeD;nodeC-left nodeE;nodeC-right nodeF;return nodeA;
}
void test() {BTNode* root CreateTree();//PreOrder(root);//InOrder(root);//PostOrder(root);//printf(size:%d\n, BinaryTreeSize(root));//printf(leaf size:%d\n, BinaryTreeLeafSize(root));//printf(K size:%d\n, BinaryTreeLevelKSize(root, 2));//printf(K size:%d\n, BinaryTreeLevelKSize(root, 3));//printf(depth:%d\n, BinaryTreeDepth(root));BTNode* find BinaryTreeFind(root, Z);if (find NULL){printf(未找到\n);}else {printf(找到了\n);}BinaryTreeDestory(root);
}
int main() {test();return 0;
} 祝大家生活愉快。
