关于二叉树，概念神马的不提，我们主要来谈一下二叉树的创建，遍历，插入，删除等等一系列的操作。
一、创建与遍历
创建要根据用户输入的字符串来统计每个字母出现的次数,从而作为每个字母的权值，来构建二叉树。
在进入主函数前先定义了全局变量
import java.util.LinkedList;
import java.util.List;
import java.util.Stack;
public class newa {
private int[] array;
private static List<Node> nodeList=null;
主函数如下
public static void main(String[] args) {
// 实例化一个接受命令行输入信息的对象
java.util.Scanner sc = new java.util.Scanner(System.in);
System.out.println("请输入要统计的字符串：");
// 获取输入的一行字符串
String temp = sc.nextLine();
newa tree=new newa();
//调用用来计算权值的方法
tree.wayOne(temp);
tree.createBinTree();
//递归与非递归实现前序遍历
preOrder(nodeList.get(0));
System.out.println();
preOrderStack(nodeList.get(0));
System.out.println();
//递归与非递归实现中序遍历
inOrder(nodeList.get(0));
System.out.println();
inOrderStack(nodeList.get(0));
System.out.println();
//递归与非递归实现后序遍历
postOrder(nodeList.get(0));
System.out.println();
postOrderStack(nodeList.get(0));
System.out.println();
}
接着就是一个又一个的方法
1、用于统计权值的方法，这是我们第一节课的练习，小伙伴们你们还记得吗？这就是每次统计后把相同的字母都删除的那个方法1，唯一不同在于要返回array的值，这样我们就得到了所有的权值
public int[] wayOne(String temp) {
// 定义一个存储统计次数的数组
// int[] array = new int[256];
// 循环遍历字符串
for (int i = 0; i < temp.length(); i++) {
// 获取指定索引位置的字符
char c = temp.charAt(i);
// 将字符转换为对应的ascii
int ascii = c;
// 将对应的ascii位置的数组元素加1
array[ascii]++;
}
// 输出
for (int i = 0; i < array.length; i++) {
// 如果统计个数部位0则输出
if (array[i] != 0) {
char c = (char) i;
System.out.println("字符" + c + "出现的次数是" + array[i]);
}
}
return array;
}
2.创建二叉树的方法
//利用既定数组创建二叉树
public void createBinTree(){
//实例化一个节点类的队列，并将数组中的数字添加进去
nodeList=new LinkedList<Node>();
for(int i=0,len=array.length;i<len;i++){
nodeList.add(new Node(array[i]));
}
int len=array.length;
int lastRootIndex=(len>>1)-1;
for(int i=lastRootIndex;i>=0;i--){
Node root=nodeList.get(i);
int leftIndex=i*2+1;
Node leftNode=nodeList.get(leftIndex);
root.setLeft(leftNode);
//最后的那个根节点一定是有左子树的，但右子树不一定
int rightIndex=leftIndex+1;
if(rightIndex<=len-1){
Node rightNode=nodeList.get(rightIndex);
root.setRight(rightNode);
}
}
}
3.使用非递归的三种遍历
//非递归先序遍历
public static void preOrderStack(Node root){
Stack<Node> stack=new Stack<Node>();
Node p=root;
if(p!=null){
stack.push(p);
while(!stack.isEmpty()){
p=stack.pop();
visit(p);
if(p.getRight()!=null)stack.push(p.getRight());
if(p.getLeft()!=null)stack.push(p.getLeft());
}
}
}
//非递归中序遍历
public static void inOrderStack(Node p){
Stack<Node> stack=new Stack<Node>();
while(p!=null||!stack.isEmpty()){
//push all LeftChild,when p has no LeftChild,that means it's root,it should be visited
while(p!=null){
stack.push(p);
p=p.getLeft();
}
if(!stack.isEmpty()){
p=stack.pop();
visit(p);
p=p.getRight();
}
}
}
//非递归后序遍历
public static void postOrderStack(Node p){
Stack<Node> stack=new Stack<Node>();
Node q=p;//q是最后一个被访问的节点
while(p!=null){
while(p.getLeft()!=null){
stack.push(p);
p=p.getLeft();
}
while(p!=null&&(p.getRight()==null||p.getRight()==q)){
visit(p);
q=p;
if(stack.isEmpty())return;
p=stack.pop();
}
stack.push(p);
p=p.getRight();
}
}
看到这里，小伙伴们又要问了，stack是个神马？ stack.push(p); 又是神马？这到底是神马跟神马？？好是环燥啊！这些东西非我原创，只是百度来跟大家分享一下下，查找了API发现：
类 Stack<E>，是java.util下的一个类，API如是说道，
public class Stack<E>extends Vector<E>
Stack 类表示后进先出（LIFO）的对象堆栈。它通过五个操作对类 Vector 进行了扩展 ，允许将向量视为堆栈。它提供了通常的 push 和 pop 操作，以及取堆栈顶点的 peek 方法、测试堆栈是否为空的 empty 方法、在堆栈中查找项并确定到堆栈顶距离的 search 方法。
首次创建堆栈时，它不包含项。
又出现了Vector<E>...我禁不住也烦躁了，有兴趣的小伙伴自己去查找吧，现在来看看Stack中的各种方法
boolean |
empty() 测试堆栈是否为空。 |
E |
peek() 查看堆栈顶部的对象，但不从堆栈中移除它。 |
E |
pop() 移除堆栈顶部的对象，并作为此函数的值返回该对象。 |
E |
push(E item) 把项压入堆栈顶部。 |
int |
search(Object o) 返回对象在堆栈中的位置，以 1 为基数。 |
看了这些以后，还是有种雾里开花水中望月的感觉，也许等我们以后接触了这个类之后就能掌握他了吧~
3、递归实现的三种遍历
//递归前序遍历
public static void preOrder(Node root){
if(root==null){return;}
System.out.print(root.getData()+" ");
preOrder(root.getLeft());
preOrder(root.getRight());
}
//递归中序遍历
public static void inOrder(Node root){
if(root==null){return;}
inOrder(root.getLeft());
System.out.print(root.getData()+" ");
inOrder(root.getRight());
}
//递归后序遍历
public static void postOrder(Node root){
if(root==null){return;}
postOrder(root.getLeft());
postOrder(root.getRight());
System.out.print(root.getData()+" ");
}
看了这三种递归实现的遍历，有对比上面的非递归算法，应了我上一篇总结的话，递归实在是灰常灰常有用的东东！！！
4、最后是节点类
//节点类
private static class Node{
private Node left;
private Node right;
private int data;
Node(int iData){
data=iData;
left=null;
right=null;
}
public void setLeft(Node leftNode){
this.left=leftNode;
}
public void setRight(Node rightNode){
this.right=rightNode;
}
public Node getLeft(){
return left;
}
public Node getRight(){
return right;
}
public int getData(){
return data;
}
}
}
5.关于删除
删除实在是个很深奥的问题，现在仅止于看懂。。。自己的还没有编出来~~先把汉化后大神的代码贴上来吧
// ---------------------------根据值删除----------------------------------
public boolean delete(int key) // 根据值删除
{ // (assumes non-empty list)
Node current = root;
Node parent = root;
boolean isLeftChild = true;
while(current.iData != key) // 寻找节点，不相等就一直找
{
parent = current;
if(key < current.iData) // 若值小于当前结点所存的值，向左转
{
isLeftChild = true;//标记自己是父节点的左子结点还是右子节点
current = current.leftChild;
}
else // or go right?
{
isLeftChild = false;
current = current.rightChild;
}
if(current == null) // 到达左边线的最下端
return false; // 没找到返回false
}
//退出了while意味着找到了对应节点
// 若没有子节点，则直接删除
if(current.leftChild==null &&
current.rightChild==null)
{
if(current == root) //半段是否为根节点
root = null; // 清空树
else if(isLeftChild)
parent.leftChild = null; // disconnect
else // from parent
parent.rightChild = null;
}
// 若没有右边的子节点，则直接把左边的子节点赋给父节点的左节点或者右节点
else if(current.rightChild==null)
if(current == root)
root = current.leftChild;
else if(isLeftChild)
parent.leftChild = current.leftChild;
else
parent.rightChild = current.leftChild;
// 若没有左边的子节点，则直接把右边的子节点赋给父节点的左节点或者右节点
else if(current.leftChild==null)
if(current == root)
root = current.rightChild;
else if(isLeftChild)
parent.leftChild = current.rightChild;
else
parent.rightChild = current.rightChild;
else // 有两个子节点则：
{
// get successor of node to delete (current)
Node successor = getSuccessor(current);
// connect parent of current to successor instead
if(current == root)
root = successor;
else if(isLeftChild)
parent.leftChild = successor;//用于调整位置的方法
else
parent.rightChild = successor;
// connect successor to current's left child
successor.leftChild = current.leftChild;
} // end else two children
// (successor cannot have a left child)
return true; // success
} // end delete()
// -------------------------------------------------------------
// 返回被删除节点的子节点中的最大值
// 从右边开始
private Node getSuccessor(Node delNode)
{
Node successorParent = delNode;
Node successor = delNode;
Node current = delNode.rightChild; // go to right child
while(current != null) // until no more
{ // left children,
successorParent = successor;
successor = current;
current = current.leftChild; // go to left child
}
// if successor not
if(successor != delNode.rightChild) // right child,
{ // make connections
successorParent.leftChild = successor.rightChild;
successor.rightChild = delNode.rightChild;
}
return successor;
}
大神用了两个方法来实现，一个是删除掉节点，一个是在他的子节点中找到最大的那一个，用来替换他的位置，我还知道了这个代码来自于清华的数据结构课件~~清华计算机学院果然强大~拜倒个~
目前二叉树就是现在这个样子，删除等我完善~~
上面那个遍历跟创建看上去如此流畅完美的代码，但却报错了！！传说中的空指针异常！！就在
for(int i=0,len=array.length;i<len;i++)
tree.createBinTree();
这两行代码上！！修改中。。。
相关推荐
### 知识点：复制一棵二叉树 #### 一、引言 在计算机科学领域，数据结构中的二叉树是一种常见的非线性数据结构，它由节点组成，每个节点最多有两个子节点，分别称为左子节点和右子节点。复制二叉树是指创建一个与原...
在IT领域，特别是数据结构和算法的学习中，二叉树是一种基本且重要的数据结构。它由节点（或称为顶点）组成，每个节点最多有两个子节点，通常分别称为左子节点和右子节点。二叉树的应用广泛，包括搜索、排序、表达式...
判断一棵二叉树是否为完全二叉树可以通过广度优先搜索来实现。 ```cpp bool IsCompleteBinaryTree(BiTree bt) { bool flag = false; // 标记是否已经遇到过空节点 SqQueue Q; InitQueue(Q); EnQueue(Q, bt); ...
1) 按先序序列建立一棵二叉树时，先构造根结点，再构造根的左子树，然后构造右子树；每棵子树又都是二叉树，所以构造一棵子树的过程与构造整棵二叉树的过程完全相同（采用递归形式直到叶子结点为止）。 2) 先序序列...
设一棵二叉树以二叉链表表示，试编写有关二叉树的递归算法
二叉树算法源码~~~C++实现的~~数据结构运用，充分应用了二叉树的模板实现的~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 二叉树算法源码~~~C++实现的~~~数据结构运用~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~...
采用先序法建立一棵二叉树，设计求该二叉树的深度，二叉树的数据域类型为字符型， 扩展二叉树的叶子结点用‘#’表示，要求可以求多棵二叉树的深度，当二叉树的深度为0时程序结束。
给定一个二叉树的前序和中序遍历序列，可以唯一地重建这棵树，这是因为这两种遍历方式提供了足够的信息来确定树的结构。 前序遍历的顺序是：根节点 -> 左子树 -> 右子树。中序遍历的顺序是：左子树 -> 根节点 -> 右...
### 唯一地确定一棵二叉树：前序遍历与中序遍历...综上所述，通过前序遍历和中序遍历序列，我们不仅能够唯一确定一棵二叉树的结构，还能验证构建的准确性，这一过程充分展示了二叉树遍历的实用性和算法设计的精妙之处。
1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树...
一个二叉树由零个或多个节点组成，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。这种结构使得二叉树能够非常有效地存储具有层级关系的数据。 #### 二、二叉树的节点定义 在给定的代码片段中，我们...
由给定的前序和中序或者给定的中序和后序确定一棵二叉树的算法
创建一棵二叉树，分别实现先序、中序和后序遍历一棵二叉树，计算二叉树结点个数等操作。 1.建立二叉树方法1 2.建立二叉树方法2 3.先序递归遍历二叉树 4.中序递归遍历二叉树 5.后序递归遍历二叉树 6.层次遍历...
1.二叉树的基本操作实现【问题描述】建立一棵二叉树，用递归方法实现二叉树的如下基本操作：（1）按先序序列构造一棵二叉链表表示的二叉树T；（2）对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出...
在二叉树的算法设计中，复制一棵二叉树是一个常见的任务，这有助于在不改变原始树的情况下进行操作。本文将详细讲解如何编写一个非递归算法来复制一棵二叉树，以及如何根据前序和中序序列重建二叉树。 首先，我们来...
在计算机科学领域，二叉树是一种基础的数据结构，它由结点构成，每个结点最多有两个子节点，分别称为左子节点和右子节点。在众多的二叉树操作中，根据后序遍历序列（也称为后序序列）来构造二叉树是一项常见的任务。...
二叉树采用二叉链表结构表示。设计并实现如下算法：输入某棵二叉树的广义表形式，建立该二叉树，并按层次遍历该二叉树