前一阵homebrew作者面试谷歌被拒，原因之一是这位老兄无法反转出二叉树。
既然众公司面试都爱用这货面试，咱也来做一下。
先定义二叉树类
public class BinaryTreeNode<T> { public string Name { get; set; } public T Data { get; set; } public BinaryTreeNode<T> Left { get; set; } public BinaryTreeNode<T> Right { get; set; } private bool _isLeaf; public bool IsLeaf { get { _isLeaf = (Left == null && Right == null); return _isLeaf; } } public BinaryTreeNode(string name, T data = default(T)) { Name = name; Data = data; } public BinaryTreeNode<T> CreateAndJionLeft(string name, T data = default(T)) { return Left = new BinaryTreeNode<T>(name, data); } public BinaryTreeNode<T> CreateAndJionRight(string name, T data = default(T)) { return Right = new BinaryTreeNode<T>(name, data); } }
Name和Data是二叉树内部元素，根据需求调整即可，CreateAndJionLeft表示将左边子节点加入当前节点，也可在外部调用端实例化子节点。
接下来是二叉树常用的几种遍历方式：前序遍历，中序遍历，后序遍历，逐层遍历
/// <summary> /// 前序遍历 /// </summary> public void PreOrderTraversal() { if (this != null) { Trace.WriteLine(Name); } if (Left != null) { Left.PreOrderTraversal(); } if (Right != null) { Right.PreOrderTraversal(); } } /// <summary> /// 前序遍历 非递归 /// </summary> public void PreOrderTraversalEx() { Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>(); BinaryTreeNode<T> node = this; while (node != null || stack.Count != 0) { while (node != null) { Trace.WriteLine(node.Name); stack.Push(node); node = node.Left; } if (stack.Count != 0) { node = stack.Pop(); node = node.Right; } } } /// <summary> /// 中序遍历 /// </summary> public void InOrderTraversal() { if (Left != null) { Left.InOrderTraversal(); } if (this != null) { Trace.WriteLine(Name); } if (Right != null) { Right.InOrderTraversal(); } } /// <summary> /// 中序遍历 非递归 /// </summary> public void InOrderTraversalEx() { Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>(); BinaryTreeNode<T> node = this; while (node != null || stack.Count != 0) { while (node != null) { stack.Push(node); node = node.Left; } if (stack.Count != 0) { node = stack.Peek(); stack.Pop(); Trace.WriteLine(node.Name); node = node.Right; } } } /// <summary> /// 后序遍历 /// </summary> public void PostOrderTraversal() { if (Left != null) { Left.PostOrderTraversal(); } if (Right != null) { Right.PostOrderTraversal(); } if (this != null) { Trace.WriteLine(Name); } } /// <summary> /// 后序遍历 非递归 /// </summary> public void PostOrderTraversalEx() { Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>(); BinaryTreeNode<T> node = this; BinaryTreeNode<T> lastNode = null; stack.Push(node); while (stack.Count!=0) { node = stack.Peek(); if ((node.Left == null && node.Right == null) || (lastNode != null && (lastNode == node.Left || lastNode == node.Right))) { //如果当前结点没有子结点或者子节点都已被访问过就输出 因为后序遍历是先子节点再根节点 Trace.WriteLine(node.Name); stack.Pop(); lastNode = node;//设定本次访问的节点为上一次访问的节点 } else { if (node.Right != null) stack.Push(node.Right); if (node.Left != null) stack.Push(node.Left); } } } /// <summary> /// 逐层遍历 /// </summary> public void Traversal() { Stack<BinaryTreeNode<T>> stack = new Stack<BinaryTreeNode<T>>(); stack.Push(this); while (stack.Count > 0) { BinaryTreeNode<T> temp = stack.Peek(); Trace.WriteLine(temp.Name); stack.Pop(); if (temp.Left != null) { stack.Push(temp.Left); } if (temp.Right != null) { stack.Push(temp.Right); } } }
递归实现反转二叉树
/// <summary> /// 反转二叉树(递归) /// </summary> public BinaryTreeNode<T> ReverseWithRecursive() { if (this == null) { return null; } if (!(Left == null && Right == null)) { BinaryTreeNode<T> temp = Right;//左右节点反转 Right = Left; Left = temp; if (Left != null) Left = Left.ReverseWithRecursive();//递归反转左子节点 if (Right != null) Right = Right.ReverseWithRecursive();//递归反转右子节点 } return this; }
非递归方式实现反转二叉树
/// <summary> /// 反转二叉树(非递归) /// </summary> /// <returns></returns> public BinaryTreeNode<T> Reverse() { if (this == null) { return null; } Queue<BinaryTreeNode<T>> nodeQueue = new Queue<BinaryTreeNode<T>>(); nodeQueue.Enqueue(this); while (nodeQueue.Count > 0) { BinaryTreeNode<T> node = nodeQueue.Peek(); nodeQueue.Dequeue(); BinaryTreeNode<T> tempNode = node.Right;//左右节点反转 node.Right = node.Left; node.Left = tempNode; if (node.Left != null) { nodeQueue.Enqueue(node.Left); } if (node.Right != null) { nodeQueue.Enqueue(node.Right); } } return this; }
定义一个队列来临时存储即将反转的节点。获取队列中存储的节点，获取到一个节点后队列中的此节点已无用将其删除，然后把获取到的节点的左右子节点反转，将反转后的左右子节点都放入队列用于下一次循环。重复执行直到反转完所有树节点。
换成栈存储
/// <summary> /// 反转二叉树(非递归) 栈 /// </summary> /// <returns></returns> public BinaryTreeNode<T> ReverseEx() { if (this == null) { return null; } Stack<BinaryTreeNode<T>> nodeStack = new Stack<BinaryTreeNode<T>>(); nodeStack.Push(this); while (nodeStack.Count > 0) { BinaryTreeNode<T> node = nodeStack.Peek(); nodeStack.Pop(); BinaryTreeNode<T> tempNode = node.Right;//左右节点反转 node.Right = node.Left; node.Left = tempNode; if (node.Left != null) { nodeStack.Push(node.Left); } if (node.Right != null) { nodeStack.Push(node.Right); } } return this; }
客户端调用
//创建二叉树 BinaryTreeNode<int> tree = new BinaryTreeNode<int>("0");//rootNode BinaryTreeNode<int> n01 = tree.CreateAndJionLeft("01"); BinaryTreeNode<int> n02 = tree.CreateAndJionRight("02"); BinaryTreeNode<int> n011 = n01.CreateAndJionLeft("011"); BinaryTreeNode<int> n012 = n01.CreateAndJionRight("012"); BinaryTreeNode<int> n021 = n02.CreateAndJionLeft("021"); BinaryTreeNode<int> n0211 = n021.CreateAndJionLeft("0211"); BinaryTreeNode<int> n0212 = n021.CreateAndJionRight("0212"); //遍历输出 tree.Traversal(); //反转二叉树并遍历输出 BinaryTreeNode<int> treeReverse = tree.Reverse(); treeReverse.Traversal();
反转前
反转后
转载请注明地址：http://www.cnblogs.com/wintersoft/p/4676124.html