求满二叉树两个节点之间的最短距离

2024-02-11 18:20
文章标签 二叉树 节点 两个 之间 短距离 求满

本文主要是介绍求满二叉树两个节点之间的最短距离，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

求满二叉树两个节点之间的最短距离

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;namespace FirstSolver
{internal class Program{static void Main(string[] args){BinaryTreeNode<int> root1 = FullBinaryTree.CreateTree(1, 4);Console.WriteLine(FullBinaryTree.PrintTree(root1));Console.WriteLine();BinaryTreeNode<int> root2 = FullBinaryTree.CreateTree(101, 4);Console.WriteLine(FullBinaryTree.PrintTree(root2));Console.WriteLine();BinaryTreeNode<int> root3 = FullBinaryTree.CreateTree(201, 4);Console.WriteLine(FullBinaryTree.PrintTree(root3));Console.WriteLine();root1.ParentNode = root2;root2.ParentNode = root3;root3.ParentNode = root1;BinaryTreeNode<int> nodeA = FullBinaryTree.FindNode(root1, 5);BinaryTreeNode<int> nodeB = FullBinaryTree.FindNode(root1, 7);Console.WriteLine($"[A({nodeA.Value})]->[B({nodeB.Value})]");Stack<BinaryTreeNode<int>> path = FullBinaryTree.FindPath(nodeA, nodeB);Console.WriteLine(FullBinaryTree.PrintPath(path));Console.WriteLine(FullBinaryTree.PrintPath(FullBinaryTree.QuickFindPath(nodeA, nodeB)));Console.WriteLine();nodeB = FullBinaryTree.FindNode(root2, 107);Console.WriteLine($"[A({nodeA.Value})]->[B({nodeB.Value})]");path = FullBinaryTree.FindPath(nodeA, nodeB);Console.WriteLine(FullBinaryTree.PrintPath(path));Console.WriteLine(FullBinaryTree.PrintPath(FullBinaryTree.QuickFindPath(nodeA, nodeB)));Console.WriteLine();nodeB = FullBinaryTree.FindNode(root3, 207);Console.WriteLine($"[A({nodeA.Value})]->[B({nodeB.Value})]");path = FullBinaryTree.FindPath(nodeA, nodeB);Console.WriteLine(FullBinaryTree.PrintPath(path));Console.WriteLine(FullBinaryTree.PrintPath(FullBinaryTree.QuickFindPath(nodeA, nodeB)));Console.WriteLine();// 测试是否死循环nodeB = new BinaryTreeNode<int>(301);Console.WriteLine($"[A({nodeA.Value})]->[B({nodeB.Value})]");path = FullBinaryTree.FindPath(nodeA, nodeB);Console.WriteLine(FullBinaryTree.PrintPath(path));Console.WriteLine(FullBinaryTree.PrintPath(FullBinaryTree.QuickFindPath(nodeA, nodeB)));Console.WriteLine();Console.ReadKey();}}/// <summary>/// 满二叉树/// </summary>/// <typeparam name="T">数据类型</typeparam>public static class FullBinaryTree{/// <summary>/// 创建深度为depth的满二叉树/// </summary>/// <param name="intial">初始值</param>/// <param name="depth">深度</param>/// <returns>满二叉树头结点</returns>public static BinaryTreeNode<int> CreateTree(int intial, int depth){BinaryTreeNode<int> header = new BinaryTreeNode<int>(intial);CreateSub(header, intial, 2, depth);return header;}/// <summary>/// 创建子树/// </summary>/// <param name="node">父节点</param>/// <param name="initial">根节点初始值</param>/// <param name="level">层级</param>/// <param name="depth">深度</param>private static void CreateSub(BinaryTreeNode<int> node, int initial, int level, int depth){if (level > depth) return;int value = (node.Value << 1) - (initial - 1);BinaryTreeNode<int> leftChildNode = new BinaryTreeNode<int>(value);BinaryTreeNode<int> rightChildNode = new BinaryTreeNode<int>(value + 1);node.LeftChildNode = leftChildNode;node.RightChildNode = rightChildNode;leftChildNode.ParentNode = node;rightChildNode.ParentNode = node;CreateSub(leftChildNode, initial, level + 1, depth);CreateSub(rightChildNode, initial, level + 1, depth);}/// <summary>/// 打印二叉树/// </summary>/// <param name="header">节点</param>/// <returns>二叉树字符串</returns>public static string PrintTree(BinaryTreeNode<int> header){StringBuilder sb = new StringBuilder($"{header.Value}");if (header.LeftChildNode != null){sb.Append($"({header.LeftChildNode.Value},{header.RightChildNode.Value})");PrintTreeSub(header.LeftChildNode, sb);PrintTreeSub(header.RightChildNode, sb);}return sb.ToString();}private static void PrintTreeSub(BinaryTreeNode<int> node, StringBuilder sb){sb.Append($" {node.Value}");if (node.LeftChildNode != null){sb.Append($"({node.LeftChildNode.Value},{node.RightChildNode.Value})");PrintTreeSub(node.LeftChildNode, sb);PrintTreeSub(node.RightChildNode, sb);}}/// <summary>/// 查找指定值的节点/// </summary>/// <param name="node">二叉树</param>/// <param name="value">要匹配的值</param>/// <returns>找到的节点</returns>public static BinaryTreeNode<int> FindNode(BinaryTreeNode<int> node, int value){if (Equals(node.Value, value)) return node;if (node.LeftChildNode != null){return FindNode(node.LeftChildNode, value) ?? FindNode(node.RightChildNode, value);}return null;}/// <summary>/// 定位根节点/// </summary>/// <param name="node">初始节点</param>/// <returns>根节点</returns>public static BinaryTreeNode<int> GetRootNode(BinaryTreeNode<int> node){while (true){if (node.ParentNode == null) break;if (node.ParentNode.LeftChildNode != node && node.ParentNode.RightChildNode != node) break;node = node.ParentNode;}return node;}/// <summary>/// 寻找节点A到节点B的最短路径/// </summary>/// <param name="nodeA">节点A</param>/// <param name="nodeB">节点B</param>/// <returns>最短路径</returns>public static Stack<BinaryTreeNode<int>> FindPath(BinaryTreeNode<int> nodeA, BinaryTreeNode<int> nodeB){BinaryTreeNode<int> rootA = GetRootNode(nodeA);Stack<BinaryTreeNode<int>> path = new Stack<BinaryTreeNode<int>>();BinaryTreeNode<int> node = nodeA;path.Push(node);bool find = FindPathSub(node, nodeB, path);if (!find){while (!find){if (node.ParentNode == null) break;// 避免死循环if (node.ParentNode == rootA && (node != rootA.LeftChildNode && node != rootA.RightChildNode)) break;path.Push(node.ParentNode);int state = 0; // 进入另一颗二叉树if (node.ParentNode.LeftChildNode == node)state = 1;else if (node.ParentNode.RightChildNode == node)state = 2;if (state == 0 || state == 1){find = FindPathSub(node.ParentNode.RightChildNode, nodeB, path);if (find) break;}if (state == 0 || state == 2){find = FindPathSub(node.ParentNode.LeftChildNode, nodeB, path);if (find) break;}node = node.ParentNode;}}return find ? path : null;}private static bool FindPathSub(BinaryTreeNode<int> node, BinaryTreeNode<int> search, Stack<BinaryTreeNode<int>> path){path.Push(node);if (node == search) return true;if (node.LeftChildNode != null){if (FindPathSub(node.LeftChildNode, search, path)) return true;if (FindPathSub(node.RightChildNode, search, path)) return true;}path.Pop();return false;}/// <summary>/// 获取到根节点的路径/// </summary>/// <param name="node">起始节点</param>/// <returns>到根节点路径</returns>public static List<BinaryTreeNode<int>> GetRootNodePath(BinaryTreeNode<int> node){List<BinaryTreeNode<int>> path = new List<BinaryTreeNode<int>>();path.Add(node);while (true){if (node.ParentNode == null) break;if (node.ParentNode.LeftChildNode != node && node.ParentNode.RightChildNode != node) break;node = node.ParentNode;path.Add(node);}return path;}/// <summary>/// 快速寻找节点A到节点B的最短路径/// </summary>/// <param name="nodeA">节点A</param>/// <param name="nodeB">节点B</param>/// <returns>最短路径</returns>public static List<BinaryTreeNode<int>> QuickFindPath(BinaryTreeNode<int> nodeA, BinaryTreeNode<int> nodeB){List<BinaryTreeNode<int>> pathA = GetRootNodePath(nodeA);List<BinaryTreeNode<int>> pathB = GetRootNodePath(nodeB);BinaryTreeNode<int> rootA = pathA[pathA.Count - 1];BinaryTreeNode<int> rootB = pathB[pathB.Count - 1];if (rootA == rootB){int i = pathA.Count - 2;int j = pathB.Count - 2;for (; i >= 0 && j >= 0; i--, j--){if (pathA[i] != pathB[j]) break;}if (pathA.Count - 2 > i) pathA.RemoveRange(i + 2, pathA.Count - i - 2);pathB.RemoveRange(j + 1, pathB.Count - j - 1);pathB.Reverse();pathA.AddRange(pathB);return pathA;}else{BinaryTreeNode<int> node = rootA;while (node.ParentNode != null){node = node.ParentNode;if (node == rootB){pathB.Reverse();pathA.AddRange(pathB);return pathA;}else if (node == rootA){   // 避免死循环break;}pathA.Add(node);}return null;}            }/// <summary>/// 打印路径/// </summary>/// <param name="path">路径</param>/// <returns>路径字符串</returns>      public static string PrintPath(IEnumerable<BinaryTreeNode<int>> path){if (path == null) return "No Path!"; // 没有路径到达IEnumerable<BinaryTreeNode<int>> p = path;if (path is Stack<BinaryTreeNode<int>>){p = p.Reverse();}            StringBuilder sb = new StringBuilder();foreach (var item in p){sb.Append($"{item.Value}->");}sb.Remove(sb.Length - 2, 2);return sb.ToString();}}/// <summary>/// 节点定义/// </summary>/// <typeparam name="T">节点数据类型：要求值类型</typeparam>public class BinaryTreeNode<T> where T : struct{public T Value { get; set; }public BinaryTreeNode<T> ParentNode { get; set; }public BinaryTreeNode<T> LeftChildNode { get; set; }public BinaryTreeNode<T> RightChildNode { get; set; }public BinaryTreeNode() { Value = default; }public BinaryTreeNode(T value) { Value = value; }}
}

这篇关于求满二叉树两个节点之间的最短距离的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/700506。

相关文章

锐捷和腾达哪个好? 两个品牌路由器对比分析

锐捷和腾达哪个好? 两个品牌路由器对比分析

《锐捷和腾达哪个好?两个品牌路由器对比分析》在选择路由器时，Tenda和锐捷都是备受关注的品牌，各自有独特的产品特点和市场定位，选择哪个品牌的路由器更合适，实际上取决于你的具体需求和使用场景，我们从... 在选购路由器时，锐捷和腾达都是市场上备受关注的品牌，但它们的定位和特点却有所不同。锐捷更偏向企业级和专
阅读更多...
【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【前端学习】AntV G6-08 深入图形与图形分组、自定义节点、节点动画（下）

【课程链接】 AntV G6：深入图形与图形分组、自定义节点、节点动画（下）_哔哩哔哩_bilibili 本章十吾老师讲解了一个复杂的自定义节点中，应该怎样去计算和绘制图形，如何给一个图形制作不间断的动画，以及在鼠标事件之后产生动画。（有点难，需要好好理解） <!DOCTYPE html><html><head><meta charset="UTF-8"><title>06
阅读更多...
day-51 合并零之间的节点

day-51 合并零之间的节点

思路 直接遍历链表即可，遇到val=0跳过，val非零则加在一起，最后返回即可 解题过程 返回链表可以有头结点，方便插入，返回head.next Code /*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}*
阅读更多...
两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

两个月冲刺软考——访问位与修改位的题型(淘汰哪一页)；内聚的类型；关于码制的知识点；地址映射的相关内容

1.访问位与修改位的题型(淘汰哪一页) 访问位：为1时表示在内存期间被访问过，为0时表示未被访问；修改位：为1时表示该页面自从被装入内存后被修改过，为0时表示未修改过。 置换页面时，最先置换访问位和修改位为00的，其次是01(没被访问但被修改过)的，之后是10(被访问了但没被修改过)，最后是11。 2.内聚的类型 功能内聚：完成一个单一功能，各个部分协同工作，缺一不可。 顺序内聚：
阅读更多...
【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟）

【每日一题】LeetCode 2181.合并零之间的节点（链表、模拟） 题目描述 给定一个链表，链表中的每个节点代表一个整数。链表中的整数由 0 分隔开，表示不同的区间。链表的开始和结束节点的值都为 0。任务是将每两个相邻的 0 之间的所有节点合并成一个节点，新节点的值为原区间内所有节点值的和。合并后，需要移除所有的 0，并返回修改后的链表头节点。 思路分析 初始化：创建一个虚拟头节点
阅读更多...
leetcode105 从前序与中序遍历序列构造二叉树

leetcode105 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7]中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3/ \9 20/ \15 7   class Solution {public TreeNode buildTree(int[] pr
阅读更多...
linux中使用rust语言在不同进程之间通信

linux中使用rust语言在不同进程之间通信

第一种：使用mmap映射相同文件 fn main() {let pid = std::process::id();println!(
阅读更多...
JS和jQuery获取节点的兄弟，父级，子级元素

JS和jQuery获取节点的兄弟，父级，子级元素

原文转自http://blog.csdn.net/duanshuyong/article/details/7562423 先说一下JS的获取方法，其要比JQUERY的方法麻烦很多，后面以JQUERY的方法作对比。 JS的方法会比JQUERY麻烦很多，主要则是因为FF浏览器，FF浏览器会把你的换行也当最DOM元素。 <div id="test"><div></div><div></div
阅读更多...
PHP实现二叉树遍历(非递归方式，栈模拟实现)

PHP实现二叉树遍历(非递归方式，栈模拟实现)

二叉树定义是这样的：一棵非空的二叉树由根结点及左、右子树这三个基本部分组成，根据节点的访问位置不同有三种遍历方式： ① NLR：前序遍历(PreorderTraversal亦称(先序遍历)) ——访问结点的操作发生在遍历其左右子树之前。 ② LNR：中序遍历(InorderTraversal) ——访问结点的操作发生在遍历其左右子树之中(间)。 ③ LRN：后序遍历(PostorderT
阅读更多...
O(n)时间内对[0..n^-1]之间的n个数排序

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内，对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序，每个数有两位，每位的取值范围是[0..n-1]，再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2