性质
- 在二叉树的第i层上至多有2i-1个结点（i>=1）。
- 深度为k的二叉树至多有2k-1个结点（k>=1）。
- 对任何一颗二叉树T，如果其终端结点数为n0,度为2的 结点 数为n2，则n0 = n2+1.
- 具有n个结点的完全二叉树深度为[log2n]+1 ([x]表示不 大于 x的最大整数)。
- 如果对一颗有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。
节点
public class TreeNode<T>{
public TreeNode leftChild;
public TreeNode rightChild;
public Integer index;
public T data;
public TreeNode( T data) {
this.data = data;
}
public TreeNode(Integer index, T data) {
this.index = index;
this.data = data;
}
@Override
public String toString() {
return "TreeNode{" +
"leftChild=" + leftChild +
", rightChild=" + rightChild +
", index=" + index +
", data=" + data +
'}';
}
}
二叉树建立
/**
* 构建二叉树
* A
* B C
* D E F
*/
public void createBinaryTree(){
System.out.println(" A");
System.out.println(" / \\");
System.out.println(" B C");
System.out.println(" / \\ \\");
System.out.println(" D E F");
TreeNode<String> nodeA = new TreeNode<String>(1, "A");
this.rootNode = nodeA;
TreeNode<String> nodeB = new TreeNode<String>(2, "B");
TreeNode<String> nodeC = new TreeNode<String>(3, "C");
TreeNode<String> nodeD = new TreeNode<String>(4, "D");
TreeNode<String> nodeE = new TreeNode<String>(5, "E");
TreeNode<String> nodeF = new TreeNode<String>(7, "F");
nodeA.leftChild = nodeB;
nodeA.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.rightChild = nodeF;
//nodeF.rightChild = new TreeNode(8,"G");
}
/**
* 前序遍历反向生成二叉树
* ABD##E##C#F
*/
public TreeNode createBinaryTree(AtomicInteger dataIndex,T[] datas){
if (dataIndex.get()>=datas.length||"#".equals(datas[dataIndex.get()])){
return null;
}
TreeNode treeNode = new TreeNode(dataIndex.get(), datas[dataIndex.get()]);
if (this.rootNode == null){
this.rootNode = treeNode;
}
dataIndex.incrementAndGet();
treeNode.leftChild = createBinaryTree(dataIndex, datas);
dataIndex.incrementAndGet();
treeNode.rightChild = createBinaryTree(dataIndex, datas);
return treeNode;
}
二叉树遍历
/**
* 前序遍历 根 左 右
*/
public void preOrder(TreeNode currNode){
if (currNode==null)
return;
System.out.println(currNode.data);
preOrder(currNode.leftChild);
preOrder(currNode.rightChild);
}
/**
*
* 中序遍历 左 根 右
*/
public void midOrder(TreeNode currNode){
if (currNode == null)
return;
midOrder(currNode.leftChild);
System.out.println(currNode.data);
midOrder(currNode.rightChild);
}
/**
* 后序遍历 左 右 根
*/
public void afterOrder(TreeNode currNode){
if (currNode==null)
return;
afterOrder(currNode.leftChild);
afterOrder(currNode.rightChild);
System.out.println(currNode.data);
}
/**
* 非递归形式树的前中后序遍历
*/
public void preNoneCycle(TreeNode currNode){
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
treeNodeStack.push(currNode);
while (!treeNodeStack.isEmpty()){
TreeNode tempNode = treeNodeStack.pop();
if (tempNode!=null)
System.out.println(tempNode.data);
if (tempNode.rightChild !=null)
treeNodeStack.push(tempNode.rightChild);
if (tempNode.leftChild !=null)
treeNodeStack.push(tempNode.leftChild);
}
}
/**
* 非递归中序遍历
* @param currNode
*/
public void midNoneCycle(TreeNode currNode){
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
while (currNode != null || !treeNodeStack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currNode != null) {
treeNodeStack.push(currNode);
currNode = currNode.leftChild;
}
currNode = treeNodeStack.pop();
System.out.println(currNode.data);
currNode = currNode.rightChild;
}
}
/**
* 非递归后序遍历
* @param currNode
*/
public void afterNoneCycle(TreeNode currNode){
LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
TreeNode currentNode = currNode;
TreeNode rightNode = null;
while (currentNode != null || !stack.isEmpty()) {
// 一直循环到二叉排序树最左端的叶子结点（currentNode是null）
while (currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.leftChild;
}
currentNode = stack.pop();
// 当前结点没有右结点或上一个结点（已经输出的结点）是当前结点的右结点，则输出当前结点
while (currentNode.rightChild == null || currentNode.rightChild == rightNode) {
System.out.print(currentNode.data + " ");
rightNode = currentNode;
if (stack.isEmpty()) {
return; //root以输出，则遍历结束
}
currentNode = stack.pop();
}
stack.push(currentNode); //还有右结点没有遍历
currentNode = currentNode.rightChild;
}
}
/**
* 广度优先遍历二叉树，又称层次遍历二叉树
* @param node
*/
public void breadthFirstTraverse(Node<E> root) {
Queue<Node<E>> queue = new LinkedList<Node<E>>();
Node<E> currentNode = null;
queue.offer(root);
while (!queue.isEmpty()) {
currentNode = queue.poll();
System.out.print(currentNode.value + " ");
if (currentNode.left != null)
queue.offer(currentNode.left);
if (currentNode.right != null)
queue.offer(currentNode.right);
}
}
二叉树高度
public int getHeight(){
return getHeight(this.rootNode);
}
public int getHeight(TreeNode currNode){
if (currNode==null){
return 0;
}
int lHeight = getHeight(currNode.leftChild);
int rHeight = getHeight(currNode.rightChild);
return Math.max(lHeight,rHeight)+1;
}
二叉树节点数量
public int getSize(){
return getSize(this.rootNode);
}
public int getSize(TreeNode currNode){
if (currNode==null){
return 0;
}
int lSize = getSize(currNode.leftChild);
int rSize = getSize(currNode.rightChild);
return lSize + rSize + 1;
}
测试代码
package com.execlib;
import java.util.Stack;
import java.util.concurrent.atomic.AtomicInteger;
public class BinaryTreeTree<T> {
public TreeNode rootNode = null;
/**
* 树的建立
*/
public class TreeNode<T>{
public TreeNode leftChild;
public TreeNode rightChild;
public Integer index;
public T data;
public TreeNode( T data) {
this.data = data;
}
public TreeNode(Integer index, T data) {
this.index = index;
this.data = data;
}
@Override
public String toString() {
return "TreeNode{" +
"leftChild=" + leftChild +
", rightChild=" + rightChild +
", index=" + index +
", data=" + data +
'}';
}
}
/**
* 构建二叉树
* A
* B C
* D E F
*/
public void createBinaryTree(){
System.out.println(" A");
System.out.println(" / \\");
System.out.println(" B C");
System.out.println(" / \\ \\");
System.out.println(" D E F");
TreeNode<String> nodeA = new TreeNode<String>(1, "A");
this.rootNode = nodeA;
TreeNode<String> nodeB = new TreeNode<String>(2, "B");
TreeNode<String> nodeC = new TreeNode<String>(3, "C");
TreeNode<String> nodeD = new TreeNode<String>(4, "D");
TreeNode<String> nodeE = new TreeNode<String>(5, "E");
TreeNode<String> nodeF = new TreeNode<String>(7, "F");
nodeA.leftChild = nodeB;
nodeA.rightChild = nodeC;
nodeB.leftChild = nodeD;
nodeB.rightChild = nodeE;
nodeC.rightChild = nodeF;
//nodeF.rightChild = new TreeNode(8,"G");
}
/**
* 前序遍历反向生成二叉树
* ABD##E##C#F
*/
public TreeNode createBinaryTree(AtomicInteger dataIndex,T[] datas){
if (dataIndex.get()>=datas.length||"#".equals(datas[dataIndex.get()])){
return null;
}
TreeNode treeNode = new TreeNode(dataIndex.get(), datas[dataIndex.get()]);
if (this.rootNode == null){
this.rootNode = treeNode;
}
dataIndex.incrementAndGet();
treeNode.leftChild = createBinaryTree(dataIndex, datas);
dataIndex.incrementAndGet();
treeNode.rightChild = createBinaryTree(dataIndex, datas);
return treeNode;
}
/**
* 递归形式树的前中后序遍历
*/
/**
* 前序遍历 根 左 右
*/
public void preOrder(TreeNode currNode){
if (currNode==null)
return;
System.out.println(currNode.data);
preOrder(currNode.leftChild);
preOrder(currNode.rightChild);
}
/**
*
* 中序遍历 左 根 右
*/
public void midOrder(TreeNode currNode){
if (currNode == null)
return;
midOrder(currNode.leftChild);
System.out.println(currNode.data);
midOrder(currNode.rightChild);
}
/**
* 后序遍历 左 右 根
*/
public void afterOrder(TreeNode currNode){
if (currNode==null)
return;
afterOrder(currNode.leftChild);
afterOrder(currNode.rightChild);
System.out.println(currNode.data);
}
/**
* 非递归形式树的前中后序遍历
*/
public void preNoneCycle(TreeNode currNode){
Stack<TreeNode> treeNodeStack = new Stack<TreeNode>();
treeNodeStack.push(currNode);
while (!treeNodeStack.isEmpty()){
TreeNode tempNode = treeNodeStack.pop();
if (tempNode!=null)
System.out.println(tempNode.data);
if (tempNode.rightChild !=null)
treeNodeStack.push(tempNode.rightChild);
if (tempNode.leftChild !=null)
treeNodeStack.push(tempNode.leftChild);
}
}
public int getSize(){
return getSize(this.rootNode);
}
public int getSize(TreeNode currNode){
if (currNode==null){
return 0;
}
int lSize = getSize(currNode.leftChild);
int rSize = getSize(currNode.rightChild);
return lSize + rSize + 1;
}
public int getHeight(){
return getHeight(this.rootNode);
}
public int getHeight(TreeNode currNode){
if (currNode==null){
return 0;
}
int lHeight = getHeight(currNode.leftChild);
int rHeight = getHeight(currNode.rightChild);
return Math.max(lHeight,rHeight)+1;
}
public static void main(String[] args) {
BinaryTreeTree<String> testTree = new BinaryTreeTree<String>();
testTree.createBinaryTree();
System.out.println("---------------");
int height = testTree.getHeight();
System.out.println("tree height :"+height);
int size = testTree.getSize();
System.out.println("tree size :"+size);
System.out.println("---------------");
System.out.println("tree preOrder :");
testTree.preOrder(testTree.rootNode);
System.out.println("tree midOrder :");
testTree.midOrder(testTree.rootNode);
System.out.println("tree afterOrder :");
testTree.afterOrder(testTree.rootNode);
System.out.println("tree preNoneCycle :");
testTree.preNoneCycle(testTree.rootNode);
System.out.println("create tree :");
testTree.preOrder(testTree.createBinaryTree(new AtomicInteger(0),new String[]{"A","B","D","#","#","E","#","#","C","#","F"}));
}
}
A
/ \
B C
/ \ \
D E F
---------------
tree height :3
tree size :6
---------------
tree preOrder :
A
B
D
E
C
F
tree midOrder :
D
B
E
A
C
F
tree afterOrder :
D
E
B
F
C
A
tree preNoneCycle :
A
B
D
E
C
F
create tree :
A
B
D
E
C
F
查找二叉树
节点
public class SearchNode<T> extends TreeNode<T>{
public SearchNode parent;
public SearchNode(T data) {
super(data);
}
public SearchNode(Integer index, T data) {
super(index, data);
}
}
加入节点
/**
* 二叉树存放节点
* @param data
* @return
*/
public TreeNode put(int data){
SearchNode<Integer> newNode = new SearchNode<Integer>(data);
if (this.rootNode == null){
rootNode = newNode;
return newNode;
}
TreeNode<Integer> node = (SearchNode<Integer>) rootNode;
TreeNode<Integer> parent = null;
while (node!=null){
parent = node;
if (data<node.data){
node = node.leftChild;
}else if (data>node.data){
node = node.rightChild;
}else {
return node;
}
}
if (parent.data>data)
parent.leftChild = newNode;
else parent.rightChild = newNode;
((SearchNode)newNode).parent = (SearchNode) parent;
return newNode;
}
查找数据
/**
* 查找数据
* @param data
* @return
*/
public TreeNode search(int data){
TreeNode<Integer> node = rootNode;
while (node!=null){
if (data<node.data){
node = node.leftChild;
}else if (data>node.data){
node = node.rightChild;
}else {
return node;
}
}
return null;
}
删除数据
/**
* 删除数据并调整节点顺序
* @param data
* @return
*/
public TreeNode delete(int data){
SearchNode node = (SearchNode) search(data);
if (node == null)
return null;
return delete(node);
}
/**
* 删除节点
* @param node
* @return
*/
private SearchNode delete(SearchNode node) {
//没有左右孩子直接删除
if (node.leftChild==null&&node.rightChild==null){
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = null;
}else {
parent.rightChild = null;
}
return node;
}
//只有左孩子
if (node.leftChild!=null&&node.rightChild==null){
SearchNode next = (SearchNode) node.leftChild;
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = next;
}else {
parent.rightChild = next;
}
return node;
}
//只有右孩子
if (node.leftChild==null&&node.rightChild!=null){
SearchNode next = (SearchNode) node.rightChild;
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = next;
}else {
parent.rightChild = next;
}
return node;
}
//有左右孩子 获取后继节点并删除后继然后将后继的值赋值给当前节点
SearchNode nextNode = getNextNode(node);
delete(nextNode);
node.data = nextNode.data;
return node;
}
/**
* 获取某节点的后继节点
* @param node
* @return
*/
private SearchNode getNextNode(SearchNode node) {
//当前节点有右孩子
if (node.rightChild!=null){
node = (SearchNode) node.rightChild;
while (node.leftChild!=null){
node = (SearchNode) node.leftChild;
}
return node;
}
//当前节点没有右孩子
SearchNode parent = node.parent;
while (parent!=null&&node==parent.rightChild){
node = parent;
parent = parent.parent;
}
return parent;
}
完整代码
package com.execlib;
public class BinarySearchTree extends BinaryTreeTree<Integer>{
public class SearchNode<T> extends TreeNode<T>{
public SearchNode parent;
public SearchNode(T data) {
super(data);
}
public SearchNode(Integer index, T data) {
super(index, data);
}
}
/**
* 二叉树存放节点
* @param data
* @return
*/
public TreeNode put(int data){
SearchNode<Integer> newNode = new SearchNode<Integer>(data);
if (this.rootNode == null){
rootNode = newNode;
return newNode;
}
TreeNode<Integer> node = (SearchNode<Integer>) rootNode;
TreeNode<Integer> parent = null;
while (node!=null){
parent = node;
if (data<node.data){
node = node.leftChild;
}else if (data>node.data){
node = node.rightChild;
}else {
return node;
}
}
if (parent.data>data)
parent.leftChild = newNode;
else parent.rightChild = newNode;
((SearchNode)newNode).parent = (SearchNode) parent;
return newNode;
}
/**
* 查找数据
* @param data
* @return
*/
public TreeNode search(int data){
TreeNode<Integer> node = rootNode;
while (node!=null){
if (data<node.data){
node = node.leftChild;
}else if (data>node.data){
node = node.rightChild;
}else {
return node;
}
}
return null;
}
/**
* 删除数据并调整节点顺序
* @param data
* @return
*/
public TreeNode delete(int data){
SearchNode node = (SearchNode) search(data);
if (node == null)
return null;
return delete(node);
}
/**
* 删除节点
* @param node
* @return
*/
private SearchNode delete(SearchNode node) {
//没有左右孩子直接删除
if (node.leftChild==null&&node.rightChild==null){
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = null;
}else {
parent.rightChild = null;
}
return node;
}
//只有左孩子
if (node.leftChild!=null&&node.rightChild==null){
SearchNode next = (SearchNode) node.leftChild;
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = next;
}else {
parent.rightChild = next;
}
return node;
}
//只有右孩子
if (node.leftChild==null&&node.rightChild!=null){
SearchNode next = (SearchNode) node.rightChild;
SearchNode parent = node.parent;
if (parent.leftChild==node){
parent.leftChild = next;
}else {
parent.rightChild = next;
}
return node;
}
//有左右孩子 获取后继节点并删除后继然后将后继的值赋值给当前节点
SearchNode nextNode = getNextNode(node);
delete(nextNode);
node.data = nextNode.data;
return node;
}
/**
* 获取某节点的后继节点
* @param node
* @return
*/
private SearchNode getNextNode(SearchNode node) {
//当前节点有右孩子
if (node.rightChild!=null){
node = (SearchNode) node.rightChild;
while (node.leftChild!=null){
node = (SearchNode) node.leftChild;
}
return node;
}
//当前节点没有右孩子
SearchNode parent = node.parent;
while (parent!=null&&node==parent.rightChild){
node = parent;
parent = parent.parent;
}
return parent;
}
public static void main(String[] args) {
BinarySearchTree binarySearchTree = new BinarySearchTree();
int[] ints = {50, 30, 20, 44, 88, 33, 87, 16, 7, 77};
for (int i = 0; i < ints.length; i++) {
binarySearchTree.put(ints[i]);
}
binarySearchTree.midOrder(binarySearchTree.rootNode);
System.out.println("search result:"+binarySearchTree.search(88));
binarySearchTree.delete(30);
System.out.println("delete result:");
binarySearchTree.midOrder(binarySearchTree.rootNode);
}
}
测试结果
7
16
20
30
33
44
50
77
87
88
search result:TreeNode{leftChild=TreeNode{leftChild=TreeNode{leftChild=null, rightChild=null, index=null, data=77}, rightChild=null, index=null, data=87}, rightChild=null, index=null, data=88}
delete result:
7
16
20
33
44
50
77
87
88
