public class BinaryTree
{
Node root;
public void addNode(int key, String name)
{
// Create a new Node and initialize it
Node newNode = new Node(key, name);
// If there is no root this becomes root
if (root == null)
{
root = newNode;
}
else
{
// Set root as the Node we will start
// with as we traverse the tree
Node focusNode = root;
// Future parent for our new Node
Node parent;
while (true)
{
// root is the top parent so we start
// there
parent = focusNode;
// Check if the new node should go on
// the left side of the parent node
if (key < focusNode.key)
{
// Switch focus to the left child
focusNode = focusNode.leftChild;
// If the left child has no children
if (focusNode == null)
{
// then place the new node on the left of it
parent.leftChild = newNode;
return; // All Done
}
}
else
{ // If we get here put the node on the right
focusNode = focusNode.rightChild;
// If the right child has no children
if (focusNode == null)
{
// then place the new node on the right of it
parent.rightChild = newNode;
return; // All Done
}
}
}
}
}
// All nodes are visited in ascending order
// Recursion is used to go to one node and
// then go to its child nodes and so forth
public void inOrderTraverseTree(Node focusNode)
{
if (focusNode != null)
{
// Traverse the left node
inOrderTraverseTree(focusNode.leftChild);
// Visit the currently focused on node
System.out.println(focusNode);
// Traverse the right node
inOrderTraverseTree(focusNode.rightChild);
}
}
public void preorderTraverseTree(Node focusNode)
{
if (focusNode != null)
{
System.out.println(focusNode);
preorderTraverseTree(focusNode.leftChild);
preorderTraverseTree(focusNode.rightChild);
}
}
public void postOrderTraverseTree(Node focusNode)
{
if (focusNode != null)
{
postOrderTraverseTree(focusNode.leftChild);
postOrderTraverseTree(focusNode.rightChild);
System.out.println(focusNode);
}
}
public Node findNode(int key)
{
// Start at the top of the tree
Node focusNode = root;
// While we haven't found the Node
// keep looking
while (focusNode.key != key)
{
// If we should search to the left
if (key < focusNode.key)
{
// Shift the focus Node to the left child
focusNode = focusNode.leftChild;
}
else
{
// Shift the focus Node to the right child
focusNode = focusNode.rightChild;
}
// The node wasn't found
if (focusNode == null)
return null;
}
return focusNode;
}
public static void main(String[] args)
{
BinaryTree theTree = new BinaryTree();
theTree.addNode(50, "Boss");
theTree.addNode(25, "Vice President");
theTree.addNode(15, "Office Manager");
theTree.addNode(30, "Secretary");
theTree.addNode(75, "Sales Manager");
theTree.addNode(85, "Salesman 1");
// Different ways to traverse binary trees
theTree.inOrderTraverseTree(theTree.root);
System.out.println();
theTree.preorderTraverseTree(theTree.root);
System.out.println();
theTree.postOrderTraverseTree(theTree.root);
// Find the node with key 75
System.out.println("\nNode with the key 75");
System.out.println(theTree.findNode(75));
}
}
class Node
{
int key;
String name;
Node leftChild;
Node rightChild;
Node(int key, String name)
{
this.key = key;
this.name = name;
}
@Override
public String toString()
{
return name + " has the key " + key;
/*
* return name + " has the key " + key + "\nLeft Child: " + leftChild + "\nRight Child: " +
* rightChild + "\n";
*/
}
}
分享到:
相关推荐
Construct Binary Tree from Preorder and Inorder Traversal 根据先序,中序建立二叉树
binary tree 的C语言实现算法,需要在linux环境下编译
This is a binary tree search implementation.
BinaryTree-源码.rar
懂的人自然懂:) 用C#写的binarytree
心希盼 C++ STL 二叉树 详细请看“心希盼 binaryTree.doc”
BinaryTree-BinaryTree
BinaryTree: 用于学习二叉树的Python库
二叉树的实现,各种方法,构造函数,析构函数,前序遍历,中序遍历,后续遍历,层次序遍历
BinaryTreeSort的java实现,简单的二叉树排序
2.binaryTree树 标准的二叉树。 实现了各种算法,增删查改等等
C++实现 操作函数包括先序、中序、后序遍历,求深度,深度、广度遍历 构建二叉树
二叉树前序遍历,leetcode
有序二叉树创建 有序二叉树查找 二叉树遍历 有序二叉树删除 类模版实现的有序二叉树
二叉树的实现代码,我的博客“Java——二叉树的基础实现”的代码。 https://blog.csdn.net/J_fla/article/details/103236673
constructing a binary tree
BinaryTree create and travel
二叉树官方源码,可以通过编译,直接参考使用。不是自己写的,官方资源
BinaryTree.opt
BinaryTree.hpp