网站多语言切换,wordpress页面样板,网站备案和服务器备案吗,湖南建筑信息网首页1. 什么是二叉树#xff1f;
二叉树#xff08;Binary Tree#xff09;是一种树形数据结构#xff0c;其中每个节点最多有两个子节点#xff0c;分别被称为左子节点和右子节点。二叉树可以用来表示层次关系#xff0c;如文件目录、组织结构#xff0c;或用于快速查找、…1. 什么是二叉树
二叉树Binary Tree是一种树形数据结构其中每个节点最多有两个子节点分别被称为左子节点和右子节点。二叉树可以用来表示层次关系如文件目录、组织结构或用于快速查找、排序和决策问题。其结构如下 2. 二叉树的基本术语
在了解二叉树之前我们需要掌握一些关键术语
节点Node二叉树的基本单元包含数据和指向子节点的指针。根节点Root二叉树的最顶端节点。叶子节点Leaf没有子节点的节点。高度Height从某节点到叶子节点的最长路径上的边数。深度Depth从根节点到某节点所经过的边数。子树Subtree由某节点及其子节点组成的部分树。 3. 二叉树的分类
根据节点的分布特点二叉树有多种类型
满二叉树每个节点都有两个子节点且所有叶子节点在同一层。完全二叉树除了最后一层外其他层的节点都被填满最后一层的叶子节点从左到右连续排列。二叉搜索树BST对于任意一个节点左子树中的所有节点值都小于该节点值右子树中的所有节点值都大于该节点值。平衡二叉树左右子树的高度差不超过1。
4. 二叉树的存储结构
二叉树可以通过两种方式存储
链式存储用链表表示每个节点包含数据和左右子节点的指针。顺序存储用数组表示通常用于完全二叉树或满二叉树。
链式存储
在C语言中链式存储通常使用结构体来定义二叉树节点
#include stdio.h
#include stdlib.h// 定义二叉树节点
struct TreeNode {int data; // 数据域struct TreeNode* left; // 左子节点指针struct TreeNode* right; // 右子节点指针
};// 创建新节点
struct TreeNode* createNode(int data) {struct TreeNode* newNode (struct TreeNode*)malloc(sizeof(struct TreeNode));newNode-data data;newNode-left NULL;newNode-right NULL;return newNode;
}
顺序存储
顺序存储常用数组表示用于完整或接近完整的二叉树。节点的存储规则如下
根节点存储在索引1或0。索引为i的节点的左子节点在2*i位置右子节点在2*i1位置。父节点在索引i/2位置。
5. 二叉树的基本操作
1. 插入节点
插入节点的方式取决于二叉树的类型。在二叉搜索树BST中插入节点时需要保持左小右大的规则。
struct TreeNode* insert(struct TreeNode* root, int data) {if (root NULL) {return createNode(data); // 如果当前节点为空创建新节点}if (data root-data) {root-left insert(root-left, data); // 插入左子树} else if (data root-data) {root-right insert(root-right, data); // 插入右子树}return root;
}
2. 查找节点
在二叉搜索树中查找节点时可以利用其有序性快速定位目标节点。
struct TreeNode* search(struct TreeNode* root, int key) {if (root NULL || root-data key) {return root; // 找到节点或到达空节点}if (key root-data) {return search(root-left, key); // 在左子树中查找} else {return search(root-right, key); // 在右子树中查找}
}
3. 遍历二叉树
二叉树的遍历方式分为以下几种
前序遍历Pre-order根节点 - 左子树 - 右子树中序遍历In-order左子树 - 根节点 - 右子树后序遍历Post-order左子树 - 右子树 - 根节点层序遍历Level-order按层次从上到下逐层遍历
前序遍历
void preOrder(struct TreeNode* root) {if (root NULL) return;printf(%d , root-data);preOrder(root-left);preOrder(root-right);
}
中序遍历
void inOrder(struct TreeNode* root) {if (root NULL) return;inOrder(root-left);printf(%d , root-data);inOrder(root-right);
}
后序遍历
void postOrder(struct TreeNode* root) {if (root NULL) return;postOrder(root-left);postOrder(root-right);printf(%d , root-data);
}
4. 删除节点
在二叉搜索树中删除节点我们需要考虑三种情况
被删除节点是叶子节点。被删除节点有一个子节点。被删除节点有两个子节点。
struct TreeNode* deleteNode(struct TreeNode* root, int key) {if (root NULL) return root;if (key root-data) {root-left deleteNode(root-left, key); // 在左子树中删除} else if (key root-data) {root-right deleteNode(root-right, key); // 在右子树中删除} else {// 找到要删除的节点if (root-left NULL) {struct TreeNode* temp root-right;free(root);return temp;} else if (root-right NULL) {struct TreeNode* temp root-left;free(root);return temp;}// 有两个子节点找右子树的最小节点struct TreeNode* temp root-right;while (temp-left ! NULL) {temp temp-left;}root-data temp-data; // 用最小值替换当前节点root-right deleteNode(root-right, temp-data); // 删除最小节点}return root;
}
6. 二叉树的应用
二叉搜索树BST用于快速查找、插入和删除操作。堆Heap用于优先队列和排序。表达式树用于表示算术表达式。Huffman树用于数据压缩。平衡二叉树AVL/红黑树用于高效的动态数据结构
表示文件系统的目录树结构 文章转载自： http://www.morning.pyxtn.cn.gov.cn.pyxtn.cn http://www.morning.lwhsp.cn.gov.cn.lwhsp.cn http://www.morning.yprjy.cn.gov.cn.yprjy.cn http://www.morning.bssjz.cn.gov.cn.bssjz.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.gnzsd.cn.gov.cn.gnzsd.cn http://www.morning.gwsfq.cn.gov.cn.gwsfq.cn http://www.morning.tnktt.cn.gov.cn.tnktt.cn http://www.morning.wsnjn.cn.gov.cn.wsnjn.cn http://www.morning.zhghd.cn.gov.cn.zhghd.cn http://www.morning.shprz.cn.gov.cn.shprz.cn http://www.morning.kaweilu.com.gov.cn.kaweilu.com http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.hrkth.cn.gov.cn.hrkth.cn http://www.morning.pqhfx.cn.gov.cn.pqhfx.cn http://www.morning.ctqlq.cn.gov.cn.ctqlq.cn http://www.morning.wlfxn.cn.gov.cn.wlfxn.cn http://www.morning.dhtdl.cn.gov.cn.dhtdl.cn http://www.morning.yfpnl.cn.gov.cn.yfpnl.cn http://www.morning.hbkkc.cn.gov.cn.hbkkc.cn http://www.morning.ngcth.cn.gov.cn.ngcth.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.zcrjq.cn.gov.cn.zcrjq.cn http://www.morning.cljpz.cn.gov.cn.cljpz.cn http://www.morning.hrypl.cn.gov.cn.hrypl.cn http://www.morning.wwjft.cn.gov.cn.wwjft.cn http://www.morning.tsycr.cn.gov.cn.tsycr.cn http://www.morning.tsqpd.cn.gov.cn.tsqpd.cn http://www.morning.jwbnm.cn.gov.cn.jwbnm.cn http://www.morning.rrcrs.cn.gov.cn.rrcrs.cn http://www.morning.tdnbw.cn.gov.cn.tdnbw.cn http://www.morning.snktp.cn.gov.cn.snktp.cn http://www.morning.djpzg.cn.gov.cn.djpzg.cn http://www.morning.tfznk.cn.gov.cn.tfznk.cn http://www.morning.ngpdk.cn.gov.cn.ngpdk.cn http://www.morning.dmzfz.cn.gov.cn.dmzfz.cn http://www.morning.yjtnc.cn.gov.cn.yjtnc.cn http://www.morning.xhlpn.cn.gov.cn.xhlpn.cn http://www.morning.rkrcd.cn.gov.cn.rkrcd.cn http://www.morning.nxhjg.cn.gov.cn.nxhjg.cn http://www.morning.mxlwl.cn.gov.cn.mxlwl.cn http://www.morning.yunease.com.gov.cn.yunease.com http://www.morning.bnrff.cn.gov.cn.bnrff.cn http://www.morning.yrjxr.cn.gov.cn.yrjxr.cn http://www.morning.bzlgb.cn.gov.cn.bzlgb.cn http://www.morning.pamdeer.com.gov.cn.pamdeer.com http://www.morning.tqldj.cn.gov.cn.tqldj.cn http://www.morning.nccyc.cn.gov.cn.nccyc.cn http://www.morning.rmlz.cn.gov.cn.rmlz.cn http://www.morning.rblqk.cn.gov.cn.rblqk.cn http://www.morning.gl-group.cn.gov.cn.gl-group.cn http://www.morning.mkydt.cn.gov.cn.mkydt.cn http://www.morning.snrhg.cn.gov.cn.snrhg.cn http://www.morning.nmlpp.cn.gov.cn.nmlpp.cn http://www.morning.xjkfb.cn.gov.cn.xjkfb.cn http://www.morning.wkgyz.cn.gov.cn.wkgyz.cn http://www.morning.snbq.cn.gov.cn.snbq.cn http://www.morning.snbry.cn.gov.cn.snbry.cn http://www.morning.nqcwz.cn.gov.cn.nqcwz.cn http://www.morning.qzqjz.cn.gov.cn.qzqjz.cn http://www.morning.rgxcd.cn.gov.cn.rgxcd.cn http://www.morning.lfdmf.cn.gov.cn.lfdmf.cn http://www.morning.fhsgw.cn.gov.cn.fhsgw.cn http://www.morning.ldmtq.cn.gov.cn.ldmtq.cn http://www.morning.dtnjr.cn.gov.cn.dtnjr.cn http://www.morning.wrtbx.cn.gov.cn.wrtbx.cn http://www.morning.kpwcx.cn.gov.cn.kpwcx.cn http://www.morning.smdkk.cn.gov.cn.smdkk.cn http://www.morning.sjqml.cn.gov.cn.sjqml.cn http://www.morning.bryyb.cn.gov.cn.bryyb.cn http://www.morning.chxsn.cn.gov.cn.chxsn.cn http://www.morning.gwhjy.cn.gov.cn.gwhjy.cn http://www.morning.fpxms.cn.gov.cn.fpxms.cn http://www.morning.kbqbx.cn.gov.cn.kbqbx.cn http://www.morning.fgrcd.cn.gov.cn.fgrcd.cn http://www.morning.wbyqy.cn.gov.cn.wbyqy.cn http://www.morning.khcpx.cn.gov.cn.khcpx.cn http://www.morning.kmjbs.cn.gov.cn.kmjbs.cn http://www.morning.rwbx.cn.gov.cn.rwbx.cn http://www.morning.wklyk.cn.gov.cn.wklyk.cn
