using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace ConsoleApplication2
{
class TreeNode
{
public int Index { get; set; }
public TreeNode Left { get; set; }
public TreeNode Right { get; set; }
public void InorderTraverse()
{
if (this.Left != null)
this.Left.InorderTraverse();
Console.WriteLine("tree node: {0}", this.Index);
if (this.Right != null)
this.Right.InorderTraverse();
}
}
class ListNode
{
public int Index { get; set; }
public ListNode Prev { get; set; }
public ListNode Next { get; set; }
public static ListNode CreateNode(int index)
{
var ret = new ListNode();
ret.Index = index;
ret.Prev = ret;
ret.Next = ret;
return ret;
}
public void Append(ListNode list)
{
Debug.Assert(list != null);
Debug.Assert(list.Prev != null);
Debug.Assert(list.Next != null);
Debug.Assert(this.Prev != null);
Debug.Assert(this.Next != null);
var listLastNode = list.Prev;
var thisLastNode = this.Prev;
// link list last node & thislist
listLastNode.Next = this;
this.Prev = listLastNode;
// link thislist last node & list
thisLastNode.Next = list;
list.Prev = thisLastNode;
}
public void TraverseForward()
{
var node = this;
do
{
Console.WriteLine("list node: {0}", node.Index);
node = node.Next;
}
while (node != this);
}
public void TraverseBackward()
{
var node = this.Prev;
do
{
Console.WriteLine("list node: {0}", node.Index);
node = node.Prev;
}
while (node != this.Prev);
}
}
class Program
{
static TreeNode BuildTree()
{
return new TreeNode()
{
Index = 4,
Left = new TreeNode()
{
Index = 2,
Left = new TreeNode()
{
Index = 1
},
Right = new TreeNode()
{
Index = 3
}
},
Right = new TreeNode()
{
Index = 6,
Left = new TreeNode()
{
Index = 5
},
Right = new TreeNode()
{
Index = 7
}
},
};
}
static ListNode ConvertToList(TreeNode root)
{
// convert to list with inorder traversal
if (root == null)
return null;
ListNode result;
var thisNode = ListNode.CreateNode(root.Index);
if (root.Left != null)
{
result = ConvertToList(root.Left);
result.Append(thisNode);
}
else
result = thisNode;
if (root.Right != null)
{
var rightList = ConvertToList(root.Right);
result.Append(rightList);
}
return result;
}
static void Main(string[] args)
{
var root = BuildTree();
Console.WriteLine("Tree inoder traversal::");
root.InorderTraverse();
var list = ConvertToList(root);
Console.WriteLine("List forward traversal::");
list.TraverseForward();
Console.WriteLine("List backward traversal::");
list.TraverseBackward();
}
}
}