甘肃第九建设集团公司网站,55建筑网官网,wordpress 相册 链接,江苏城乡建设部网站文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念
二叉树#xff08;Binary Tree#xff09;是数据结构中一种… 文章目录 二叉树的概念代码实现二叉树的定义创建一棵树并初始化组装二叉树前序遍历中序遍历后序遍历计算树的结点个数求二叉树第K层的结点个数求二叉树高度查找X所在的结点查找指定节点在不在完整代码 二叉树的概念
二叉树Binary Tree是数据结构中一种非常重要的树形结构它的特点是每个节点最多有两个子节点通常称为左子节点和右子节点。这种结构使得二叉树在数据存储和查找等方面具有高效性广泛应用于各种算法和程序中。
节点Node二叉树的基本单元用于存储数据和指向子节点的指针。每个节点可以包含三个部分数据域、左指针和右指针。数据域用于存储节点的值左指针指向左子节点右指针指向右子节点。 特点 有序性二叉树的每个节点都有明确的左子节点和右子节点之分这种有序性使得二叉树在数据查找和遍历等方面具有高效性。 递归性二叉树的很多操作都可以通过递归的方式来实现例如遍历、插入和删除等。这种递归性使得二叉树的处理变得简洁而统一。 灵活性二叉树可以根据实际需求进行不同的扩展和变形例如平衡二叉树、二叉搜索树等以满足不同的应用场景。
代码实现
以下代码实现的是最普通的二叉树
二叉树的定义
这段代码定义了一个简单的二叉树节点结构体其中包含指向左子树和右子树的指针以及一个整数值。 通过这种结构我们可以构建一个二叉树其中每个节点都有一个值以及可能存在的左子树和右子树。
// 首先定义一个结构体类型别名BinTreeNode这个结构体用于表示二叉树的节点。
typedef struct BinTreeNode { // left是一个指向左子树根节点的指针。 // 在二叉树中每个节点最多有两个子节点这里left表示节点的左子树。 struct BinTreeNode* left; // right是一个指向右子树根节点的指针。 // 与left相似right表示节点的右子树。 struct BinTreeNode* right; // val表示节点存储的数据值这里是一个整型值。 int val; } BTNode; // BTNode是这个结构体的类型别名方便后续在代码中使用。
创建一棵树并初始化
BuyNode函数是一个用于创建和初始化二叉树节点的函数。 它接受一个整数val作为参数动态分配内存来创建一个新的BTNode结构体实例 并将该实例的left和right指针初始化为NULLval成员设置为传入的参数值。 如果内存分配失败则打印错误信息并返回NULL。 如果成功则返回指向新创建节点的指针。
// 函数用于创建一个新的二叉树节点并初始化它
BTNode* BuyNode(int val) { // 使用malloc动态分配内存空间大小为BTNode结构体的大小 // 并将分配到的内存地址强制转换为BTNode指针类型赋值给newnode BTNode* newnode (BTNode*)malloc(sizeof(BTNode)); // 检查malloc是否成功分配了内存 // 如果newnode为NULL说明内存分配失败 if (newnode NULL) { // 如果内存分配失败则打印错误信息 perror(malloc fail); // 并返回NULL表示节点创建失败 return NULL; } // 初始化新节点的左子树指针为NULL表示当前没有左子树 newnode-left NULL; // 初始化新节点的右子树指针为NULL表示当前没有右子树 newnode-right NULL; // 将传入的val值赋给新节点的val成员设置节点的值 newnode-val val; // 注意这里的val是函数参数表示节点的数据值 // 返回新创建的节点指针供外部使用 return newnode; // 节点创建成功返回其地址
}
组装二叉树
CreatNode函数是一个用于组装特定二叉树的函数。 它首先调用BuyNode函数来创建6个独立的节点并分别给它们赋值。 然后它将这些节点通过它们的left和right指针连接起来形成一个具有特定结构的二叉树。 最后它返回根节点的指针以便外部可以访问和操作这棵树。
// 函数用于组装创建并连接一个具体的二叉树并返回其根节点指针
BTNode* CreatNode() { // 调用BuyNode函数创建6个新的二叉树节点并分别初始化它们的值为1到6 BTNode* n1 BuyNode(1); // 创建值为1的节点并作为根节点 BTNode* n2 BuyNode(2); // 创建值为2的节点 BTNode* n3 BuyNode(3); BTNode* n4 BuyNode(4); BTNode* n5 BuyNode(5); BTNode* n6 BuyNode(6); // 下面的代码将这些节点连接起来形成一个具体的二叉树结构 n1-left n2; // 将n2节点设置为n1节点的左子树 n1-right n4; // 将n4节点设置为n1节点的右子树 n2-left n3; // 将n3节点设置为n2节点的左子树n2没有右子树 n4-left n5; // 将n5节点设置为n4节点的左子树 n4-right n6; // 将n6节点设置为n4节点的右子树 //以上是我们人工建的一颗二叉树// 返回根节点的指针这样外部就可以通过这个指针来访问整棵树了 return n1; // 根节点是n1所以返回n1的指针
}
前序遍历
从这个函数开始后面的函数基本都是递归了强烈建议在刚开始学的时候多画几遍递归展开图理解每个函数的运行过程熟练之后就可以直接在脑海里理解过程了。 PreOrder函数实现了二叉树的前序遍历。 前序遍历的顺序是先访问根节点然后遍历左子树最后遍历右子树。 在遍历过程中如果遇到空节点即子树不存在则打印N 。这里打印N是为了更易于理解。 这个函数通过递归的方式简洁地实现了前序遍历的逻辑。
// 定义前序遍历函数参数为二叉树的根节点指针
void PreOrder(BTNode* root) { // 首先检查根节点是否为空 if (root NULL) { // 如果根节点为空则打印N 表示此处无节点NULL的简写 printf(N ); // 然后直接返回不再继续遍历 return; } // 如果根节点不为空则首先打印根节点的值 printf(%d , root-val); // 接着递归地调用前序遍历函数传入左子树的根节点 // 这样会先遍历整个左子树 PreOrder(root-left); // 最后递归地调用前序遍历函数传入右子树的根节点 // 这样会遍历整个右子树 PreOrder(root-right);
}
中序遍历
InOrder函数递归地先处理左子树然后打印当前节点的值最后处理右子树直到所有节点都被访问并打印出来。如果树中存在空指针即某个节点没有左子节点或右子节点则打印N 来表示该位置为空。 中序遍历的顺序是先遍历左子树然后访问根节点最后遍历右子树。 在遍历过程中如果遇到空节点即子树不存在则打印N 。这里打印N是为了更易于理解。 这个函数也是通过递归的方式实现的每次递归都处理当前节点的左子树、自身和右子树。
// 定义中序遍历函数参数为二叉树的根节点指针
void InOrder(BTNode* root) { // 首先检查根节点是否为空 if (root NULL) { // 如果当前节点为空即已经遍历到叶子节点下面或者子树不存在 // 则打印N 表示此处无节点值可输出 printf(N ); // 打印完毕后直接返回不再继续遍历 return; } // 如果当前节点不为空则先递归调用中序遍历函数传入左子节点 // 这样可以确保在打印当前节点之前先遍历并打印整个左子树 InOrder(root-left); // 遍历完左子树后回到当前节点并打印当前节点的值 printf(%d , root-val); // 打印完当前节点值后递归调用中序遍历函数传入右子节点 // 这样可以确保在打印完当前节点后继续遍历并打印整个右子树 InOrder(root-right);
}
后序遍历
PostOrder函数实现了二叉树的后序遍历。 后序遍历的顺序是先遍历左子树然后遍历右子树最后访问根节点。 这个过程一直进行到所有节点都被访问并打印出来为止。 遍历过程中若遇到空节点即某节点没有左子节点或右子节点或子树不存在则打印N 。 函数通过递归方式实现递归的基准情况是节点为空时返回。
// 定义后序遍历函数参数为二叉树的根节点指针
void PostOrder(BTNode* root) { // 首先检查传入的根节点是否为空 if (root NULL) { // 如果根节点为空表示已经遍历到了叶子节点下面或者子树不存在 // 在此处打印N 作为空节点NULL的占位符输出 printf(N ); // 打印完空节点后直接返回不再继续递归遍历 return; } // 如果当前节点不为空则先递归调用后序遍历函数传入左子节点 // 后序遍历的顺序是先遍历左子树 PostOrder(root-left); // 接着递归调用后序遍历函数传入右子节点 // 后序遍历接下来遍历右子树 PostOrder(root-right); // 在确保左右子树都已经遍历完成后打印当前节点的值 // 后序遍历的最后一步是访问打印根节点 printf(%d , root-val);
}
计算树的结点个数
TreeSize函数用于递归地计算一棵二叉树中节点的总数。 函数首先检查传入的根节点是否为空如果为空则返回0表示没有节点。 如果根节点不为空则函数递归地调用自身来计算左子树和右子树的节点数 然后将这两个数相加并加上1代表当前根节点从而得到整棵树的节点总数。 对于每个非空节点函数会分别计算其左子树和右子树的节点数然后将这两个数目相加并加上当前节点自身计数为1从而得到以当前节点为根的子树的节点总数。这个过程会一直递归进行直到遍历完整棵树最终返回整棵树的节点总数。 递归方法写的代码一般都比较短但是比一般方法更难以理解
// 定义计算二叉树节点个数的函数参数为二叉树的根节点指针
int TreeSize(BTNode* root) { // 使用三目运算符条件运算符判断根节点是否为空 // 如果root为空说明已经遍历到了叶子节点下面或者子树不存在直接返回0 // 否则递归地计算左子树的节点个数和右子树的节点个数并将它们相加再加上根节点自身即1 return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}
求二叉树第K层的结点个数
TreeKLevel函数通过递归的方式求解二叉树第k层的节点个数。 以下方法的核心是当前树的第k层个数 左子树的第k-1层个数 左子树的第k-1层个数 递归的基准情况有两种一是当节点为空时返回0二是当k等于1时返回1。 对于其他情况函数会递归地调用自身来计算左子树和右子树中第k-1层的节点数 然后将这两个数相加得到结果。这个过程会一直进行下去直到达到基准情况为止。 小结这段代码的核心思想是利用递归逐层向下遍历二叉树同时记录当前所在的层数。当遍历到目标层时返回该层的节点数。由于二叉树的层数是从根节点开始计算的因此在每次递归调用时都需要将目标层数k减去1以正确地定位到下一层。通过这种方式函数能够准确地计算出二叉树中任意一层的节点个数。
// 定义函数TreeKLevel用于求二叉树第k层的节点个数
// 参数root为二叉树的根节点指针k为目标层数
int TreeKLevel(BTNode* root, int k) { // 如果根节点为空说明已经遍历到空树或者子树不存在 // 直接返回0表示第k层没有节点 if (root NULL) { return 0; } // 如果k等于1说明当前层就是第一层根节点所在的层 // 直接返回1因为根节点是唯一一个在第1层的节点 if (k 1) { return 1; } // 如果k大于1说明目标层在根节点的下面 // 递归地调用TreeKLevel函数分别传入左子树和右子树的根节点以及k-1作为新的层数 // 然后将两个递归调用的结果相加得到第k层的节点总数 // 注意这里k要减1是因为往下一层递归时层数要相应地减少 return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
求二叉树高度
该函数通过递归的方式计算二叉树的高度。 递归的基准情况是当节点为空时返回1表示空树或不存在的高度加1是为了方便递归计算。 /对于非空节点函数会分别计算其左子树和右子树的高度然后取两者中的较大值并加1作为当前树的高度。 返回值是整棵树的高度。
// 定义函数TreeHigh用于求二叉树的高度
// 参数root为二叉树的根节点指针
int TreeHigh(BTNode* root) { // 如果根节点为空说明当前子树不存在或为空树 // 按照常规定义空树的高度为0但这里为了递归方便返回1表示高度为0的层级上加1 // 注意这种定义在递归的上下文中是合理的但在实际应用中可能需要调整以确保空树高度为0 if (root NULL) { return 1; } // 递归调用TreeHigh函数计算左子树的高度 int leftHigh TreeHigh(root-left); // 递归调用TreeHigh函数计算右子树的高度 int rightHigh TreeHigh(root-right); // 使用三目运算符比较左子树和右子树的高度 // 返回较高的一边的高度并加上1加上根节点所在的这一层 return leftHigh rightHigh ? leftHigh 1 : rightHigh 1;
}
查找X所在的结点
TreeFind函数是一个递归函数用于在二叉树中查找值为x的节点。 它首先检查根节点是否为空或者是否就是要找的节。如果根节点为空则返回NULL表示未找到。如果根节点的值等于x则返回根节点的指针。 否则函数会递归地在左子树和右子树中查找直到找到目标节点或者遍历完整棵树。 如果在整棵树中都没有找到值为x的节点则最终返回NULL。
// 定义函数TreeFind用于在二叉树中查找值为x的节点并返回该节点的指针
// 参数root为二叉树的根节点指针x为要查找的值
BTNode* TreeFind(BTNode* root, int x) { // 如果根节点为空说明已经遍历到了空子树或者树本身为空 // 直接返回NULL表示在当前子树中没有找到值为x的节点 if (root NULL) { return NULL; } // 如果根节点的值等于x说明找到了目标节点 // 直接返回根节点的指针 if (root-val x) { return root; } // 递归调用TreeFind函数在左子树中查找值为x的节点 // 将返回的节点指针赋值给ret1 BTNode* ret1 TreeFind(root-left, x); // 如果ret1不为空说明在左子树中找到了值为x的节点 // 直接返回ret1即找到了目标节点的指针 if (ret1) { return ret1; } // 如果左子树中没有找到继续递归调用TreeFind函数在右子树中查找值为x的节点 // 将返回的节点指针赋值给ret2 BTNode* ret2 TreeFind(root-right, x); // 如果ret2不为空说明在右子树中找到了值为x的节点 // 直接返回ret2即找到了目标节点的指针 if (ret2) { return ret2; } // 如果左右子树中都没有找到值为x的节点说明整个树中都不存在该节点 // 返回NULL表示没有找到目标节点 return NULL;
}查找指定节点在不在
// 参数root 是指向二叉树根节点的指针x 是要查找的节点值
// 返回值bool 类型如果找到指定节点则返回 true否则返回 false这个通常用于条件语句或者循环语句里返回true时执行返回false时不执行
// 功能在二叉树中查找指定的节点值是否存在
bool TreeFindExit(BTNode* root, int x) { // 如果当前节点为空即已经遍历到叶子节点之后的位置则返回 false if (root NULL) { return false; } // 如果当前节点的值等于要查找的值 x则说明找到了指定的节点 // 直接返回 true if (root-val x) { return true; } // 如果当前节点的值不是要查找的值则递归地在左子树和右子树中查找 // 使用逻辑或操作符 ||表示如果左子树或右子树中任何一个找到了指定节点就返回 true // 如果左右子树都没有找到最终会返回 false return TreeFindExit(root-left, x) || TreeFindExit(root-right, x);
}完整代码
#includestdio.h
#includestdlib.h
#includestdbool.h//二叉树的定义
typedef struct BinTreeNode {struct BinTreeNode* left;struct BinTreeNode* right;int val;
}BTNode;//创建一棵树并初始化
BTNode* BuyNode(int val) {BTNode* newnode (BTNode*)malloc(sizeof(BTNode));if (newnode NULL) {perror(malloc fail);return;//注意这里应该是return NULL}newnode-left NULL;newnode-right NULL;newnode-val val;//这里是valreturn newnode;//创建了就要返回
}//组装二叉树
BTNode* CreatNode() {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-left n2;n1-right n4;n2-left n3;n4-left n5;n4-right n6;return n1;//记得返回
}//前序遍历
void PreOrder(BTNode* root) {if (root NULL) {printf(N );return;}printf(%d , root-val);PreOrder(root-left);PreOrder(root-right);
}//中序遍历
void InOrder(BTNode* root) {if (root NULL) {printf(N );return;}InOrder(root-left);printf(%d ,root-val);InOrder(root-right);
}//后序遍历
void PostOrder(BTNode* root) {if (root NULL) {printf(N );return;}PostOrder(root-left);PostOrder(root-right);printf(%d ,root-val);
}//计算树的结点个数
int TreeSize(BTNode* root) {return root NULL ? 0 : TreeSize(root-left) TreeSize(root-right) 1;
}//求二叉树第K层的结点个数
int TreeKLevel(BTNode* root,int k) {if (root NULL) {return 0;}if (k 1) {//k1时不需要再往下求了return 1;}return TreeKLevel(root-left, k - 1) TreeKLevel(root-right, k - 1);
}
//求二叉树高度
int TreeHigh(BTNode* root) {if (root NULL) {return 1;}int leftHigh TreeHigh(root-left);int rightHigh TreeHigh(root-right);return leftHigh rightHigh ? leftHigh 1 : rightHigh 1;
}//查找X所在的结点
BTNode*TreeFind(BTNode*root,int x){if (root NULL) {return NULL;}if (root-val x) {return root;}BTNode* ret1TreeFind(root-left, x);if (ret1) {return ret1;}BTNode* ret2 TreeFind(root-right, x);if (ret2) {return ret2;}return NULL;}//查找指定节点在不在
bool TreeFindExit(BTNode* root, int x) {if (root NULL) {return false;}if (root-val x) {return true;}return TreeFindExit(root-left, x) || TreeFindExit(root-right, x);
}int main() {BTNode* root CreatNode();PreOrder(root);printf(\n);InOrder(root);printf(\n);PostOrder(root);printf(\n);int high TreeHigh(root);printf(%d\n, high);int a TreeKLevel(root,2);printf(%d\n, a);BTNode* b TreeFind(root, 1);printf(%d\n, b-val);if (TreeFindExit(root, 2)) {printf(存在\n);}else {printf(不存在\n);}return 0;
}
文章转载自： http://www.morning.lokext.com.gov.cn.lokext.com http://www.morning.dpdns.cn.gov.cn.dpdns.cn http://www.morning.fbbpj.cn.gov.cn.fbbpj.cn http://www.morning.gbxxh.cn.gov.cn.gbxxh.cn http://www.morning.dkfrd.cn.gov.cn.dkfrd.cn http://www.morning.hxhrg.cn.gov.cn.hxhrg.cn http://www.morning.fbmzm.cn.gov.cn.fbmzm.cn http://www.morning.cftkz.cn.gov.cn.cftkz.cn http://www.morning.qyqmj.cn.gov.cn.qyqmj.cn http://www.morning.ryznd.cn.gov.cn.ryznd.cn http://www.morning.mqnbm.cn.gov.cn.mqnbm.cn http://www.morning.wmlby.cn.gov.cn.wmlby.cn http://www.morning.lqgfm.cn.gov.cn.lqgfm.cn http://www.morning.rdtp.cn.gov.cn.rdtp.cn http://www.morning.pdwny.cn.gov.cn.pdwny.cn http://www.morning.slzkq.cn.gov.cn.slzkq.cn http://www.morning.wylpy.cn.gov.cn.wylpy.cn http://www.morning.pwmm.cn.gov.cn.pwmm.cn http://www.morning.ddqdl.cn.gov.cn.ddqdl.cn http://www.morning.snccl.cn.gov.cn.snccl.cn http://www.morning.jfjbl.cn.gov.cn.jfjbl.cn http://www.morning.kfqzd.cn.gov.cn.kfqzd.cn http://www.morning.nxkyr.cn.gov.cn.nxkyr.cn http://www.morning.rgnq.cn.gov.cn.rgnq.cn http://www.morning.hytr.cn.gov.cn.hytr.cn http://www.morning.btmwd.cn.gov.cn.btmwd.cn http://www.morning.nfks.cn.gov.cn.nfks.cn http://www.morning.szoptic.com.gov.cn.szoptic.com http://www.morning.xhpnp.cn.gov.cn.xhpnp.cn http://www.morning.znqxt.cn.gov.cn.znqxt.cn http://www.morning.kxnjg.cn.gov.cn.kxnjg.cn http://www.morning.pqyms.cn.gov.cn.pqyms.cn http://www.morning.dxtxk.cn.gov.cn.dxtxk.cn http://www.morning.hlnys.cn.gov.cn.hlnys.cn http://www.morning.cpnsh.cn.gov.cn.cpnsh.cn http://www.morning.wfwqr.cn.gov.cn.wfwqr.cn http://www.morning.jmspy.cn.gov.cn.jmspy.cn http://www.morning.qlpyn.cn.gov.cn.qlpyn.cn http://www.morning.spbp.cn.gov.cn.spbp.cn http://www.morning.qnypp.cn.gov.cn.qnypp.cn http://www.morning.nbqwt.cn.gov.cn.nbqwt.cn http://www.morning.wslr.cn.gov.cn.wslr.cn http://www.morning.dnpft.cn.gov.cn.dnpft.cn http://www.morning.xprzq.cn.gov.cn.xprzq.cn http://www.morning.plqqn.cn.gov.cn.plqqn.cn http://www.morning.cjrmf.cn.gov.cn.cjrmf.cn http://www.morning.gmrxh.cn.gov.cn.gmrxh.cn http://www.morning.ymjrg.cn.gov.cn.ymjrg.cn http://www.morning.zlwg.cn.gov.cn.zlwg.cn http://www.morning.brwp.cn.gov.cn.brwp.cn http://www.morning.qwpyf.cn.gov.cn.qwpyf.cn http://www.morning.mlnzx.cn.gov.cn.mlnzx.cn http://www.morning.nlryq.cn.gov.cn.nlryq.cn http://www.morning.qzpsk.cn.gov.cn.qzpsk.cn http://www.morning.djxnn.cn.gov.cn.djxnn.cn http://www.morning.xdpjf.cn.gov.cn.xdpjf.cn http://www.morning.ljllt.cn.gov.cn.ljllt.cn http://www.morning.yqfdl.cn.gov.cn.yqfdl.cn http://www.morning.dpflt.cn.gov.cn.dpflt.cn http://www.morning.tpqzs.cn.gov.cn.tpqzs.cn http://www.morning.xrsqb.cn.gov.cn.xrsqb.cn http://www.morning.dtnzk.cn.gov.cn.dtnzk.cn http://www.morning.zfyr.cn.gov.cn.zfyr.cn http://www.morning.gwxwl.cn.gov.cn.gwxwl.cn http://www.morning.chmkt.cn.gov.cn.chmkt.cn http://www.morning.mlckd.cn.gov.cn.mlckd.cn http://www.morning.jzlkq.cn.gov.cn.jzlkq.cn http://www.morning.ggcjf.cn.gov.cn.ggcjf.cn http://www.morning.mtktn.cn.gov.cn.mtktn.cn http://www.morning.gmyhq.cn.gov.cn.gmyhq.cn http://www.morning.mzhh.cn.gov.cn.mzhh.cn http://www.morning.fjlsfs.com.gov.cn.fjlsfs.com http://www.morning.ydxx123.cn.gov.cn.ydxx123.cn http://www.morning.rmmz.cn.gov.cn.rmmz.cn http://www.morning.gmrxh.cn.gov.cn.gmrxh.cn http://www.morning.mjqms.cn.gov.cn.mjqms.cn http://www.morning.czxrg.cn.gov.cn.czxrg.cn http://www.morning.gnkbf.cn.gov.cn.gnkbf.cn http://www.morning.clkyw.cn.gov.cn.clkyw.cn http://www.morning.trffl.cn.gov.cn.trffl.cn
