公司介绍网站源码,wordpress进入数据库,建立企业网站的形式有哪几种,搜索引擎关键词优化目录
一#xff0c;二叉树的链式结构
二#xff0c;二叉链的接口实现 1#xff0c;二叉链的创建 2#xff0c;接口函数 3#xff0c;动态创立新结点 4#xff0c;创建二叉树 5#xff0c;前序遍历 6#xff0c;中序遍历 7#xff0c;后序遍历
三#xff0c;结点个…目录
一二叉树的链式结构
二二叉链的接口实现 1二叉链的创建 2接口函数 3动态创立新结点 4创建二叉树 5前序遍历 6中序遍历 7后序遍历
三结点个数以及高度等 1接口函数 2结点个数 3叶子结点个数 4二叉树高度 5二叉树第k层结点个数 6二叉树查找值为x的结点 一二叉树的链式结构 二叉树的链式存储结构是指用链表来表示一棵二叉树即用链来指示元素的逻辑关系 通常的方法是链表中每个结点由三个域组成数据域和左右指针域左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。 链式结构又分为二叉链和三叉链这里我们学习二叉链 二叉树是
1空树
2非空根节点根节点的左子树、根节点的右子树组成的。 从图示中可以看出二叉树定义是递归式的也称递归树因此后序基本操作中基本都是按照该概念实现的 二叉链结构图示 二二叉链的接口实现 1二叉链的创建
typedef int BTDataType;
//二叉链
typedef struct BinaryTreeNode
{BTDataType data; // 当前结点值域 struct BinaryTreeNode* left; // 指向当前结点左孩子struct BinaryTreeNode* right; // 指向当前结点右孩子
}BTNode;
首先创建一个结构体表示二叉链data是当前结点的值域BTDataType是储存的值的数据类型
left是指向当前结点左孩子right是指向当前结点右孩子
这里的BTDataType是int的重命名也可以说是数据类型的重命名这样统一化方便后续更改 2接口函数
//动态创立新结点
BTNode* BuyNode(BTDataType x);
//创建二叉树
BTNode* GreatBTree();
//前序遍历
void PrevOrder(BTNode* root);
//中序遍历
void InOrder(BTNode* root);
//后序遍历
void PostOrder(BTNode* root);
这是以上要实现的接口函数 3动态创立新结点
//动态创立新结点
BTNode* BuyNode(BTDataType x)
{BTNode* newnode (BTNode*)malloc(sizeof(BTNode));assert(newnode);newnode-data x;newnode-left NULL;newnode-right NULL;return newnode;
}
后面创立新结点时直接调用此函数一定要向堆区申请空间这样函数结束空间会保留不会被回收
将data赋新值left与right都指向空再返回结点指针即可 4创建二叉树
//创建二叉树
BTNode* GreatBTree()
{BTNode* node1 BuyNode(1);BTNode* node2 BuyNode(2);BTNode* node3 BuyNode(3);BTNode* node4 BuyNode(4);BTNode* node5 BuyNode(5);BTNode* node6 BuyNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return node1;
}
然后我们申请结点来构造二叉树通过链接将新结点链接起来
创建的二叉树结构图示如下 5前序遍历
//前序遍历
void PrevOrder(BTNode* root)
{if (root NULL){printf(N );return;}printf(%d , root-data);PrevOrder(root-left);PrevOrder(root-right);
}
二叉树的前序中序后续遍历都是同一种思路 1. 前序遍历(Preorder Traversal 亦称先序遍历)——根结点----左子树---右子树 2. 中序遍历(Inorder Traversal)——左子树---根结点---右子树 3. 后序遍历(Postorder Traversal)——左子树---右子树---根结点 这里要用到递归思想这里NULL用N表示建议画图来理解一层一层遍历下去 前序遍历
先访问根结点1然后访问其左子树2打印 1
此时根结点为2然后访问其左子树3打印1 2
此时根结点为3然后访问其左子树NULL打印1 2 3
此时根结点为NULLreturn NULL到3然后访问3的右子树NULL打印1 2 3 N
此时根结点为NULLreturn NULL到3此时对3也就是对2的左子树的访问结束了然后访问2的右子树NULL)打印1 2 3 N N
此时根结点为NULLreturn NULL到2此时对2也就是对1的左子树访问结束了然后访问1的右子树4打印1 2 3 N N N
此时根结点为4然后访问其左子树5打印1 2 3 N N N 4
此时根结点为5然后访问其左子树NULL打印1 2 3 N N N 4 5
此时根结点为NULLreturn NULL到5然后访问5的右子树NULL打印1 2 3 N N N 4 5 N
此时根结点为NULLreturn NULL到5此时对5也就是对4的左子树的访问结束了然后访问4的右子树6打印 1 2 3 N N N 4 5 N N
此时根结点为6然后访问其左子树NULL打印1 2 3 N N N 4 5 N N 6
此时根结点为NULLreturn NULL到6然后访问6的右子树NULL打印1 2 3 N N N 4 5 N N 6 N
此时根结点为NULLreturn NULL到6此时对6也就是对4的右子树的访问结束了此时对4也就是对1的右子树的访问结束了此时对1的访问也结束了前序遍历也就结束了打印1 2 3 N N N 4 5 N N 6 N N
图解思路示例 BTNode* root GreatBTree();
//前序遍历
PrevOrder(root); 这就是前序遍历 6中序遍历
//中序遍历
void InOrder(BTNode* root)
{if (root NULL){printf(N );return;}InOrder(root-left);printf(%d , root-data);InOrder(root-right);
}
中序遍历左子树---根结点---右子树
跟前序遍历思路一致就是换了一下访问的顺序按照前序遍历的思路来就完事了
//中序遍历
InOrder(root);
printf(\n); 7后序遍历
//后序遍历
void PostOrder(BTNode* root)
{if (root NULL){printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d , root-data);
}
后序遍历左子树---右子树---根结点
思路还是一致的就是换了一下访问顺序前中后序遍历的思路都是一致的只要搞清楚其中一个就全部拿捏了
//后续遍历
PostOrder(root);
printf(\n); 这里对二叉链的基础遍历就实现完全了有人说还有一个层序遍历这个遍历需要用到队列目前C语言阶段实现太过于繁琐后序博主会补上 三结点个数以及高度等 像此类问题也都是递归问题更加看重我们对函数栈帧的理解 1接口函数
//结点个数
int SumNode(BTNode* root);
//叶子结点个数
int LeafNode(BTNode* root);
//二叉树高度
int HeightTree(BTNode* root);
//二叉树第k层结点个数
int BTreeLeveSize(BTNode* root, int k);
//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x);
以上是要实现的函数 2结点个数
//结点个数
int SumNode(BTNode* root)
{return root NULL ? 0 : SumNode(root-left) SumNode(root-right) 1;
}
递归其实说难也难说不难也不难是有技巧在里面的 1大事化小根结点为1的二叉树的结点总和左子树2的结点总和加上右子树4的结点总和再加上本身的结点个数1然后根结点为2的结点总和左子树3的总和加上NULL加1这就是规律【1241 】
2结束条件当结点为NULL时返回0
//结点个数
printf(%d\n, SumNode(root)); 3叶子结点个数
//叶子结点个数
int LeafNode(BTNode* root)
{if (root NULL){return 0;}if (root-leftNULL root-rightNULL){return 1;}else{return LeafNode(root-left) LeafNode(root-right);}
} 大事化小求根结点为1的二叉树的叶子节点的个数其左子树2加上其右子树4的叶子节点的个数【124】
结束条件当结点为NULL时返回0当结点的左右子树都为NULL时返回1 4二叉树高度
//二叉树高度
int HeightTree(BTNode* root)
{if (root NULL){return 0;}int left HeightTree(root-left);int right HeightTree(root-right);return left right ? left 1 : right 1;
} 大事化小求根结点为1的二叉树的高度其左子树2与右子树4中高的一颗的高度加上本身的高度1【1242141 】
结束条件当结点为NULL时返回0
//二叉树高度
printf(%d\n, HeightTree(root)); 5二叉树第k层结点个数
//二叉树第k层结点个数
int BTreeLeveSize(BTNode* root, int k)
{if (root NULL){return 0;}if (k 1){return 1;}return BTreeLeveSize(root-left, k - 1) BTreeLeveSize(root-right, k - 1);
} 大事化小求根结点为1的二叉树第K层的结点个数其左子树2加上右子树4中第K-1层结点的个数【124】
结束条件当结点为NULL时返回0当K等于1时返回1
//二叉树第k层结点个数
printf(%d\n, BTreeLeveSize(root,3)); 6二叉树查找值为x的结点
//二叉树查找值为x的结点
BTNode* BTreeFine(BTNode* root, int x)
{if (root NULL){return NULL;}if (root-data x){return root;}if (BTreeFine(root-left, x) NULL){return BTreeFine(root-right, x);}else{return BTreeFine(root-left, x);}
} 大事化小查找根结点为1的二叉树中值为x的结点查找其左子树2与右子树4中值为x的结点
结束条件当结点为NULL时返回NULL当结点的值为x时返回该结点
思路所以当其中一个子树不为NULL时就是所求的结点如果左子树不为空则返回左子树的结点否则返回右子树的结点如果左右都为空那也返回右子树的结点
//二叉树查找值为x的结点
BTNode* ret BTreeFine(root, 6);
printf(%d\n, ret-data);ret BTreeFine(root, 3);
printf(%d\n, ret-data); 到这里就结束了通过这些题目也充分的认识了二叉树递归树这就是递归算法还是要多画图来理解递归基层的知识就是函数栈帧的创建与销毁 第三阶段就到这里了这阶段带大家了解一下二叉树递归树的递归思想
后面博主会陆续更新
如有不足之处欢迎来补充交流
完结。。
