树
树是n(n>0)个结点的有限集合,n=0时称为空树,在任意的一棵非空树中.在任意一棵非空树中
- 有且仅有一个特定的称为根(Root)的结点
-
当n>1时,其余结点可分为m(m>0)个互不相交的有限集T1,T2...其中每一个集合本身又是一棵树,并称为根的子树
image
- 结点拥有的子树数称为结点的度
- 度为0的结点称为叶子结点或终端点
- 度不为0的结点称为非终端结点或分支结点
- 根结点以外,分支结点也称为内部结点
-
树的度是树内各结点的度的最大值
image
-
树的层次和深度
image
1. 树的存储结构
1. 双亲表示法(用处很少)
image
2. 孩子表示法(主要使用)
image
3. 双亲孩子表示法(用处很少)
把每个结点的孩子结点排列起来，以单链表作为存储结构，
则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，
然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中
image
4. 孩子兄弟表示法
孩子兄弟表示法为每个节点设计三个域：
一个数据域，一个该节点的第一个孩子节点域，一个该节点的下一个节点的兄弟指针域
image
3.二叉树
二叉树是n(n>0)个结点的有限集合,该集合或这为空集(称为空二叉树),或者由一个根节点和俩棵互不相交的,分别称为根结点的左子树和又子树的二叉树组成
image
1. 二叉树的存储结构
-
顺序存储(用的很少)
image
-
链式存储
image
创建一个二叉树
public class BinarayTree {
/**
* 根结点
*/
public Node<String> root;
public BinarayTree(String data) {
root = new Node<>(data, null, null);
}
/**
* 生成二叉树
*/
public void createTree() {
Node<String> nodeB = new Node<>("B", null, null);
Node<String> nodeC = new Node<>("C", null, null);
Node<String> nodeD = new Node<>("D", null, null);
Node<String> nodeE = new Node<>("E", null, null);
Node<String> nodeF = new Node<>("F", null, null);
Node<String> nodeG = new Node<>("G", null, null);
Node<String> nodeH = new Node<>("H", null, null);
Node<String> nodeI = new Node<>("I", null, null);
Node<String> nodeJ = new Node<>("J", null, null);
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeC.leftChild = nodeE;
nodeC.rightChild = nodeF;
nodeD.leftChild = nodeG;
nodeD.rightChild = nodeH;
nodeH.leftChild = nodeI;
nodeE.rightChild = nodeJ;
}
/**
* 结点
*
* @param <T>
*/
public class Node<T> {
T data;
Node<T> leftChild;
Node<T> rightChild;
public Node(T data, Node<T> leftChild, Node<T> rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
2. 二叉树的遍历
-
前序(DLR)
规则是若二叉树为空，则空操作返回，否则先访问跟结点，然后前序遍历左子树，再前序遍历右子树
image
BinarayTree tree = new BinarayTree("A");
tree.createTree();
tree.preOrderTraverse(tree.root);
/**
* 前序访问树的所有结点
*
* @param root
*/
public void preOrderTraverse(Node root) {
if (root == null) {
return;
}
System.out.println("mid:" + root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
}
- 中序(LDR)
若树为空,则空操作返回,否则从根结点开始(注意并不是先访问根结点),中序便利根结点的左子树,然后是访问根结点,最后中序遍历右子树
LDR(先取左边,再取中间,最后取右边)image
/**
* 中序访问树的所有结点
*
* @param root
*/
public void midOrderTraverse(Node root) {
if (root == null) {
return;
}
midOrderTraverse(root.leftChild);
System.out.println("mid:" + root.data);
midOrderTraverse(root.rightChild);
}
BinarayTree tree = new BinarayTree("A");
tree.createTree();
tree.midOrderTraverse(tree.root);
取出后为GDHBAEICF
-
后序(LRD)
规则是若树为空，则空操作返回，否则从左到右先叶子后结点的方式遍历访问左右子树，最后是访问根结点
image
/**
* 后序访问树的所有结点
*
* @param root
*/
public void postOrderTraverse(Node root) {
if (root == null) {
return;
}
postOrderTraverse(root.leftChild);
postOrderTraverse(root.rightChild);
System.out.println("mid:" + root.data);
}
BinarayTree tree = new BinarayTree("A");
tree.createTree();
tree.postOrderTraverse(tree.root);
网友评论