声明，本文所有11道算法题目，覆盖了基本上所有常见的二叉树问题，全都用C#实现，并测试通过，代码下载：BinNode.zip
目录：
1.二叉树三种周游（traversal）方式：
2.怎样从顶部开始逐层打印二叉树结点数据
3.如何判断一棵二叉树是否是平衡二叉树
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
5.如何不用递归实现二叉树的前序/后序/中序遍历？
6.在二叉树中找出和为某一值的所有路径
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
8.判断整数序列是不是二叉搜索树的后序遍历结果
9.求二叉树的镜像
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
11.把二叉搜索树转变成排序的双向链表
首先写一个二叉树的C#实现，这是我们的基石：
public class BinNode { public int Element; public BinNode Left; public BinNode Right; public BinNode(int element, BinNode left, BinNode right) { this.Element = element; this.Left = left; this.Right = right; } public bool IsLeaf() { return this.Left == null && this.Right == null; } }
1.二叉树三种周游（traversal）方式：
1）前序周游（preorder）：节点 –> 子节点Left（包括其子树） –> 子节点Right（包括其子树）
static void PreOrder(BinNode root) { if (root == null) return; //visit current node Console.WriteLine(root.Element); PreOrder(root.Left); PreOrder(root.Right); }
2）后序周游（postorder）：子节点Left（包括其子树） –> 子节点Right（包括其子树） –> 节点
static void PostOrder(BinNode root) { if (root == null) return; PostOrder(root.Left); PostOrder(root.Right); //visit current node Console.WriteLine(root.Element); }
3）中序周游（inorder）：子节点Left（包括其子树） –> 节点 –> 子节点Right（包括其子树）
static void InOrder(BinNode root) { if (root == null) return; InOrder(root.Left); //visit current node Console.WriteLine(root.Element); InOrder(root.Right); }
我们发现，三种周游的code实现，仅仅是访问当前节点的这条语句所在位置不同而已。
2.怎样从顶部开始逐层打印二叉树结点数据
有2种算法：
算法1：基于Queue来实现，也就是广度优先搜索（BFS）的思想
static void PrintTree1(BinNode root) { if (root == null) return; BinNode tmp = null; Queue queue = new Queue(); queue.Enqueue(root); while (queue.Count > 0) { tmp = (BinNode)queue.Dequeue(); Console.WriteLine(tmp.Element); if (tmp.Left != null) queue.Enqueue(tmp.Left); if (tmp.Right != null) queue.Enqueue(tmp.Right); } }
话说，BFS和DFS思想本来是用于图的，但我们不能被传统的思维方式所束缚。
算法2：基于单链表实现
如果没有Queue给我们用，我们只好使用单链表，把每个节点存在单链表的Data中，实现如下：
public class Link { public Link Next; public BinNode Data; public Link(Link next, BinNode data) { this.Next = next; this.Data = data; } }
看过了Queue的实现，我们发现永远是先出队1个（队头），然后入队2个（把出队的Left和Right放到队尾）。
对于单链表而言，我们可以先模拟入队——把first的Data所对应的Left和Right，先后插到second的后面，即 second.Next和second.Next.Next位置，同时second向前走0、1或2次，再次到达链表末尾，这取决于Left和Right 是否为空；然后我们模拟出队——first前进1步。
当first指针走不下去了，那么任务也就结束了。
static void PrintTree2(BinNode root) { if (root == null) return; Link head = new Link(null, root); Link first = head; Link second = head; while (first != null) { if (first.Data.Left != null) { second.Next = new Link(null, first.Data.Left); second = second.Next; } if (first.Data.Right != null) { second.Next = new Link(null, first.Data.Right); second = second.Next; } Console.WriteLine(first.Data.Element); first = first.Next; } }
3.如何判断一棵二叉树是否是平衡二叉树
平衡二叉树的定义，如果任意节点的左右子树的深度相差不超过1，那这棵树就是平衡二叉树。
算法思路：先编写一个计算二叉树深度的函数GetDepth，利用递归实现；然后再递归判断每个节点的左右子树的深度是否相差1
static int GetDepth(BinNode root) { if (root == null) return 0; int leftLength = GetDepth(root.Left); int rightLength = GetDepth(root.Right); return (leftLength > rightLength ? leftLength : rightLength) + 1; }
注意这里的+1，对应于root不为空（算作当前1个深度）
static bool IsBalanceTree(BinNode root) { if (root == null) return true; int leftLength = GetDepth(root.Left); int rightLength = GetDepth(root.Right); int distance = leftLength > rightLength ? leftLength - rightLength : rightLength - leftLength; if (distance > 1) return false; else return IsBalanceTree(root.Left) && IsBalanceTree(root.Right); }
上述程序的逻辑是，只要当前节点root的Left和Right深度差不超过1，就递归判断Left和Right是否也符合条件，直到为Left或Right为null，这意味着它们的深度为0，能走到这一步，前面必然都符合条件，所以整个二叉树都符合条件。
4.设计一个算法，找出二叉树上任意两个节点的最近共同父结点，复杂度如果是O(n2)则不得分。
本题网上有很多算法，都不怎么样。这里提出包氏的两个算法：
算法1：做一个容器，我们在遍历二叉树寻找节点的同时，把从根到节点的路径扔进去（两个节点就是两个容器）。由于根节点最后一个被扔进去，但我们接下来又需要第一个就能访问到它——后进先出，所以这个容器是一个栈。时间复杂度O(N)，空间复杂度O(N)。
static bool GetPositionByNode(BinNode root, BinNode node, ref Stack stack) { if (root == null) return false; if (root == node) { stack.Push(root); return true; } if (GetPositionByNode(root.Left, node, ref stack) || GetPositionByNode(root.Right, node, ref stack)) { stack.Push(root); return true; } return false; }
然后我们要同时弹出这两个容器的元素，直到它们不相等，那么之前那个相等的元素就是我们要求的父亲节点。
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2) { Stack stack1 = new Stack(); GetPositionByNode(root, node1, ref stack1); Stack stack2 = new Stack(); GetPositionByNode(root, node2, ref stack2); BinNode tempNode = null; while (stack1.Peek() == stack2.Peek()) { tempNode = (BinNode)stack1.Pop(); stack2.Pop(); } return tempNode; }
算法2：如果要求o(1)的空间复杂度，就是说，只能用一个变量来辅助我们。
我们选择一个64位的整数，然后从1开始，从左到右逐层为二叉树的每个元素赋值，root对应1，root.Left对应2，root.Right对应3，依次类推，而不管实际这个位置上是否有节点，我们发现两个规律：
//// 1
//// 2 3
//// 4 5 6 7
//// 8 9 10
如果要找的是5和9位置上的节点。
我们发现，它们的二进制分别是101和1001，右移1001使之与101位数相同，于是1001变成了100（也就是9的父亲4）。
这时101和100（也就是4和5位于同样的深度），我们从左往右找，101和100具有2位相同，即10，这就是我们要找的4和5的父亲，也就是9和5的最近父亲。
由上面观察，得到算法：
1)将找到的两个节点对应的数字
static bool GetPositionByNode(BinNode root, BinNode node, ref int pos) { if (root == null) return false; if (root == node) return true; int temp = pos; //这么写很别扭，但是能保证只要找到就不再进行下去 pos = temp * 2; if (GetPositionByNode(root.Left, node, ref pos)) { return true; } else { //找不到左边找右边 pos = temp * 2 + 1; return GetPositionByNode(root.Right, node, ref pos); } }
2)它们的二进制表示，从左向右逐一比较，直到一个结束或不再相同，则最大的相同子串，就是我们需要得到的最近父亲所对应的位置K。
static int FindParentPosition(int larger, int smaller) { if (larger == smaller) return larger; int left = GetLen(larger) - GetLen(smaller); while (left > 0) { larger = larger >> 1; left--; } while (larger != smaller) { larger = larger >> 1; smaller = smaller >> 1; } return smaller; } static int GetLen(int num) { int length = 0; while (num != 0) { num = num >> 1; length++; } return length; }
3)第3次递归遍历，寻找K所对应的节点。
函数GetNodeByPosition的思想是，先算出k在第几层power，观察k的二进制表示，比如说12，即1100，从左向右数第一个位1不算，还剩下100，1表示向右走，0表示向左走，于是从root出发，1->3->6->12。
static BinNode GetNodeByPosition(BinNode root, int num) { if (num == 1) return root; int pow = (int)Math.Floor(Math.Log(num, 2)); //1 return 0, 2-3 return 1, 4-7 return 2 //第一个位不算 num -= 1 << pow; while (pow > 0) { if ((num & 1 << (pow - 1)) == 0) root = root.Left; else root = root.Right; pow--; } return root; }
总结上面的3个步骤：
static BinNode FindParentNode(BinNode root, BinNode node1, BinNode node2) { int pos1 = 1; GetPositionByNode(root, node1, ref pos1); int pos2 = 1; GetPositionByNode(root, node2, ref pos2); int parentposition = 0; if (pos1 >= pos2) { parentposition = FindParentPosition(pos1, pos2); } else //pos1<pos2 { parentposition = FindParentPosition(pos2, pos1); } return GetNodeByPosition(root, parentposition); }
5.如何不用递归实现二叉树的前序/后序/中序遍历？
算法思想：三种算法的思想都是让root的Left的Left的Left全都入栈。所以第一个while循环的逻辑，都是相同的。
下面详细分析第2个while循环，这是一个出栈动作，只要栈不为空，就始终要弹出栈顶元素，由于我们之前入栈的都是Left节点，所以每次在出栈的时候，我们都要考虑Right节点是否存在。因为前序/后序/中序遍历顺序的不同，所以在具体的实现上有略为区别。
1)前序遍历
这个是最简单的。
前序遍历是root->root.Left->root.Right的顺序。
因为在第一个while循环中，每次进栈的都可以认为是一个root，所以我们直接打印，然后root.Right和root.Left先后进栈，那么出栈的时候，就能确保先左后右的顺序。
static void PreOrder(BinNode root) { Stack stack = new Stack(); BinNode temp = root; //入栈 while (temp != null) { Console.WriteLine(temp.Element); if (temp.Right != null) stack.Push(temp.Right); temp = temp.Left; } //出栈，当然也有入栈 while (stack.Count > 0) { temp = (BinNode)stack.Pop(); Console.WriteLine(temp.Element); while (temp != null) { if (temp.Right != null) stack.Push(temp.Right); temp = temp.Left; } } }
//后序遍历比较麻烦，需要记录上一个访问的节点，然后在本次循环中判断当前节点的Right或Left是否为上个节点，当前节点的Right为null表示没有右节点。 static void PostOrder(BinNode root) { Stack stack = new Stack(); BinNode temp = root; //入栈 while (temp != null) { if (temp != null) stack.Push(temp); temp = temp.Left; } //出栈，当然也有入栈 while (stack.Count > 0) { BinNode lastvisit = temp; temp = (BinNode)stack.Pop(); if (temp.Right == null || temp.Right == lastvisit) { Console.WriteLine(temp.Element); } else if (temp.Left == lastvisit) { stack.Push(temp); temp = temp.Right; stack.Push(temp); while (temp != null) { if (temp.Left != null) stack.Push(temp.Left); temp = temp.Left; } } } }
//中序遍历，类似于前序遍历 static void InOrder(BinNode root) { Stack stack = new Stack(); BinNode temp = root; //入栈 while (temp != null) { if (temp != null) stack.Push(temp); temp = temp.Left; } //出栈，当然也有入栈 while (stack.Count > 0) { temp = (BinNode)stack.Pop(); Console.WriteLine(temp.Element); if (temp.Right != null) { temp = temp.Right; stack.Push(temp); while (temp != null) { if (temp.Left != null) stack.Push(temp.Left); temp = temp.Left; } } } }
6.在二叉树中找出和为某一值的所有路径
算法思想：这道题目的苦恼在于，如果用递归，只能打出一条路径来，其它符合条件的路径打不出来。
为此，我们需要一个Stack，来保存访问过的节点，即在对该节点的递归前让其进栈，对该节点的递归结束后，再让其出栈——深度优先原则（DFS）。
此外，在递归中，如果发现某节点（及其路径）符合条件，如何从头到尾打印是比较头疼的，因为DFS使用的是stack而不是queue，为此我们需要一个临时栈，来辅助打印。
static void FindBinNode(BinNode root, int sum, Stack stack) { if (root == null) return; stack.Push(root.Element); //Leaf if (root.IsLeaf()) { if (root.Element == sum) { Stack tempStack = new Stack(); while (stack.Count > 0) { tempStack.Push(stack.Pop()); } while (tempStack.Count > 0) { Console.WriteLine(tempStack.Peek()); stack.Push(tempStack.Pop()); } Console.WriteLine(); } } if (root.Left != null) FindBinNode(root.Left, sum - root.Element, stack); if (root.Right != null) FindBinNode(root.Right, sum - root.Element, stack); stack.Pop(); }
7.怎样编写一个程序，把一个有序整数数组放到二叉树中？
算法思想：我们该如何构造这棵二叉树呢？当然是越平衡越好，如下所示：
//// arr[0]
//// arr[1] arr[2]
//// arr[3] arr[4] arr[5]
相应编码如下：
public static void InsertArrayIntoTree(int[] arr, int pos, ref BinNode root) { root = new BinNode(arr[pos], null, null); root.Element = arr[pos]; //if Left value less than arr length if (pos * 2 + 1 > arr.Length - 1) { return; } else { InsertArrayIntoTree(arr, pos * 2 + 1, ref root.Left); } //if Right value less than arr length if (pos * 2 + 2 > arr.Length - 1) { return; } else { root.Right = new BinNode(arr[pos * 2 + 2], null, null); InsertArrayIntoTree(arr, pos * 2 + 2, ref root.Right); } }
8.判断整数序列是不是二叉搜索树的后序遍历结果
比如，给你一个数组： int a[] = [1, 6, 4, 3, 5] ，则F(a) => false
算法思想：在后续遍历得到的序列中，最后一个元素为树的根结点。从头开始扫描这个序列，比根结点小的元素都应该位于序列的左半部分；从第一个大于跟 结点开始到跟结点前面的一个元素为止，所有元素都应该大于跟结点，因为这部分元素对应的是树的右子树。根据这样的划分，把序列划分为左右两部分，我们递归 地确认序列的左、右两部分是不是都是二元查找树。
由于不能使用动态数组，所以我们每次递归都使用同一个数组arr，通过start和length来模拟“部分”数组。
public static bool VerifyArrayOfBST(int[] arr, int start, int length) { if (arr == null || arr.Length == 0 || arr.Length == 1) { return false; } int root = arr[length + start - 1]; int i = start; for (; i < length - 1; i++) { if (arr[i] >= root) break; } int j = i; for (; j < length - 1; j++) { if (arr[j] < root) return false; } bool left = true; if (i > start) { left = VerifyArrayOfBST(arr, start, i - start); } bool right = true; if (j > i) { right = VerifyArrayOfBST(arr, i, j - i + 1); } return left && right; }
9.求二叉树的镜像
算法1：利用上述遍历二叉树的方法（比如说前序遍历），把访问操作修改为交换左右节点的逻辑：
static void PreOrder(ref BinNode root) { if (root == null) return; //visit current node BinNode temp = root.Left; root.Left = root.Right; root.Right = temp; PreOrder(ref root.Left); PreOrder(ref root.Right); }
算法2：使用循环也可以完成相同的功能。
static void PreOrder2(ref BinNode root) { if (root == null) return; Stack stack = new Stack(); stack.Push(root); while (stack.Count > 0) { //visit current node BinNode temp = root.Left; root.Left = root.Right; root.Right = temp; if (root.Left != null) stack.Push(root.Left); if (root.Right != null) stack.Push(root.Right); } }
10.一棵排序二叉树（即二叉搜索树BST），令 f=(最大值+最小值)/2，设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
算法思想：最小最大节点分别在最左下与最右下节点，O(N)
static BinNode Find(BinNode root) { BinNode min = FindMinNode(root); BinNode max = FindMaxNode(root); double find = (double)(min.Element + max.Element) / 2; return FindNode(root, find); }
static BinNode FindMinNode(BinNode root) { BinNode min = root; while (min.Left != null) { min = min.Left; } return min; } static BinNode FindMaxNode(BinNode root) { BinNode max = root; while (max.Right != null) { max = max.Right; } return max; }
递归寻找BST的节点，O(logN)。
static BinNode FindNode(BinNode root, double mid) { //如果小于相等，则从右边找一个最小值 if (root.Element <= mid) { if (root.Right == null) return root; BinNode find = FindNode(root.Right, mid); //不一定找得到 return find.Element < mid ? root : find; } //如果大于，则找到Left else //temp.Element > find { if (root.Left == null) return root; BinNode find = FindNode(root.Left, mid); //不一定找得到 return find.Element < mid ? root : find; } }
11.把二叉搜索树转变成排序的双向链表，如
//// 13
//// 10 15
//// 5 11 17
//// 16 22
转变为Link：5=10=11=13=15=16=17=22
算法思想：这个就是中序遍历啦，因为BST的中序遍历就是一个从小到大的访问顺序。局部修改中序遍历算法，于是有如下代码：
static void ConvertNodeToLink(BinNode root, ref DoubleLink link) { if (root == null) return; BinNode temp = root; if (temp.Left != null) ConvertNodeToLink(temp.Left, ref link); //visit current node link.Next = new DoubleLink(link, null, root); link = link.Next; if (temp.Right != null) ConvertNodeToLink(temp.Right, ref link); }
但是我们发现，这样得到的Link是指向双链表最后一个元素22，而我们想要得到的是表头5，为此，我们不得不额外进行while循环，将指针向前移动到表头：
static DoubleLink ReverseDoubleLink(BinNode root, ref DoubleLink link) { ConvertNodeToLink(root, ref link); DoubleLink temp = link; while (temp.Prev != null) { temp = temp.Prev; } return temp; }
这么写有点蠢，为什么不直接在递归中就把顺序反转呢？于是有算法2：
算法2：观察算法1的递归方法，访问顺序是Left -> Root –> Right，所以我们要把访问顺序修改为Right -> Root –> Left。
此外，算法的节点访问逻辑，是连接当前节点和新节点，同时指针link向前走，即5=10=11=13=15=16=17=22=link
代码如下所示：
link.Next = new DoubleLink(link, null, root); link = link.Next;
那么，即使我们颠倒了访问顺序，新的Link也只是变为：22=17=16=15=13=11=10=5=link。
为此，我们修改上面的节点访问逻辑——将Next和Prev属性交换：
link.Prev = new DoubleLink(null, link, root); link = link.Prev;
这样，新的Link就变成这样的顺序了：link=5=10=11=13=15=16=17=22
算法代码如下所示：
static void ConvertNodeToLink2(BinNode root, ref DoubleLink link) { if (root == null) return; BinNode temp = root; if (temp.Right != null) ConvertNodeToLink2(temp.Right, ref link); //visit current node link.Prev = new DoubleLink(null, link, root); link = link.Prev; if (temp.Left != null) ConvertNodeToLink2(temp.Left, ref link); }
以下算法属于二叉树的基本概念，未列出：
1.Huffman Tree的生成、编码和反编码
2.BST的实现
3.Heap的实现，优先队列
4.非平衡二叉树如何变成平衡二叉树？
http://www.cppblog.com/bellgrade/archive/2009/10/12/98402.html
玩二叉树，基本都要用到递归算法。
唉，对于递归函数，我一直纠结，到底要不要返回值？到底先干正事还是先递归？到底要不要破坏原来的数据结构？到底要不要额外做个 stack/queue/link/array来转存，还是说完全在递归里面实现？到底终结条件要写成什么样子？ ref在递归里面貌似用的很多哦。
原文地址：http://www.cnblogs.com/Jax/archive/2009/12/28/1633691.html
相关推荐
二叉树算法源码~~~C++实现的~~数据结构运用，充分应用了二叉树的模板实现的~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 二叉树算法源码~~~C++实现的~~~数据结构运用~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
最优二叉树 最优二叉树算法
在本文中，我们将深入探讨C语言中的二叉树算法。二叉树是一种数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。在C程序中，我们可以使用结构体来表示二叉树的节点，并实现对二叉树的各种操作，...
"树与二叉树算法汇总" 本资源摘要信息主要讨论树与二叉树算法，涵盖树与二叉树的表示、遍历和操作等方面的知识点。 一、树与二叉树的表示 树是一种基本的数据结构，用于存储具有层次关系的数据。二叉树是树的一种...
在C#中实现二叉树算法可以帮助我们理解和解决复杂的数据结构问题。本篇文章将深入探讨二叉树的原理、常见操作以及如何在C#中实现这些算法。 二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，通常称为左...
这篇博客"java二叉树算法（转）"可能会探讨如何在Java中实现和操作二叉树，特别是涉及算法的部分。二叉树通常用于搜索、排序和组织数据，其特性是每个节点最多有两个子节点，通常分为左子节点和右子节点。 二叉树的...
二叉树算法的动画演示软件开发 本资源是关于二叉树算法的动画演示软件开发的毕业设计论文。论文首先介绍了二叉树算法的重要性和必要性，然后详细介绍了二叉树算法的动画演示软件的开发背景、开发意义、应用目标、...
这是一个基于生成树的算法，可以先用回溯、递推求出二叉树，再用二叉树求解，主要用于遍历问题！
树与二叉树算法总结 树与二叉树是计算机科学中非常重要的一部分，掌握树与二叉树的算法对于数据结构和算法设计非常重要。本文将对树与二叉树的基本概念、性质、运算和应用进行总结。 一、树的基本概念 树是一种非...
（3）中序遍历二叉树:非递归算法（最好也能实现先序，后序非递归算法）。 （4）求二叉树的高度 。 （5）求二叉树的叶子个数。 （6）对于树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。 （8...
本文将深入探讨在VS2005环境下实现二叉树算法的相关知识点。 首先，我们要理解什么是二叉树。二叉树是一种特殊的树形数据结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。二叉树可以分为两种类型：满...
"按层次遍历二叉树的算法" 按层次遍历二叉树的算法是指从树的根结点开始，逐层遍历树的所有结点，直到遍历完整个树。这种遍历方式可以分为两种：宽度优先遍历（Breadth-First Traversal）和深度优先遍历（Depth-...
二叉树算法是一种高效且灵活的排序方法，尤其在处理复杂数据结构时具有显著优势。本资源提供了使用C#实现的二叉树排序功能，不仅能够对常规数据进行排序，还能处理更复杂的自定义数据类型。 首先，我们来了解一下...
在这个"二叉树算法集用C语言实现"的压缩包中，我们可以期待看到一系列的C语言源代码，用于实现与二叉树相关的各种操作和算法。 首先，建立二叉树的过程通常涉及到动态地创建节点并连接它们。在C语言中，这可能通过...
本系统突出从教师教学环节中的难点和学生易于出错的知识点这两方面出发，解决了现有二叉树算法演示软件不能满足计算机教师教学要求的问题，可以使学生更好地理解二叉树的基本算法及操作，也可以使教师的教学工作更加...
二叉树算法，二叉树的删除，添加，排序
2、先序遍历（递归算法）\n"); 3、中序遍历（递归算法）\n");4、后序遍历（递归算法）\n"); 5、中序遍历（非递归算法）\n"); 6、求二叉树的高度\n"); 7、求二叉树叶子个数\n");8、借助队列实现二叉树层次遍历