自己做自媒体在哪个网站比较好,整站策划营销型网站建设网站优化,自己做软件的网站,网站写作赚钱目录
1. 二叉树的链式存储#xff1a;
2. 二叉树的前序遍历#xff1a;
3. 二叉树的中序遍历#xff1a;
4. 二叉树的后序遍历#xff1a;
5. 统计二叉树的结点总数 6.统计二叉树的叶子结点数#xff1a;
7. 统计二叉树第层的结点数量#xff1a;
8. 二叉树的销毁…
目录
1. 二叉树的链式存储
2. 二叉树的前序遍历
3. 二叉树的中序遍历
4. 二叉树的后序遍历
5. 统计二叉树的结点总数 6.统计二叉树的叶子结点数
7. 统计二叉树第层的结点数量
8. 二叉树的销毁
9.查找树中值为结点
10. 二叉树的层序遍历
11. 代码总览
11.1 头文件TRLIst.h
11.2 函数实现文件TRList.c
11.3 函数测试文件Test.c 在数据结构的第七篇文章中提到对于完全二叉树而言可以采用顺序存储的方法来存储完全二叉树。但是对于非完全二叉树而言例如下图中给出的二叉树存储方法需要采用链式存储。本文将围绕二叉树的链式存储展开介绍链式存储方法以及此类二叉树相关功能的实现。 1. 二叉树的链式存储 在前几篇文章介绍完全二叉树及堆的代码实现时会涉及到此类数据结构的插入结点、删除结点等特点。但是对于非完全二叉树由于结构并不像完全二叉树一样有一定规律因此利用非完全二叉树存储数据的操作较为复杂。并且在存储数据这一方面之前的完全二叉树更为合适。所以对于普通的非完全二叉树来说插入、删除结点的操作是没有意义的。 对于非完全二叉树的价值主要是体现于后续更复杂的数据结构中例如红黑树等。因此文章后续实现的功能主要是利用递归来针对于非完全二叉树自身而言例如求非完全二叉树的叶子结点数目二叉树的深度等等。在二叉树的链式存储这一部分将通过构建关于新建结点函数来手动构建上图给出的非完全二叉树。 对于非完全二叉树在关于树的基础的文章中就提到链式存储的方法可以归结为左孩子右兄弟。所以树的结点的结构如下
typedef int TRDataType;
typedef struct TreeNode
{TRDataType val;struct TreeNode* left;struct TreeNode* right;
}TRNode; 在确立了二叉树结点的结构之后下一步构建函数代码如下
TRNode* BuyTRNode(int x)
{TRNode* newnode (TRNode*)malloc(sizeof(TRNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-left NULL;newnode-right NULL;return newnode;
}
下一步通过上面的两个函数直接构建出上图中给出的非完全二叉树即
int main()
{TRNode* node1 BuyTRNode(1);TRNode* node2 BuyTRNode(2);TRNode* node3 BuyTRNode(3);TRNode* node4 BuyTRNode(4);TRNode* node5 BuyTRNode(5);TRNode* node6 BuyTRNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;return 0;
}
注 文章后续所有的运行结果均需要适配相应的测试代码测试代码将在文章最后统一给出
2. 二叉树的前序遍历
对于二叉树的前序遍历其顺序是按照根结点左结点右结点进行访问的例如对于上面给出的树其结点访问顺序依次为注将空看作结点123,,,4,5,,,6,,。 利用图形来表示结点访问的顺序即 其中均代表访问到空结点代表访问到空结点后返回上一个结点。在结点访问的过程中每个结点都是按照根结点、左结点、右结点的顺序。因此对于这种重复性的问题可以使用递归实现具体代码如下
//前序遍历
void PreOrder(TRNode* root)
{if (root NULL){return;}//访问根结点printf(%d , root-val);//访问左结点PreOrder(root-left);//访问右结点PreOrder(root-right);
}
运行结果如下 3. 二叉树的中序遍历 二叉树的中序遍历顺序为左结点、根结点、右结点依旧针对于上面给出的二叉树中序遍历对于结点的访问顺序为321546。用图片表示结点的访问顺序即 对应代码如下
//中序遍历
void InOrder(TRNode* root)
{if (root NULL){return;}//访问左结点InOrder(root-left);//访问根结点printf(%d , root-val);//访问右结点InOrder(root-right);
}
结果如下 4. 二叉树的后序遍历
二叉树的后序遍历顺序为左结点右结点根结点。针对上方给出的二叉树后序遍历访问结点的顺序依次为。
用图形表示结点的访问顺序即 对应代码如下
//后序遍历
void PostOrder(TRNode* root)
{if (root NULL){return;}//访问左结点InOrder(root-left);//访问右结点InOrder(root-right);//访问根结点printf(%d , root-val);}
结果如下 5. 统计二叉树的结点总数
对于统计二叉树的结点总数这一功能可以拆分为以下步骤利用递归进行实现
1. 检测结点是否为空如果为空则表示结点为空即不存在此结点返回。如果不为空则表示存在本结点结果加1并且向下检测本结点的左、右结点。
2.在检测结点时需要检测结点的左、右结点检测方法参考1
具体代码如下
//统计二叉树的结点树
int TreeSize(TRNode* root)
{if (root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;
}
测试结果如下 6.统计二叉树的叶子结点数
对于统计二叉树叶子结点数的功能实现可以分成下面的部分
1. 检测本结点是否符合叶子结点的特点即,并且。如果符合则返回值返回。
2.若本结点不符合1中的判定条件则存在两种情况一是本结点为空二是本结点为分支结点。对于第一种情况返回值返回对于第二种情况则继续向下检测本结点的子结点即
对应代码为
//统计二叉树的叶子结点数
int TreeLeafSize(TRNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return TreeLeafSize(root-left) TreeLeafSize(root-right);
}
运行结果如下 符合上图中的叶子结点数量。
7. 统计二叉树第层的结点数量
对于此功能的实现同样可以分为下面的几步
1.额外创建一个变量用来间接表示二叉树的层数每经过依次递归对进行一次的操作。当时表示已经到达目标层数。此时如果目标层存在结点则返回值返回.
2.当时表示还未到达目标层数继续向下遍历该结点左、右两个子结点。
3.在函数传参的时候需要注意不能传递需要传递。具体代码如下
//统计二叉树第k层结点数
int TNodeSize(TRNode* root, int k)
{if (root NULL){return 0;}if (k 0){return 1;}return TNodeSize(root-left, k - 1) TNodeSize(root-right, k - 1);
}
运行结果如下 结点数量符合上方给出的二叉树。 8. 二叉树的销毁
原理较为简单只给出代码不做过多解释
//二叉树的销毁
void TNodeDestory(TRNode* root)
{if (root NULL){return;}TNodeDestory(root-left);TNodeDestory(root-right);free(root);
} 9.查找树中值为结点
对于查找树中值为的结点这一功能可以分成下面的步骤实现
1. 检测本结点是否为空如果为空则返回。
2.若本结点不为空则检测本结点中存储的数值是否若符合条件则返回该结点的地址。
3.此时结点即不为空结点中存储的数值也因此继续遍历该结点的左、右两个子结点。
对于函数返回值的处理可以在函数中额外创建一个函数指针为了方便表达将这个指针命名为。
如果函数的根结点中存储的数值就是则直接返回该结点指针。如果不等于按照上面的思路函数会继续遍历根结点的子结点。直接令接收函数的返回值并且在遍历的后方加上对于的判定。由于的返回值只存在两种情况即。所以如果返回值不为则不允许返回返回值。判定的返回值为则返回返回值。如果在函数遍历的过程中所有的都不允许返回则表示树种不存在存储数值为的结点。直接返回
对应代码如下
//查找树中值为x的结点
TRNode* TRFind(TRNode* root,int x)
{if (root NULL){return NULL;}if (root-val x){return root;}TRNode* ret NULL;ret TRFind(root-left, x);if (ret){return ret;}ret TRFind(root-right, x);if (ret){return ret;}return NULL;
}
运行结果如下 10. 二叉树的层序遍历
对于二叉树的层序遍历由于需要每一层挨个访问结点因此不能再用前面递归的思想来实现此功能 。如果不采用递归则必须对每个结点的数值进行一次存储。所以文章这里利用队列来辅助实现二叉树的层序遍历
注关于队列的相关知识及代码可在前面的文章一起学数据结构6——栈和队列-CSDN博客获取需要注意在实现本功能时需要将队列头文件中 改成 以便匹配后序的返回值
实现本功能的具体思路如下
1. 创建一个队列为了方便表达将这个队列命名为。
2. 先往队列中利用插入函数插入二叉树根结点的数值。
3. 创建一个指针命名为利用这个指针来接受函数(取队头元素函数)的返回值返回值返回该结点的地址)。
4.按照层序遍历的顺序(即一层一层从左到右访问结点)向队列中插入数据顺序为插入左子结点插入右子结点
5.销毁队头指针利用循环配合上述步骤来完成对整个二叉树的访问判定条件为(探空函数
对应代码如下
//层序遍历
void LevelOrder(Que* qs,TRNode* root)
{if(root)QueuePush(qs, root);while (!QueueEmpty(qs)){TRNode* violent QueueFront(qs);printf(%d , violent-val);if (violent-left)QueuePush(qs,violent-left);if (violent-right)QueuePush(qs,violent-right);QueuePop(qs);}}
运行结果如下
11. 代码总览
11.1 头文件TRLIst.h
#includestdio.h
#includestdlib.h
#includeassert.htypedef int TRDataType;
typedef struct TreeNode
{TRDataType val;struct TreeNode* left;struct TreeNode* right;
}TRNode;#includequeue.h//结点插入函数
TRNode* BuyTRNode(int x);//前序遍历
void PreOrder(TRNode* root);//中序遍历
void InOrder(TRNode* root);//后序遍历
void PostOrder(TRNode* root);//统计二叉树的结点树
int TreeSize(TRNode* root);//统计二叉树的叶子结点数
int TreeLeafSize(TRNode* root);//统计二叉树第k层结点数
int TNodeSize(TRNode* root, int k);//二叉树的销毁
void TNodeDestory(TRNode* root);//查找树中值为x的结点
TRNode* TRFind(TRNode* root, int x);//层序遍历
void LevelOrder(Que* qs,TRNode* root);11.2 函数实现文件TRList.c
#includeTRList.h//结点插入函数
TRNode* BuyTRNode(int x)
{TRNode* newnode (TRNode*)malloc(sizeof(TRNode));if (newnode NULL){perror(malloc fail);exit(-1);}newnode-val x;newnode-left NULL;newnode-right NULL;return newnode;
}//前序遍历
void PreOrder(TRNode* root)
{if (root NULL){return;}//访问根结点printf(%d , root-val);//访问左结点PreOrder(root-left);//访问右结点PreOrder(root-right);
}//中序遍历
void InOrder(TRNode* root)
{if (root NULL){return;}//访问左结点InOrder(root-left);//访问根结点printf(%d , root-val);//访问右结点InOrder(root-right);
}//后序遍历
void PostOrder(TRNode* root)
{if (root NULL){return;}//访问左结点InOrder(root-left);//访问右结点InOrder(root-right);//访问根结点printf(%d , root-val);
}//统计二叉树的结点树
int TreeSize(TRNode* root)
{if (root NULL){return 0;}return TreeSize(root-left) TreeSize(root-right) 1;
}//统计二叉树的叶子结点数
int TreeLeafSize(TRNode* root)
{if (root NULL){return 0;}if (root-left NULL root-right NULL){return 1;}return TreeLeafSize(root-left) TreeLeafSize(root-right);
}//统计二叉树第k层结点数
int TNodeSize(TRNode* root, int k)
{if (root NULL){return 0;}if (k 0){return 1;}return TNodeSize(root-left, k - 1) TNodeSize(root-right, k - 1);
}//二叉树的销毁
void TNodeDestory(TRNode* root)
{if (root NULL){return;}TNodeDestory(root-left);TNodeDestory(root-right);free(root);
}//查找树中值为x的结点
TRNode* TRFind(TRNode* root,int x)
{if (root NULL){return NULL;}if (root-val x){return root;}TRNode* ret NULL;ret TRFind(root-left, x);if (ret){return ret;}ret TRFind(root-right, x);if (ret){return ret;}return NULL;
}//层序遍历
void LevelOrder(Que* qs,TRNode* root)
{if(root)QueuePush(qs, root);while (!QueueEmpty(qs)){TRNode* violent QueueFront(qs);printf(%d , violent-val);if (violent-left)QueuePush(qs,violent-left);if (violent-right)QueuePush(qs,violent-right);QueuePop(qs);}}
11.3 函数测试文件Test.c
#includeTRList.hvoid TestOrder(TRNode* root)
{printf(前序遍历);PreOrder(root);printf(\n);printf(中序遍历);InOrder(root);printf(\n);printf(后序遍历);PostOrder(root);printf(\n);
}void TestNode(TRNode* root)
{printf(二叉树的结点总数为);int sum TreeSize(root);printf(%d , sum);printf(\n);int sum1 TreeLeafSize(root);printf(二叉树叶子结点总数为);printf(%d , sum1);printf(\n);int k 0;printf(请输入k的值);scanf(%d, k);int sum2 TNodeSize(root, k-1);printf(\n);printf(二叉树第K层结点数量为);printf(%d , sum2);printf(\n);
}void TestTRDes(TRNode* root)
{printf(请输入想要查找的值);int x 0;scanf(%d, x);TRNode* ret NULL;ret TRFind(root, x);printf(\n);
}void TestLOrder(TRNode* root)
{Que qs;QueueInit(qs);LevelOrder(qs, root);QueueDestory(qs);
}int main()
{TRNode* node1 BuyTRNode(1);TRNode* node2 BuyTRNode(2);TRNode* node3 BuyTRNode(3);TRNode* node4 BuyTRNode(4);TRNode* node5 BuyTRNode(5);TRNode* node6 BuyTRNode(6);node1-left node2;node1-right node4;node2-left node3;node4-left node5;node4-right node6;TestOrder(node1);TestNode(node1);TestTRDes(node1);TestLOrder(node1);return 0;
}
