基本术语
- 结点：树中的一个独立的单元。包含一个数据元素及若干个分支（二叉树最多两个）
- 结点的度：结点拥有的子树数称为结点的度
- 树的度：树的度是树内各个结点中最大的度
- 叶子：度为0的结点称为叶子或终端结点
- 非终端结点：非叶子的结点
- 双亲和孩子：结点的子树的根称为该结点的孩子，相应的该结点称为孩子的双亲
- 兄弟：父结点相同的结点即为兄弟结点
- 树的深度：树中结点的最大层次称为树的深度或高度
介绍
与前面所介绍循序表以及链表的结构所不同，树结构是一种描述非线性层次关系的数据结构。
其主要有一下几个特点：
- 在一个树结构中，有且仅有一个结点没有直接前驱，那这个结点就是树的根结点
- 除了根结点外，其余结点有且仅有一个直接前驱
- 每个结点可以有n个直接后驱（二叉树最多只有两个）
而在树结构中，二叉树是最简单的一种形式。在研究树结构时，二叉树是树结构内容中的重点。二叉树的描述、处理相对简单，而且更重要的是，任意的树都可以转为二叉树，因此，二叉树是所有树的基础。
二叉树 结构图
二叉树-循环存储.png
二叉树遍历算法
主要有以下三种：
- 先序遍历
- 中序遍历
-
后序遍历
先序遍历.png
中序遍历.png
后序遍历.png
Java代码实现
/**
* 二叉树结构
* Created by Sheldon on 2019/4/3.
* Project Name: alstudy.
* Package Name: tree.
*/
// 二叉树结构
public class ChainTree {
// 结点数据
String data;
// 左子树
ChainTree leftTree;
// 右子树
ChainTree rightTree;
// 二叉树根结点
ChainTree root;
/**
* 初始化二叉树，向根结点插入数据
* @param data
*/
ChainTree(String data){
this.data = data;
this.root = this;
}
public static ChainTree bulieTree(String[] datas, int index){
ChainTree node = null;
if (index<datas.length){
String value = datas[index];
if (value=="#"){
return null;
}
node = new ChainTree(value);
// node.leftTree = bulieTree(datas, 2*index+1);
// node.rightTree = bulieTree(datas,2*index+2);
node.addLeftTree(bulieTree(datas, 2*index+1));
node.addRightTree(bulieTree(datas,2*index+2));
return node;
}
return node;
}
/**
* 添加左子树
* @return
*/
public void addLeftTree(ChainTree node){
leftTree = node;
}
/**
* 添加右子树
* @return
*/
public void addRightTree(ChainTree node){
rightTree = node;
}
/**
* 先序遍历
* @param root
*/
public void DLR(ChainTree root){
ChainTree node = root;
if (node!=null){
System.out.printf(node.data+", ");
DLR(node.leftTree);
DLR(node.rightTree);
}
}
/**
* 中序遍历
* @param root
*/
public void LDR(ChainTree root){
ChainTree node = root;
if (node!=null){
LDR(node.leftTree);
System.out.printf(node.data+", ");
LDR(node.rightTree);
}
}
/**
* 后序遍历
* @param root
*/
public void LRD(ChainTree root){
ChainTree node = root;
if (node!=null){
LRD(node.leftTree);
LRD(node.rightTree);
System.out.printf(node.data+", ");
}
}
/**
* 二叉树深度
* @param node
* @return
*/
public int depth(ChainTree node){
int depleft, depright;
if (node==null){
return 0;
}else {
depleft = depth(node.leftTree);
depright = depth(node.rightTree);
if (depleft>depright){
return depleft+1;
}else {
return depright+1;
}
}
}
public static void main(String[] args) {
String[] datas = new String[]{"0","1","2","3","4","5","6","7","8","9","10"};
// 构建双叉树
ChainTree chainTree = bulieTree(datas,0);
// 先序遍历（中->左->右）
chainTree.DLR(chainTree.root);
System.out.println();
// 中序遍历（左->右->中）
chainTree.LDR(chainTree.root);
System.out.println();
// 后序遍历（左->右->中）
chainTree.LRD(chainTree.root);
System.out.println();
// 二叉树深度
System.out.println(chainTree.depth(chainTree.root));;
}
}
运行结果：
运行结果
