|
目录
二叉树三种周游（traversal）方式
怎样从顶部开始逐层打印二叉树结点数据
如何判断一棵二叉树是否是平衡二叉树
设计一个算法找出二叉树上任意两个节点的最近共同父结点复杂度如果是O(n)则不得分
如何不用递归实现二叉树的前序/后序/中序遍历？
在二叉树中找出和为某一值的所有路径
怎样编写一个程序把一个有序整数数组放到二叉树中？
判断整数序列是不是二叉搜索树的后序遍历结果
求二叉树的镜像
一棵排序二叉树（即二叉搜索树BST）令 f=(最大值+最小值)/设计一个算法找出距离f值最近大于f值的结点复杂度如果是O(n)则不得分
把二叉搜索树转变成排序的双向链表 首先写一个二叉树的C#实现这是我们的基石
public class BinNode
{
public int Element;
public BinNode Left;
public BinNode Right;
public BinNode(int element BinNode left BinNode right)
{
thisElement = element;
thisLeft = left;
thisRight = right;
} public bool IsLeaf()
{
return thisLeft == null &#;&#; thisRight == null;
}
} 二叉树三种周游（traversal）方式
）前序周游（preorder）节点 –> 子节点Left（包括其子树） –> 子节点Right（包括其子树）
static void PreOrder(BinNode root)
{
if (root == null)
return;
//visit current node
ConsoleWriteLine(rootElement);
PreOrder(rootLeft);
PreOrder(rootRight);
} ）后序周游（postorder）子节点Left（包括其子树） –> 子节点Right（包括其子树） –> 节点
static void PostOrder(BinNode root)
{
if (root == null)
return;
PostOrder(rootLeft);
PostOrder(rootRight);
//visit current node
ConsoleWriteLine(rootElement);
} ）中序周游（inorder）子节点Left（包括其子树） –> 节点 –> 子节点Right（包括其子树）
static void InOrder(BinNode root)
{
if (root == null)
return;
InOrder(rootLeft);
//visit current node
ConsoleWriteLine(rootElement);
InOrder(rootRight);
} 我们发现三种周游的code实现仅仅是访问当前节点的这条语句所在位置不同而已 怎样从顶部开始逐层打印二叉树结点数据
有种算法
算法基于Queue来实现也就是广度优先搜索（BFS）的思想
static void PrintTree(BinNode root)
{
if (root == null) return;
BinNode tmp = null;
Queue queue = new Queue();
queueEnqueue(root);
while (queueCount > )
{
tmp = (BinNode)queueDequeue();
ConsoleWriteLine(tmpElement);
if (tmpLeft != null)
queueEnqueue(tmpLeft);
if (tmpRight != null)
queueEnqueue(tmpRight);
}
} 话说BFS和DFS思想本来是用于图的但我们不能被传统的思维方式所束缚 算法基于单链表实现
如果没有Queue给我们用我们只好使用单链表把每个节点存在单链表的Data中实现如下
public class Link
{
public Link Next;
public BinNode Data;
public Link(Link next BinNode data)
{
thisNext = next;
thisData = data;
}
}
看过了Queue的实现我们发现永远是先出队个（队头）然后入队个（把出队的Left和Right放到队尾）
对于单链表而言我们可以先模拟入队——把first的Data所对应的Left和Right先后插到second的后面即secondNext和secondNextNext位置同时second向前走或次再次到达链表末尾这取决于Left和Right是否为空然后我们模拟出队——first前进步
当first指针走不下去了那么任务也就结束了
static void PrintTree(BinNode root)
{
if (root == null) return;
Link head = new Link(null root);
Link first = head;
Link second = head;
while (first != null)
{
if (firstDataLeft != null)
{
secondNext = new Link(null firstDataLeft);
second = secondNext;
}
if (firstDataRight != null)
{
secondNext = new Link(null firstDataRight);
second = secondNext;
}
ConsoleWriteLine(firstDataElement);
first = firstNext;
}
} 如何判断一棵二叉树是否是平衡二叉树
平衡二叉树的定义如果任意节点的左右子树的深度相差不超过那这棵树就是平衡二叉树
算法思路先编写一个计算二叉树深度的函数GetDepth利用递归实现然后再递归判断每个节点的左右子树的深度是否相差
static int GetDepth(BinNode root)
{
if (root == null)
return ;
int leftLength = GetDepth(rootLeft);
int rightLength = GetDepth(rootRight);
return (leftLength > rightLength
leftLength : rightLength) + ;
} 注意这里的+对应于root不为空（算作当前个深度）
static bool IsBalanceTree(BinNode root)
{
if (root == null)
return true;
int leftLength = GetDepth(rootLeft);
int rightLength = GetDepth(rootRight);
int distance = leftLength > rightLength
leftLength &#; rightLength : rightLength &#; leftLength; if (distance > )
return false;
else
return IsBalanceTree(rootLeft) &#;&#; IsBalanceTree(rootRight);
} 上述程序的逻辑是只要当前节点root的Left和Right深度差不超过就递归判断Left和Right是否也符合条件直到为Left或Right为null这意味着它们的深度为能走到这一步前面必然都符合条件所以整个二叉树都符合条件 设计一个算法找出二叉树上任意两个节点的最近共同父结点复杂度如果是O(n)则不得分
本题网上有很多算法都不怎么样这里提出包氏的两个算法
算法做一个容器我们在遍历二叉树寻找节点的同时把从根到节点的路径扔进去（两个节点就是两个容器）由于根节点最后一个被扔进去但我们接下来又需要第一个就能访问到它——后进先出所以这个容器是一个栈时间复杂度O(N)空间复杂度O(N)
static bool GetPositionByNode(BinNode root BinNode node ref Stack stack)
{
if (root == null)
return false;
if (root == node)
{
stackPush(root);
return true;
}
if (GetPositionByNode(rootLeft node ref stack) || GetPositionByNode(rootRight node ref stack))
{
stackPush(root);
return true;
}
return false;
} 然后我们要同时弹出这两个容器的元素直到它们不相等那么之前那个相等的元素就是我们要求的父亲节点
static BinNode FindParentNode(BinNode root BinNode node BinNode node)
{
Stack stack = new Stack();
GetPositionByNode(root node ref stack);
Stack stack = new Stack();
GetPositionByNode(root node ref stack);
BinNode tempNode = null;
while (stackPeek() == stackPeek())
{
tempNode = (BinNode)stackPop();
stackPop();
}
return tempNode;
} 算法如果要求o()的空间复杂度就是说只能用一个变量来辅助我们
我们选择一个位的整数然后从开始从左到右逐层为二叉树的每个元素赋值root对应rootLeft对应rootRight对应依次类推而不管实际这个位置上是否有节点我们发现两个规律
////
////
////
////
如果要找的是和位置上的节点
我们发现它们的二进制分别是和右移使之与位数相同于是变成了（也就是的父亲）
这时和（也就是和位于同样的深度）我们从左往右找和具有位相同即这就是我们要找的和的父亲也就是和的最近父亲
由上面观察得到算法
)将找到的两个节点对应的数字
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 * ;
if (GetPositionByNode(rootLeft node ref pos))
{
return true;
}
else
{
//找不到左边找右边
pos = temp * + ;
return GetPositionByNode(rootRight node ref pos);
}
}
)它们的二进制表示从左向右逐一比较直到一个结束或不再相同则最大的相同子串就是我们需要得到的最近父亲所对应的位置K
static int FindParentPosition(int larger int smaller)
{
if (larger == smaller) return larger;
int left = GetLen(larger) &#; GetLen(smaller);
while (left > )
{
larger = larger >> ;
left&#;;
}
while (larger != smaller)
{
larger = larger >> ;
smaller = smaller >> ;
}
return smaller;
}
static int GetLen(int num)
{
int length = ;
while (num != )
{
num = num >> ;
length++;
}
return length;
}
)第次递归遍历寻找K所对应的节点
函数GetNodeByPosition的思想是先算出k在第几层power观察k的二进制表示比如说即从左向右数第一个位不算还剩下表示向右走表示向左走于是从root出发>>>
static BinNode GetNodeByPosition(BinNode root int num)
{
if (num == ) return root;
int pow = (int)MathFloor(MathLog(num )); // return return return
//第一个位不算
num = << pow;
while (pow > )
{
if ((num &#; << (pow )) == )
root = rootLeft;
else
root = rootRight;
pow;
}
return root;
} 总结上面的个步骤
static BinNode FindParentNode(BinNode root BinNode node BinNode node)
{
int pos = ;
GetPositionByNode(root node ref pos);
int pos = ;
GetPositionByNode(root node ref pos);
int parentposition = ;
if (pos >= pos)
{
parentposition = FindParentPosition(pos pos);
}
else //pos {
parentposition = FindParentPosition(pos pos);
}
return GetNodeByPosition(root parentposition);
} 如何不用递归实现二叉树的前序/后序/中序遍历？
算法思想三种算法的思想都是让root的Left的Left的Left全都入栈所以第一个while循环的逻辑都是相同的
下面详细分析第个while循环这是一个出栈动作只要栈不为空就始终要弹出栈顶元素由于我们之前入栈的都是Left节点所以每次在出栈的时候我们都要考虑Right节点是否存在因为前序/后序/中序遍历顺序的不同所以在具体的实现上有略为区别
)前序遍历
这个是最简单的
前序遍历是root>rootLeft>rootRight的顺序
因为在第一个while循环中每次进栈的都可以认为是一个root所以我们直接打印然后rootRight和rootLeft先后进栈那么出栈的时候就能确保先左后右的顺序
static void PreOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
ConsoleWriteLine(tempElement);
if (tempRight != null)
stackPush(tempRight);
temp = tempLeft;
}
//出栈当然也有入栈
while (stackCount > )
{
temp = (BinNode)stackPop();
ConsoleWriteLine(tempElement);
while (temp != null)
{
if (tempRight != null)
stackPush(tempRight);
temp = tempLeft;
}
}
}
//后序遍历比较麻烦需要记录上一个访问的节点然后在本次循环中判断当前节点的Right或Left是否为上个节点当前节点的Right为null表示没有右节点
static void PostOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
if (temp != null)
stackPush(temp);
temp = tempLeft;
}
//出栈当然也有入栈
while (stackCount > )
{
BinNode lastvisit = temp;
temp = (BinNode)stackPop();
if (tempRight == null || tempRight == lastvisit)
{
ConsoleWriteLine(tempElement);
}
else if (tempLeft == lastvisit)
{
stackPush(temp);
temp = tempRight;
stackPush(temp);
while (temp != null)
{
if (tempLeft != null)
stackPush(tempLeft);
temp = tempLeft;
}
}
}
}
//中序遍历类似于前序遍历
static void InOrder(BinNode root)
{
Stack stack = new Stack();
BinNode temp = root;
//入栈
while (temp != null)
{
if (temp != null)
stackPush(temp);
temp = tempLeft;
}
//出栈当然也有入栈
while (stackCount > )
{
temp = (BinNode)stackPop();
ConsoleWriteLine(tempElement);
if (tempRight != null)
{
temp = tempRight;
stackPush(temp);
while (temp != null)
{
if (tempLeft != null)
stackPush(tempLeft);
temp = tempLeft;
}
}
}
} 在二叉树中找出和为某一值的所有路径
算法思想这道题目的苦恼在于如果用递归只能打出一条路径来其它符合条件的路径打不出来
为此我们需要一个Stack来保存访问过的节点即在对该节点的递归前让其进栈对该节点的递归结束后再让其出栈——深度优先原则（DFS）
此外在递归中如果发现某节点（及其路径）符合条件如何从头到尾打印是比较头疼的因为DFS使用的是stack而不是queue为此我们需要一个临时栈来辅助打印
static void FindBinNode(BinNode root int sum Stack stack)
{
if (root == null)
return;
stackPush(rootElement);
//Leaf
if (rootIsLeaf())
{
if (rootElement == sum)
{
Stack tempStack = new Stack();
while (stackCount > )
{
tempStackPush(stackPop());
}
while (tempStackCount > )
{
ConsoleWriteLine(tempStackPeek());
stackPush(tempStackPop());
}
ConsoleWriteLine();
}
}
if (rootLeft != null)
FindBinNode(rootLeft sum &#; rootElement stack);
if (rootRight != null)
FindBinNode(rootRight sum &#; rootElement stack);
stackPop();
} 怎样编写一个程序把一个有序整数数组放到二叉树中？
算法思想我们该如何构造这棵二叉树呢？当然是越平衡越好如下所示
//// arr[]
//// arr[] arr[]
//// arr[] arr[] arr[]
相应编码如下
public static void InsertArrayIntoTree(int[] arr int pos ref BinNode root)
{
root = new BinNode(arr[pos] null null);
rootElement = arr[pos];
//if Left value less than arr length
if (pos * + > arrLength &#; )
{
return;
}
else
{
InsertArrayIntoTree(arr pos * + ref rootLeft);
}
//if Right value less than arr length
if (pos * + > arrLength &#; )
{
return;
}
else
{
rootRight = new BinNode(arr[pos * + ] null null);
InsertArrayIntoTree(arr pos * + ref rootRight);
}
} 判断整数序列是不是二叉搜索树的后序遍历结果
比如给你一个数组 int a[] = [ ] 则F(a) => false
算法思想在后续遍历得到的序列中最后一个元素为树的根结点从头开始扫描这个序列比根结点小的元素都应该位于序列的左半部分从第一个大于跟结点开始到跟结点前面的一个元素为止所有元素都应该大于跟结点因为这部分元素对应的是树的右子树根据这样的划分把序列划分为左右两部分我们递归地确认序列的左右两部分是不是都是二元查找树
由于不能使用动态数组所以我们每次递归都使用同一个数组arr通过start和length来模拟部分数组
public static bool VerifyArrayOfBST(int[] arr int start int length)
{
if (arr == null || arrLength == || arrLength == )
{
return false;
}
int root = arr[length + start ];
int i = start;
for (; i < length ; i++)
{
if (arr[i] >= root)
break;
}
int j = i;
for (; j < length ; 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 + );
}
return left &#;& right;
} 求二叉树的镜像
算法利用上述遍历二叉树的方法（比如说前序遍历）把访问操作修改为交换左右节点的逻辑
static void PreOrder(ref BinNode root)
{
if (root == null)
return;
//visit current node
BinNode temp = rootLeft;
rootLeft = rootRight;
rootRight = temp;
PreOrder(ref rootLeft);
PreOrder(ref rootRight);
} 算法使用循环也可以完成相同的功能
static void PreOrder(ref BinNode root)
{
if (root == null)
return;
Stack stack = new Stack();
stackPush(root);
while (stackCount > )
{
//visit current node
BinNode temp = rootLeft;
rootLeft = rootRight;
rootRight = temp;
if (rootLeft != null)
stackPush(rootLeft);
if (rootRight != null)
stackPush(rootRight);
}
} 一棵排序二叉树（即二叉搜索树BST）令 f=(最大值+最小值)/设计一个算法找出距离f值最近大于f值的结点复杂度如果是O(n)则不得分
算法思想最小最大节点分别在最左下与最右下节点O(N)
static BinNode Find(BinNode root)
{
BinNode min = FindMinNode(root);
BinNode max = FindMaxNode(root);
double find = (double)(minElement + maxElement) / ;
return FindNode(root find);
} static BinNode FindMinNode(BinNode root)
{
BinNode min = root;
while (minLeft != null)
{
min = minLeft;
}
return min;
}
static BinNode FindMaxNode(BinNode root)
{
BinNode max = root;
while (maxRight != null)
{
max = maxRight;
}
return max;
}
递归寻找BST的节点O(logN)
static BinNode FindNode(BinNode root double mid)
{
//如果小于相等则从右边找一个最小值
if (rootElement <= mid)
{
if (rootRight == null)
return root;
BinNode find = FindNode(rootRight mid);
//不一定找得到
return findElement < mid
root : find;
}
//如果大于则找到Left
else //tempElement > find
{
if (rootLeft == null)
return root;
BinNode find = FindNode(rootLeft mid);
//不一定找得到
return findElement < mid
root : find;
}
} 把二叉搜索树转变成排序的双向链表如
////
////
////
////
转变为Link=======
算法思想这个就是中序遍历啦因为BST的中序遍历就是一个从小到大的访问顺序局部修改中序遍历算法于是有如下代码
static void ConvertNodeToLink(BinNode root ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (tempLeft != null)
ConvertNodeToLink(tempLeft ref link);
//visit current node
linkNext = new DoubleLink(link null root);
link = linkNext;
if (tempRight != null)
ConvertNodeToLink(tempRight ref link);
} 但是我们发现这样得到的Link是指向双链表最后一个元素而我们想要得到的是表头为此我们不得不额外进行while循环将指针向前移动到表头
static DoubleLink ReverseDoubleLink(BinNode root ref DoubleLink link)
{
ConvertNodeToLink(root ref link);
DoubleLink temp = link;
while (tempPrev != null)
{
temp = tempPrev;
}
return temp;
}
这么写有点蠢为什么不直接在递归中就把顺序反转呢？于是有算法 算法观察算法的递归方法访问顺序是Left > Root –> Right所以我们要把访问顺序修改为Right > Root –> Left
此外算法的节点访问逻辑是连接当前节点和新节点同时指针link向前走即========link
代码如下所示
linkNext = new DoubleLink(link null root);
link = linkNext;
那么即使我们颠倒了访问顺序新的Link也只是变为========link
为此我们修改上面的节点访问逻辑——将Next和Prev属性交换
linkPrev = new DoubleLink(null link root);
link = linkPrev;
这样新的Link就变成这样的顺序了link========
算法代码如下所示
static void ConvertNodeToLink(BinNode root ref DoubleLink link)
{
if (root == null)
return;
BinNode temp = root;
if (tempRight != null)
ConvertNodeToLink(tempRight ref link);
//visit current node
linkPrev = new DoubleLink(null link root);
link = linkPrev;
if (tempLeft != null)
ConvertNodeToLink(tempLeft ref link);
} 以下算法属于二叉树的基本概念未列出
Huffman Tree的生成编码和反编码
BST的实现
Heap的实现优先队列 非平衡二叉树如何变成平衡二叉树？ 玩二叉树基本都要用到递归算法
唉对于递归函数我一直纠结到底要不要返回值？到底先干正事还是先递归？到底要不要破坏原来的数据结构？到底要不要额外做个stack/queue/link/array来转存还是说完全在递归里面实现？到底终结条件要写成什么样子？ ref在递归里面貌似用的很多哦 |
