记事本怎样做网站,中信建设有限责任公司电话,手机百度高级搜索入口在哪里,wordpress 模版开发一、概念 二叉树#xff08;Binary Tree#xff09;是一种树形数据结构#xff0c;其中每个节点最多有两个子节点#xff0c;分别称为左子节点和右子节点。二叉树的每个节点包含三个部分#xff1a;一个值、一个指向左子节点的引用和一个指向右子节点的引用。
二、二叉树…一、概念 二叉树Binary Tree是一种树形数据结构其中每个节点最多有两个子节点分别称为左子节点和右子节点。二叉树的每个节点包含三个部分一个值、一个指向左子节点的引用和一个指向右子节点的引用。
二、二叉树的基本概念
节点二叉树中的每个元素称为节点。每个节点包含一个值以及指向其左子节点和右子节点的引用。根节点二叉树的顶端节点称为根节点。它是树中唯一没有父节点的节点。子节点每个节点可以有零个、一或两个子节点。子节点分为左子节点和右子节点。叶节点没有子节点的节点称为叶节点或终端节点。内部节点至少有一个子节点的节点称为内部节点。高度从根节点到某个节点的最长路径上的边数称为该节点的高度。树的高度是所有节点高度的最大值。深度从根节点到某个节点的路径上的边数称为该节点的深度。根节点的深度为0。层次树中所有深度相同的节点组成一层。根节点在第0层其子节点在第1层以此类推。
三、二叉树的类型
满二叉树每个节点要么是叶节点要么有两个子节点。完全二叉树除了最后一层外每一层都是满的并且最后一层的所有节点都尽可能地靠左排列。二叉搜索树BST对于树中的每个节点其左子树中的所有节点值都小于该节点的值而其右子树中的所有节点值都大于该节点的值。
四、二叉树的作用
快速查找二叉搜索树允许我们以O(log n)的时间复杂度进行查找操作。排序通过中序遍历可以得到一个有序的元素列表。动态集合支持动态插入和删除操作适用于需要频繁修改的数据集合。表达式解析二叉树常用于表示算术表达式其中内部节点表示运算符叶节点表示操作数。
五、二叉树的遍历
遍历是指访问树中每个节点的过程。常见的遍历方法包括
前序遍历Pre-order Traversal先访问根节点然后递归地访问左子树最后递归地访问右子树。中序遍历In-order Traversal先递归地访问左子树然后访问根节点最后递归地访问右子树。这种遍历方式特别适用于二叉搜索树因为它会按升序访问所有节点。后序遍历Post-order Traversal先递归地访问左子树然后递归地访问右子树最后访问根节点。层次遍历Level-order Traversal按层次逐层访问节点从上到下从左到右。
六、二叉搜索树Binary Search Tree, BST
定义
二叉搜索树是一种特殊的二叉树它满足以下性质
对于树中的每个节点其左子树中的所有节点值都小于该节点的值而其右子树中的所有节点值都大于该节点的值。
特性
查找操作由于二叉搜索树的性质可以通过比较节点值快速定位目标节点平均时间复杂度为O(log n)。插入操作新节点总是插入到叶节点的位置保持二叉搜索树的性质。删除操作删除节点时需要考虑三种情况 节点是叶节点直接删除即可。节点有一个子节点用子节点替换被删除的节点。节点有两个子节点找到该节点的中序后继右子树中的最小节点或中序前驱左子树中的最大节点用它替换被删除的节点然后删除该后继或前驱节点。
七、二叉搜索树代码实现 1、定义二叉树结构 /// summary/// 二叉树搜索树节点结构/// /summarypublic class TreeNode{public int Value;public TreeNode? Left;public TreeNode? Right;public TreeNode(int value) {Value value;Left null;Right null;}} 2、定义二叉搜索树类实现包括二叉搜索树的插入、删除、搜索、中序遍历等
/// summary
/// 二叉搜索树
/// /summary
public class BinarySearchTree
{private TreeNode? root;public BinarySearchTree() { root null; }//二叉树插入数据public void BinaryTreeInsert(int value){if (root null){root new TreeNode(value); }else{InsertRec(root, value);} }//递归插入数据到二叉树public void InsertRec(TreeNode node,int value){if(value node.Value)//小于当前节点往当前节点的左子树判断插入{if(node.Left null){node.Left new TreeNode(value);}else{InsertRec(node.Left, value);}}else if(value node.Value)//大于当前节点往当前节点的右子树判断插入{if(node.Right null){node.Right new TreeNode(value);}else{InsertRec(node.Right, value);}}else if (value node.Value) //等于当前节点重复不插入{return;}}//二叉树搜索public bool BinaryTreeSearch(int value){return SearchRec(root, value);}//递归搜索二叉树public bool SearchRec(TreeNode? node,int value){if(node null){return false;}if (value node.Value)//小于当前节点往当前节点的左子树判断比较{return SearchRec(node.Left, value);}else if (value node.Value){return SearchRec(node.Right, value);//大于当前节点往当前节点的左子树判断比较}else{return true; }}//二叉树删除节点public void BinaryTreeRemove(int value){root RemoveRec(root, value);}//递归删除二叉树节点public TreeNode? RemoveRec(TreeNode? node,int value){if (node null){ return null; }if(value node.Value){node.Left RemoveRec(node.Left, value);}else if(value node.Value){node.Right RemoveRec(node.Right, value);}else{if(node.Left ! null node.Right ! null){//如果需要删除的节点左右子节点都不为空使用节点的右子树的最小节点替换当前节点TreeNode? minNode FinMinNode(node.Right);if(minNode ! null){node.Value minNode.Value;node.Right RemoveRec(node.Right, minNode.Value);}}else{TreeNode? tempNode node.Left ! null ? node.Left : node.Right;node tempNode;}}return node;}//查找二叉树的最小节点public TreeNode? FinMinNode(TreeNode? node){if(node null){return null;}while (node.Left ! null) //往左子树找最小{ node node.Left;}return node;}//遍历二叉树排序输出public Listint InorderTraversal(){Listint arry new Listint();InorderTraversalRec(root,arry);return arry;}public void InorderTraversalRec(TreeNode? node, Listint arrys){if(node ! null){InorderTraversalRec(node.Left , arrys);arrys.Add(node.Value);InorderTraversalRec(node.Right , arrys);}}//后序遍历public void PostOrderTraversal(){PostOrderTraversalRec(root);}public void PostOrderTraversalRec(TreeNode? node){if (node null){return;}PostOrderTraversalRec(node.Right);PostOrderTraversalRec(node.Left);Console.WriteLine(node.Value);}//前序遍历public void PreOrderTraversal(){PreOrderTraversalRec(root);}public void PreOrderTraversalRec(TreeNode? node){if(root null){return;}Console.WriteLine(node.Value);PreOrderTraversalRec(node.Left);PreOrderTraversalRec(node.Right);}
}
八、二叉搜索树验证 1、编写验证代码
static async Task Main(string[] args)
{BinarySearchTreeTest();
}/// summary
/// 二叉树测试
/// /summary
static void BinarySearchTreeTest()
{var bst new BinarySearchTree();bst.BinaryTreeInsert(35);bst.BinaryTreeInsert(13);bst.BinaryTreeInsert(23);bst.BinaryTreeInsert(45);bst.BinaryTreeInsert(78);bst.BinaryTreeInsert(4);bst.BinaryTreeInsert(17);bst.BinaryTreeInsert(89);bst.BinaryTreeInsert(67);Console.WriteLine(中序遍历打印有序数组);Listint list bst.InorderTraversal();foreach (int i in list){Console.WriteLine(i);}Console.WriteLine(\n);// 查找Console.WriteLine(Search for 45: bst.BinaryTreeSearch(45)); // 输出: TrueConsole.WriteLine(Search for 25: bst.BinaryTreeSearch(25)); // 输出: FalseConsole.WriteLine(\n);// 删除bst.BinaryTreeRemove(17);Console.WriteLine(删除17后,中序遍历打印有序数组);Listint list1 bst.InorderTraversal();foreach (int j in list1){Console.WriteLine(j);}
} 2、运行验证 总结
