二叉樹(3)——三叉チェーンが示す二叉樹
三叉チェーンが表す二叉樹の定義
畏怖する三叉チェーンとは、二叉の木が左の子供の結点、右の子供の結点、父の結点である「三叉」を指す参照データとデータから構成されることを意味します.
前の順序は巡回します:A BD E＿F中で順次巡回します:D BE A Fの後で順次巡回します:D EB F Aレベルは遍歴します:A BC D E Fは二叉の木を印刷します:C F A E B葉の結点の個数:3本の結点のデータの元素:E
畏怖する三叉チェーンとは、二叉の木が左の子供の結点、右の子供の結点、父の結点である「三叉」を指す参照データとデータから構成されることを意味します.
package datastructure.tree.btree;
/**
*
* @author Administrator
*
*/
public class BinTreeNode{
private Object data; //
private BinTreeNode parent; //
private BinTreeNode lChild; //
private BinTreeNode rChild; //
private int height; //
private int size; // （ ）
public BinTreeNode() {
this(null);
}
public BinTreeNode(Object e) {
data = e;
height = 0;
size = 1;
parent = lChild = rChild = null;
}
//************ Node *************/
/**
*
*/
public Object getData() {
return data;
}
public void setData(Object obj) {
data = obj;
}
//------------- ， ------------
/**
*
* @return
*/
public boolean hasParent() {
return parent != null;
}
/**
*
* @return true, false
*/
public boolean hasLChild() {
return null != lChild;
}
/**
*
* @return
*/
public boolean hasRChild() {
return null != rChild;
}
/**
*
* @return
*/
public boolean isLeaf() {
return (!hasLChild() && !hasRChild());
}
/**
*
* @return
*/
public boolean isLChild() {
return (hasParent() && this == parent.lChild);
}
/**
*
* @return
*/
public boolean isRChild() {
return (hasParent()) && this == parent.rChild;
}
//-------------- height -----------------
/**
* ，
* @return
*/
public int getHeight() {
return height;
}
/**
*
*/
public void updateHeight() {
int newH = 0;// 0， 1
if (hasLChild())
newH = Math.max(newH, (lChild.getHeight() + 1));// //////////////???
if (hasRChild())
newH = Math.max(newH, (rChild.getHeight() + 1));// 0 1 ， 1 1
if (newH == height)
return; //
height = newH; // ，
if (hasParent()) //
parent.updateHeight();
}
/********* size **********/
/**
*
* @return
*/
public int getSize() {
return size;
}
/**
*
*/
public void updateSize() {
size = 1; // 1，
if (hasLChild())
size = size + lChild.getSize(); //
if (hasRChild())
size = size + rChild.getSize(); //
if (hasParent())
parent.updateSize();
}
/********** parent **********/
/**
*
* @return
*/
public BinTreeNode getParent() {
return parent;
}
/**
*
*/
public void sever() {
if (!hasParent())
return;
if (isLChild())
parent.lChild = null;
else
parent.rChild = null;
parent.updateHeight(); //
parent.updateSize(); //
parent = null;
}
//********** lChild ********/
/**
*
* @return
*/
public BinTreeNode getLChild() {
return lChild;
}
/**
* ，
* @param lc
* @return
*/
public BinTreeNode setLChild(BinTreeNode lc) {
BinTreeNode oldLC = this.lChild;
if (hasLChild()) {
lChild.sever();
} //
if (null != lc) {
lc.sever(); // lc
this.lChild = lc; //
lc.parent = this;
this.updateHeight(); //
this.updateSize(); //
}
return oldLC; //
}
//********** rChild *********/
/**
*
* @return
*/
public BinTreeNode getRChild() {
return rChild;
}
/**
* ，
* @param rc
* @return
*/
public BinTreeNode setRChild(BinTreeNode rc) {
BinTreeNode oldRC = this.rChild;
if (hasRChild()) {
rChild.sever();
} //
if (null != rc) {
rc.sever(); // rc
this.rChild = rc; //
rc.parent = this;
this.updateHeight(); //
this.updateSize(); //
}
return oldRC; //
}
/**
* toString
*/
public String toString() {
return "" + data;
}
}
package datastructure.tree.btree;
import java.util.*;
import datastructure.common.Strategy;
import datastructure.queue.Queue;
import datastructure.queue.ArrayQueue;
/**
*
* @author luoweifu
*
*/
public class BinaryTreeOrder {
private int leafSize = 0;
private BinTreeNode root = null;
Strategy strategy = new StrategyEqual();
/**
* ，
* @param node
*
*/
public BinaryTreeOrder(BinTreeNode node) {
this.root = node;
Strategy strategy = new StrategyEqual();
}
public BinTreeNode getRoot() {
return root;
}
/**
*
*
* @return Iterator
*/
public Iterator preOrder() {
List<BinTreeNode> list = new LinkedList();
preOrderRecursion(this.root, list);
return list.iterator();
}
/**
*
* @param rt
*
* @param list
* LinkedList
*/
private void preOrderRecursion(BinTreeNode rt, List list) {
if (null == rt)
return; // ，
list.add(rt); //
preOrderRecursion(rt.getLChild(), list);//
preOrderRecursion(rt.getRChild(), list);//
}
/**
*
*
* @return
*/
public Iterator inOrder() {
List<BinTreeNode> list = new LinkedList();
inOrderRecursion(this.root, list);
return list.iterator();
}
/**
*
* @param rt
*
* @param list
* LinkedList
*/
private void inOrderRecursion(BinTreeNode rt, List list) {
if (null == rt)
return; // ，
inOrderRecursion(rt.getLChild(), list);//
list.add(rt); //
inOrderRecursion(rt.getRChild(), list);//
}
/**
*
* @return
*/
public Iterator postOrder() {
List<BinTreeNode> list = new LinkedList();
postOrderRecursion(this.root, list);
return list.iterator();
}
/**
*
* @param rt
*
* @param list
* LinkedList
*/
private void postOrderRecursion(BinTreeNode rt, List list) {
if (null == rt)
return; // ，
postOrderRecursion(rt.getLChild(), list);//
postOrderRecursion(rt.getRChild(), list);//
list.add(rt);//
}
/**
*
* @return
*/
public Iterator levelOrder() {
List<BinTreeNode> list = new LinkedList();
levelOrderTraverse(this.root, list);
return list.iterator();
}
/**
*
* @param rt
* @param list
*/
private void levelOrderTraverse(BinTreeNode rt, List list) {
if (null == rt)
return;
Queue q = new ArrayQueue();
q.push(rt);//
while (!q.isEmpty()) {
BinTreeNode p = (BinTreeNode) q.deQueue(); // p
list.add(p);
if (p.hasLChild())
q.push(p.getLChild()); // p
if (p.hasRChild())
q.push(p.getRChild());
}
}
/**
* e，
* @param e
* @return
*/
public BinTreeNode find(Object e) {
return searchE(root, e);
}
/**
* e
* @param rt
* @param e
* @return
*/
private BinTreeNode searchE(BinTreeNode rt, Object e) {
if (null == rt)
return null;
if (strategy.equal(rt.getData(), e))
return rt;
BinTreeNode v = searchE(rt.getLChild(), e);
if (null == v)
v = searchE(rt.getRChild(), e);
return v;
}
/**
*
* @return
*/
public String printBinTree() {
StringBuilder sb = new StringBuilder();
printBinTree(root, 0, sb);
return sb.toString();
}
/**
*
* @param btree
* @param n
* @param sb
*/
private void printBinTree(BinTreeNode btree, int n, StringBuilder sb) {
if (null == btree)
return;
printBinTree(btree.getRChild(), n + 1, sb);
for (int i = 0; i < n; i++)
sb.append("\t");
if (n >= 0)
sb.append(btree.getData() + "
");
printBinTree(btree.getLChild(), n + 1, sb);
}
/**
*
* @return
*/
public int sizeLeaf() {
searchLeaf(this.root);
return leafSize;
}
/**
*
* @param rt
*/
private void searchLeaf(BinTreeNode rt) {
if (null == rt)
return;
if (rt.isLeaf())
leafSize++;
else {
searchLeaf(rt.getLChild());
searchLeaf(rt.getRChild());
}
}
}
package datastructure.tree.btree;
import java.util.Iterator;
public class BTreeTest2 {
//
// ： ，
public static void main(String args[]) {
//
BinTreeNode roots = new BinTreeNode();
BinTreeNode node = new BinTreeNode();
roots.setData('A');
roots.setLChild(new BinTreeNode('B'));
roots.setRChild(new BinTreeNode('C'));
node = roots.getLChild();
node.setLChild(new BinTreeNode('D'));
node.setRChild(new BinTreeNode('E'));
node = roots.getRChild();
node.setLChild(new BinTreeNode('F'));
BinaryTreeOrder order = new BinaryTreeOrder(roots);
//------ --------
Iterator<BinTreeNode> iter1 = order.preOrder();
System.out.println(" ：");
printIterator(iter1);
Iterator<BinTreeNode> iter2 = order.inOrder();
System.out.println(" ：");
printIterator(iter2);
Iterator<BinTreeNode> iter3 = order.postOrder();
System.out.println(" ：");
printIterator(iter3);
Iterator<BinTreeNode> iter4 = order.levelOrder();
System.out.println(" ：");
printIterator(iter4);
String str = order.printBinTree();
System.out.println(" ：
" + str);
System.out.println(" ：" + order.sizeLeaf());
BinTreeNode nodeone = order.find('E');
System.out.println(" ：" + nodeone.getData());
}
public static void printIterator(Iterator<BinTreeNode> iter) {
while(iter.hasNext()) {
System.out.print("\t" + iter.next().getData());
}
System.out.println();
}
}
前の順序は巡回します:A BD E＿F中で順次巡回します:D BE A Fの後で順次巡回します:D EB F Aレベルは遍歴します:A BC D E Fは二叉の木を印刷します:C F A E B葉の結点の個数:3本の結点のデータの元素:E