树
树
节点的度
结点拥有的子树数称为结点的度。度为0的结点称为叶子结点或终端结点，度不为0的结点称为非终端结点或分支结点。除根结点以外，分支结点也称为内部结点。树的度是树内各结点的度的最大值。
度
层次和深度
定义
森林
森林
树的存储结构
三种表示方法：
双亲表示法
孩子表示法
双亲孩子表示法
孩子兄弟表示法
双亲表示法
在每个结点中，附设一个指示器指示其双亲结点到链表中的位置。
数据格式
列如：
树
数据
image.png
孩子表示法
方案一：
方案一
方案二：
方案二
孩子双亲表示法
把每个结点的孩子结点排列起来，以单链表作为存储结构，则n个结点有n个孩子链表，如果是叶子结点则此单链表为空，然后n个头指针又组成一个线性表，采用顺序存储结构，存放在一个一维数组中
孩子双亲
二叉树
二叉树的定义
二叉树
满二叉树
满二叉树
完全二叉树
定义
对于一个树高为h的二叉树，如果其第0层至第h-1层的节点都满。如果最下面一层节点不满，则所有的节点在左边的连续排列，空位都在右边。这样的二叉树就是一棵完全二叉树。
二叉树的性质
性质1：在二叉树的第i层上至多有2i-1个结点（i>=1）。
性质2：深度为k的二叉树至多有2k-1个结点（k>=1）。
性质3：对任何一颗二叉树T，如果其终端结点数为n0,度为2的 结点 数为n2，则n0 = n2+1.
性质4：具有n个结点的完全二叉树深度为[log2n]+1 ([x]表示不 大于 x的最大整数)。
性质5：如果对一颗有n个结点的完全二叉树（其深度为[log2n]+1） 的结点按层序编号（从第1层到第[log2n]+1层，每层从左到 右），对任意一个结点i(1<=i<=n)有：
1）.如果i=1,则结点i是二叉树的根，无双亲；如果i>1,则其双亲是结 点[i/2]
2）.如果2i>n,则结点i无左孩子（结点i为叶子结点）；否则其左孩 子是结点2i。
3）.如果2i+1>n,则结点i无右孩子；否则其右孩子是结点2i+1。
二叉树的链式存储结构
二叉树的遍历
L：左指针 D：数据 R：右指针
前序遍历：DLR
中序遍历：LDR
后序遍历：LRD
比如遍历这个二叉树
前序遍历
前序遍历：ABDGH CEIF
中序遍历
中序遍历：GDHBAEICF
后序遍历
后序遍历：GHDB IEFCA
二叉排序树
1）若左子树不为空，那么左子树上面的所有节点的关键字值都比根节点的关键字值小
2）若右子树不为空，那么右子树上面的所有节点的关键字值都比根节点的关键字值大
3）左右子树都为二叉树
二叉排序树
二叉排序树就是比结点大的放右边小的放左边
二叉树的遍历：
public class BinarayThree {
public Node root;
public Node getRoot(){
return root;
}
public BinarayThree(String data) {
this.root = new Node(data,null,null);
}
public static class Node<T>{
T data;
Node leftChild;
Node rightChild;
public Node(T data, Node leftChild, Node rightChild) {
this.data = data;
this.leftChild = leftChild;
this.rightChild = rightChild;
}
}
/**
* 前序遍历
* 递归的方式
* @param node
*/
public void preOrderTraverse(Node node){
if (root==null){
return;
}
System.out.print(root.data);
preOrderTraverse(root.leftChild);
preOrderTraverse(root.rightChild);
}
/**
* 前序遍历
* @param node
*/
public void preOrderTraverse2(Node node){
if (root==null){
return;
}
Stack<Node<String>> stack = new Stack<>();
stack.push(root);
while (!stack.isEmpty()){
Node<String> cur = stack.pop();
System.out.print(cur.data);
if (cur.rightChild!=null){
stack.push(cur.rightChild);
}
if (cur.leftChild!=null){
stack.push(cur.leftChild);
}
}
}
public void createThree(){
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);
root.leftChild = nodeB;
root.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.rightChild = nodeF;
}
public static void main(String[] args){
BinarayThree rTree = new BinarayThree("A");
rTree.createThree();
rTree.preOrderTraverse(rTree.root);
rTree.preOrderTraverse2(rTree.root);
}
}
二叉排序树、二叉树的数据搜索和删除
public class SearchBinaryTree {
public TreeNode root;
public TreeNode getRoot() {
return root;
}
//二叉排序树
public TreeNode put(int data) {
if (root == null) {
TreeNode node = new TreeNode(data);
root = node;
return node;
}
TreeNode parent = null;
TreeNode node = root;
for(; node != null;) {
parent = node;
if (data < node.data) {
node = node.leftChild;
} else if(data > node.data) {
node = node.rightChild;
} else {
return node;
}
}
TreeNode newNode = new TreeNode(data);
if (data < parent.data) {
parent.leftChild = newNode;
} else {
parent.rightChild = newNode;
}
// 有坑
newNode.parent = parent;
return newNode;
}
//
public void midOrderTraverse(TreeNode root) {
if (root == null) {
return;
}
midOrderTraverse(root.leftChild);
System.out.print(root.data + " ");
midOrderTraverse(root.rightChild);
}
//搜索
public TreeNode searchNode (int data) {
if (root == null) {
return null;
}
TreeNode node = root;
while (node != null) {
if (node.data == data) {
return node;
} else if (node.data < data) {
node = node.rightChild;
} else if(node.data > data) {
node = node.leftChild;
}
}
return null;
}
public class TreeNode{
int data;
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(int data) {
super();
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.parent = null;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public TreeNode getLeftChild() {
return leftChild;
}
public void setLeftChild(TreeNode leftChild) {
this.leftChild = leftChild;
}
public TreeNode getRightChild() {
return rightChild;
}
public void setRightChild(TreeNode rightChild) {
this.rightChild = rightChild;
}
public TreeNode getParent() {
return parent;
}
public void setParent(TreeNode parent) {
this.parent = parent;
}
}
/**
* 删除一个节点
* @param node
*/
private void delNode(TreeNode node){
if(node == null) {
throw new NoSuchElementException();
} else {
TreeNode parent = node.parent;
//1：没有孩子
if (node.leftChild ==null && node.rightChild ==null) {
if (parent == null) {
root = null;
} else if (parent.rightChild == node) {
parent.rightChild = null;
} else if(parent.leftChild == node) {
parent.leftChild = null;
}
node.parent = null;
} else if (node.leftChild != null && node.rightChild == null) {
//2：只有左孩子
if (parent == null) {
node.parent = null;
node.leftChild.parent = null;
root = node.leftChild;
} else {
if (parent.leftChild == node) {
parent.leftChild = node.leftChild;
} else {
parent.rightChild = node.leftChild;
}
node.parent = null;
}
} else if (node.leftChild == null && node.rightChild != null) {//3：只有右孩子
if (parent == null) {
node.parent = null;
node.rightChild.parent = null;
root = node.rightChild;
} else {
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
node.parent = null;
}
} else {//4：有左右两个孩子
//1：删除节点的右子树的左子树是否为空，如果为空，则把要删除节点的左子树设为删除点的右子树的左子树
if (node.rightChild.leftChild == null) {
node.rightChild.leftChild = node.leftChild;
if (parent == null) {
root = node.rightChild;
} else {
if (parent.leftChild == node) {
parent.leftChild = node.rightChild;
} else {
parent.rightChild = node.rightChild;
}
}
node.rightChild.parent = parent;
node.parent = null;
} else {
// 最左子树
TreeNode leftNode = getMinLeftTreeNode(node.rightChild);
// 001
leftNode.leftChild.parent = leftNode;
leftNode.leftChild = node.leftChild;
//002
TreeNode leftNodeP = leftNode.parent;
leftNodeP.leftChild = leftNode.rightChild;
if(leftNode.rightChild != null){
leftNode.rightChild.parent = leftNode.parent;
}
//003
leftNode.rightChild = node.rightChild;
//004
if (parent == null) {
root = leftNode;
} else {
if (parent.leftChild == node) {
parent.leftChild = leftNode;
} else {
parent.rightChild = leftNode;
}
}
leftNode.parent = parent;
}
}
}
}
private TreeNode getMinLeftTreeNode(TreeNode node) {
TreeNode curRoot = null;
if (node == null) {
return null;
} else {
curRoot = node;
while(curRoot.leftChild != null) {
curRoot = curRoot.leftChild;
}
}
return curRoot;
}
public static void main(String[] args) {
int[] arrays = {12, 3 ,23, 5 ,8, 1, 19};
SearchBinaryTree tree = new SearchBinaryTree();
for(int i: arrays) {
tree.put(i);
}
tree.midOrderTraverse(tree.root);
System.out.println();
TreeNode node = tree.searchNode(1);
tree.delNode(node);
tree.midOrderTraverse(tree.root);
}
}
