海阳市建设工程交易中心网站,制作网站的步骤和方法,个人网站对主机有什么要求,wordpress支持论坛概述#xff1a; 二叉树#xff0c;这里采用孩子链表存储法#xff0c;即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候#xff0c;先创建各个二叉树结点#xff08;这里的结点采用动态分配#xff0c;因此结点为指针变量#xff09;…概述 二叉树这里采用孩子链表存储法即一个数据域和两个左右孩子指针域。随后递归进行遍历即可。在创建二叉树的时候先创建各个二叉树结点这里的结点采用动态分配因此结点为指针变量随后再根据逻辑结构图手动通过左右指针域链接到对应位置即可。
代码如下
#include stdio.h
#include string.h
#include stdlib.h
//二叉树结点
typedef struct BTnode
{int data;struct BTnode *lchild,*rchild;
}BTnode;BTnode* BuyNode(int x)
{//创建树的结点空间动态分配。 BTnode* node (BTnode*)malloc(sizeof(BTnode));//给结点赋值指针域置空 node-datax;node-lchildNULL;node-rchildNULL;return node;
}
//创建二叉树
BTnode* CreatTree()
{//创建树的结点 BTnode* node1 BuyNode(1);//因为BuyNode是动态分配的空间因此用指针接收 BTnode* node2 BuyNode(2);BTnode* node3 BuyNode(3);BTnode* node4 BuyNode(4);BTnode* node5 BuyNode(5);//手动链接起来。node1-lchildnode2;node1-rchildnode3;node2-lchildnode4;node2-rchildnode5; //链接完毕返回头指针即根结点return node1;
}
//打印树-前序遍历
void PreOrder(BTnode* root)
{if(root NULL){printf(# );return;//返回调用的上一级 }printf(%d ,root-data);PreOrder(root-lchild);PreOrder(root-rchild);
}
void InOrder(BTnode* root)//中序遍历
{if(root NULL){printf(# );return;//返回调用的上一级 }InOrder(root-lchild); //左 printf(%d ,root-data);//根 InOrder(root-rchild);//右 }
void PostOrder(BTnode* root)//后序遍历
{if(root NULL){printf(# );return;//返回调用的上一级 }PostOrder(root-lchild);//左 PostOrder(root-rchild);// 右 printf(%d ,root-data);//根 }
//计算树的结点分治思想分工最后汇总。
int BTtreeSize(BTnode* root)
{if(root NULL)//树是空的就返回0 return 0;else//不是空的就进行左右子树遍历再加1因为要给本身加上。空根不加一但这里非空必定1 {//递归到叶子节点时叶子节点的左右子树都为空返回00011因此叶子节点再往上一层返回即可。 return BTtreeSize(root-lchild)BTtreeSize(root-rchild)1; }
}
//计算树的叶子节点
int LeafSizes(BTnode* root)
{//是空根就返回0if(root NULL)return 0;//符合叶子结点特征即结点的左右子树均为空则返回1即记录上 if(root-lchild NULL root-rchildNULL )return 1;else//都不符合便进入左右子树进行递归计算最后汇总即可。 return LeafSizes(root-lchild)LeafSizes(root-rchild); //实在不明白画个递归图就明白了。
} int main()
{BTnode* rootCreatTree();//遍历递归打印时每个结点调用结束销毁空间返回上一级调用位置。//直到所有结点遍历结束临时空间逐个销毁。 printf(前序遍历);PreOrder(root);printf(\n中序遍历);InOrder(root);printf(\n后序遍历);PostOrder(root); //计算树的结点 int countBTtreeSize(root);printf(\n树有%d个结点,count);int leafcountLeafSizes(root);printf(\n树有%d个叶子结点,leafcount);return 0;}
结果
