運作結果
代碼
using System;
namespace ThreadedBinaryTree
{
class Program
{
static void Main(string[] args)
{
ThreadedBinaryTreeC threadedBinaryTreeC = new ThreadedBinaryTreeC();
string[] strarry = new string[] { "A", "B", "C", "D", "E", "F" };
ThreadedBinaryTreeC.Node root = threadedBinaryTreeC.CreateBinaryTree(strarry, 0);
threadedBinaryTreeC.inThreadOrder(root);
threadedBinaryTreeC.inThreadList(root);
}
}
class ThreadedBinaryTreeC
{
Node preNode = null;
public class Node
{
public string data;
public Node left;
public Node right;
public bool leftType;
public bool rightType;
public Node(string data)
{
this.data = data;
}
}
public Node CreateBinaryTree(string[] array, int index)
{
Node node = null;
if (index < array.Length)
{
node = new Node(array[index]);
node.left = CreateBinaryTree(array, index * 2 + 1);
node.right = CreateBinaryTree(array, index * 2 + 2);
}
return node;
}
public void inThreadOrder(Node node)
{
while (node == null)
{
return;
}
inThreadOrder(node.left);
if (node.left == null)
{
node.left = preNode;
node.leftType = true;
}
if (preNode != null && preNode.right == null)
{
preNode.right = node;
preNode.rightType = true;
}
preNode = node;
inThreadOrder(node.right);
}
public void inThreadList(Node node)
{
while (node != null && !node.leftType)
{
node = node.left;
}
while (node != null)
{
Console.WriteLine(node.data);
if (node.rightType)
{
node = node.right;
}
else
{
node = node.right;
while (node != null && !node.leftType)
{
node = node.left;
}
}
}
}
}
}
參考
線索二叉樹原理及前序、中序線索化(Java版)