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

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。

相关文章

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法

《golang获取当前时间、时间戳和时间字符串及它们之间的相互转换方法》：本文主要介绍golang获取当前时间、时间戳和时间字符串及它们之间的相互转换,本文通过实例代码给大家介绍的非常详细,感兴趣... 目录1、获取当前时间2、获取当前时间戳3、获取当前时间的字符串格式4、它们之间的相互转化上篇文章给大家介
阅读更多...
Vue中组件之间传值的六种方式（完整版）

Vue中组件之间传值的六种方式（完整版）

《Vue中组件之间传值的六种方式（完整版）》组件是vue.js最强大的功能之一,而组件实例的作用域是相互独立的,这就意味着不同组件之间的数据无法相互引用,针对不同的使用场景,如何选择行之有效的通信方式... 目录前言方法一、props/$emit1.父组件向子组件传值2.子组件向父组件传值（通过事件形式）方
阅读更多...
C语言实现两个变量值交换的三种方式

C语言实现两个变量值交换的三种方式

《C语言实现两个变量值交换的三种方式》两个变量值的交换是编程中最常见的问题之一,以下将介绍三种变量的交换方式,其中第一种方式是最常用也是最实用的,后两种方式一般只在特殊限制下使用,需要的朋友可以参考下... 目录1.使用临时变量（推荐）2.相加和相减的方式（值较大时可能丢失数据）3.按位异或运算1.使用临时
阅读更多...
Python实现PDF与多种图片格式之间互转(PNG, JPG, BMP, EMF, SVG)

Python实现PDF与多种图片格式之间互转(PNG, JPG, BMP, EMF, SVG)

《Python实现PDF与多种图片格式之间互转(PNG,JPG,BMP,EMF,SVG)》PDF和图片是我们日常生活和工作中常用的文件格式,有时候,我们可能需要将PDF和图片进行格式互转来满足... 目录一、介绍二、安装python库三、Python实现多种图片格式转PDF1、单张图片转换为PDF2、多张图
阅读更多...
java两个List的交集,并集方式

java两个List的交集,并集方式

《java两个List的交集,并集方式》文章主要介绍了Java中两个List的交集和并集的处理方法,推荐使用Apache的CollectionUtils工具类,因为它简单且不会改变原有集合,同时,文章... 目录Java两个List的交集,并集方法一方法二方法三总结java两个List的交集,并集方法一
阅读更多...
Java对象和JSON字符串之间的转换方法(全网最清晰)

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》：本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为
阅读更多...
Python如何计算两个不同类型列表的相似度

Python如何计算两个不同类型列表的相似度

《Python如何计算两个不同类型列表的相似度》在编程中,经常需要比较两个列表的相似度,尤其是当这两个列表包含不同类型的元素时,下面小编就来讲讲如何使用Python计算两个不同类型列表的相似度吧... 目录摘要引言数字类型相似度欧几里得距离曼哈顿距离字符串类型相似度Levenshtein距离Jaccard相
阅读更多...
java父子线程之间实现共享传递数据

java父子线程之间实现共享传递数据

《java父子线程之间实现共享传递数据》本文介绍了Java中父子线程间共享传递数据的几种方法,包括ThreadLocal变量、并发集合和内存队列或消息队列,并提醒注意并发安全问题... 目录通过 ThreadLocal 变量共享数据通过并发集合共享数据通过内存队列或消息队列共享数据注意并发安全问题总结在 J
阅读更多...
使用Navicat工具比对两个数据库所有表结构的差异案例详解

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》：本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较：二、开始比较总结概要公司存在多
阅读更多...
Java文件与Base64之间的转化方式

Java文件与Base64之间的转化方式

《Java文件与Base64之间的转化方式》这篇文章介绍了如何使用Java将文件（如图片、视频）转换为Base64编码,以及如何将Base64编码转换回文件,通过提供具体的工具类实现,作者希望帮助读者... 目录Java文件与Base64之间的转化1、文件转Base64工具类2、Base64转文件工具类3、
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2