(C# Binary Tree) 基本概念和算法

A binary tree is defined as a tree where each node can have no more than two children.

Building a Binary Search Tree:

首先创建一个节点Class

    public class BtNode
{
public int Data { get; set; } public BtNode Left { get; set; } public BtNode Right { get; set; } public void DisplayNode()
{
Console.Write("Data: {0}, ", this.Data);
}
}

然后创建BST Class 提供Insert 方法:

    public class BinarySearchTree
{
private BtNode root = null; public BtNode Root
{
get
{
return this.root;
}
set
{
this.root = value;
}
} public void Insert(int data)
{
BtNode newNode = new BtNode();
newNode.Data = data;
if (this.root == null)
{
this.root = newNode;
}
else
{
// Add to children nodes.
BtNode current = this.root;
BtNode parent = new BtNode(); while(true)
{
parent = current;
if (data < current.Data)
{
current = current.Left;
if (current == null )
{
parent.Left = newNode;
break;
} }
else
{
current = current.Right;
if (current == null)
{
parent.Right = newNode;
break;
}
}
}
}
}
}

Level traverse the binary tree.

思路就是用 Queue (FIFO),从左到右扫描节点,一个节点出队列,就将其节点的左右孩子入队。

        public static void PrintLevelTracversal(BtNode root)
{
if (root == null)
{
throw new Exception("Binary true is null!");
} Queue<BtNode> queueBtNode = new Queue<BtNode>();
queueBtNode.Enqueue(root);
BtNode currentNode = root; // Dequeue the node from left to right and put its left/right children into queue.
while(currentNode != null)
{
currentNode = queueBtNode.Dequeue();
currentNode.DisplayNode(); if (currentNode.Left != null)
{
queueBtNode.Enqueue(currentNode.Left);
} if (currentNode.Right != null)
{
queueBtNode.Enqueue(currentNode.Right);
}
}
}

Level traverse and print nodes as Zigzag.

思路: 用2个Stuck, 一个保存Current Level, 另一个保存Next Level.

当一层 扫完后,将下一层copy到当前层。

       // Non-Recursive method.  Use two stacks.
public static void PrintZigzagLevelTraversal(BtNode root)
{
if (root == null)
{
throw new Exception("Binary tree is null!");
} Stack<BtNode> currentLevelStack = new Stack<BtNode>();
Stack<BtNode> nextLevelStack = new Stack<BtNode>();
BtNode currentBtNode = new BtNode(); int level = ;
currentLevelStack.Push(root); while(currentLevelStack.Count > )
{
// Display current node data.
currentBtNode = currentLevelStack.Pop();
currentBtNode.DisplayNode(); if (level % == ) // even level
{
if (currentBtNode.Left != null)
{
nextLevelStack.Push(currentBtNode.Left);
}
if (currentBtNode.Right != null)
{
nextLevelStack.Push(currentBtNode.Right);
}
}
else
{
if (currentBtNode.Right != null)
{
nextLevelStack.Push(currentBtNode.Right);
}
if (currentBtNode.Left != null)
{
nextLevelStack.Push(currentBtNode.Left);
}
} // Move data from next level to current level stack.
if (nextLevelStack.Count > && currentLevelStack.Count == )
{
BtNode[] nodes = new BtNode[nextLevelStack.Count];
nextLevelStack.CopyTo(nodes, );
for (int i = nodes.Length - ; i >= ; i--)
{
currentLevelStack.Push(nodes[i]);
}
nextLevelStack.Clear();
level++;
}
}
}
 
上一篇:013 将数据离散化


下一篇:【HIHOCODER 1576】 子树中的最小权值(线段树维护DFS序)