java树状结构之二叉树

时间:2022-02-02 10:57:11

参考:http://blog.csdn.net/zhangerqing/article/details/8822476

前面已经提到过树和二叉树的相关概念内容,下面主要来介绍下关于二叉树的创建,遍历,查找等相关内容。在此之间先说一个概念,广义表

一、广义表

广义表是一种非线性的数据结构,广义表是n个数据元素d1,d2,d3,…,dn的有限序列,但线性表不同的是,广义表中的di 则既可以是单个元素,还可以是一个广义表,通

常记作:GL=(d1,d2,d3,…,dn)。GL是广义表的名字,通常广义表的名字用大写字母表示。n是广义表的长度。若其中di是一个广义表,则称di是广义表GL的子表。在

广义表GL中,d1是广义表GL的表头,而广义表GL其余部分组成的表(d2,d3,…,dn)称为广义表的表尾。由此可见广义表的定义是递归定义的。

二、创建二叉树

采用广义表的方式创建二叉树。创建的二叉树结构如下:
java树状结构之二叉树

1 定义Node节点

public class Node {

	private char data;
private Node lchild;
private Node rchild; public Node(){ }
public char getData() {
return data;
} public void setData(char data) {
this.data = data;
} public Node getRchild() {
return rchild;
} public void setRchild(Node rchild) {
this.rchild = rchild;
} public Node getLchild() {
return lchild;
} public void setLchild(Node lchild) {
this.lchild = lchild;
} public Node(char ch, Node rchild, Node lchild) {
this.data = ch;
this.rchild = rchild;
this.lchild = lchild;
} public String toString() {
return "" + getData();
}
}

2. 二叉树创建类

Node createTree(String express, char split){
String[] array = StringUtils.split(express, split);
int length = array.length-1;
int capicity = (1<<(length-1))-1;
Node[] nodes = new Node[capicity];
Node head =null;
Node p = null;
int level = -1;
int childType = 0;
int index =0;
char data;
char[] charArray = express.toCharArray();
while(index < charArray.length-1){
data = charArray[index];
switch(data){
case '(':
level++;
childType = 1;
nodes[level]=p;
break;
case ',':
childType = 2;
break;
case ')':
level--;
break;
default:
p = new Node(data, null, null);
if(head == null){
head = p;
break;
}else{
switch(childType){
case 1: nodes[level].setLchild(p);break;
case 2: nodes[level].setRchild(p);break;
}
}
}
data = charArray[++index];
}
return head;
}

三、二叉树的遍历

1. 先序遍历

此种遍历模式是先读取父节点,然后再读取左右节点。

1.1 递归先序遍历

        /**
* 递归先序遍历
* @param node
*/
public void preTraversal(Node node){
if(null == node){
return;
}else{
System.out.print(node.getData()+" ");
preTraversal(node.getLchild());
preTraversal(node.getRchild());
}
}

1.2 非递归先序遍历

        /**
* 非递归先序遍历
* @param node
*/
public void preTraversalNoRecursive(Node node){
if(null == node){
return;
}
Node p = null;
int level=0;
Node[] stack = new Node[1024];
stack[0] = node;//先将树根节点压入栈中
while(level > -1){
p = stack[level];
level--;//移除栈的顶层节点
System.out.print(p.getData()+" ");
if(null != p.getRchild()){//如果树右子节点不为null,则压入栈中
stack[++level] = p.getRchild();
}
if(null != p.getLchild()){//如果树左子节点不为Null,则压入栈中
stack[++level] = p.getLchild();
}
}
}

2. 中序遍历

此种遍历模式是先读取左子节点,然后读取父节点,最后读取右节点。

2.1  递归中序遍历

<span style="white-space:pre">	</span>/**
* 递归中序遍历
* @param node
*/
public void midTraversal(Node node){
if(null == node){
return;
}else{
midTraversal(node.getLchild());
System.out.print(node.getData()+" ");
midTraversal(node.getRchild());
}
}

2.2 非递归中序遍历

/**
* 非递归中序遍历
* @param node
*/
public void midTraversalNoRecursive(Node node){
if(null == node){
return;
}
int level = -1;
Node[] stack = new Node[1024];
Node p = node;
while(p != null || level > -1){//节点不为null或则当前层数不为-1
while(p != null){
stack[++level] = p;//将p压入栈
p = p.getLchild();//获取p的左子结点
}
if(level > -1){
p = stack[level];//获取栈顶层节点
level--;
System.out.print(p.getData()+" ");
p = p.getRchild();//读取为最下方的左子节点,接着访问该节点的右子节点
}
}
}

3. 后序遍历

此种遍历模式是先读取左右节点,然后再读取父节点。

3.1 递归后序遍历

<span style="white-space:pre">	</span>/**
* 递归后序遍历
* @param node
*/
public void lastTraversal(Node node){
if(null == node){
return;
}else{
lastTraversal(node.getLchild());
lastTraversal(node.getRchild());
System.out.print(node.getData()+" ");
}
}

4. 二叉树的深度遍历

待补充

5. 二叉树的广度遍历

待补充