二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）。二叉树常被用于实现二叉查找树和二叉堆。
二叉树的第i层至多有2{i-1}个结点；深度为k的二叉树至多有2k-1个结点。一棵深度为k，且有2^k-1个节点称之为满二叉树；深度为k，有n个节点的二叉树，当且仅当其每一个节点都与深度为k的满二叉树中，序号为1至n的节点对应时，称之为完全二叉树。
完全二叉树：一棵二叉树至多只有最下面的一层上的结点的度数可以小于2，并且最下层上的结点都集中在该层最左边的若干位置上，则此二叉树成为完全二叉树。
满二叉树：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树。
二叉树的链式存储结构是一类重要的数据结构，其形式定义如下：
private class TreeNode{
private int key=0;
private String data=null;
private boolean isVisted=false;
private TreeNode leftChild=null;
private TreeNode rightChild=null;
public TreeNode(){}
/**
* @param key 层序编码
* @param data 数据域
*/
public TreeNode(int key,String data){
this.key=key;
this.data=data;
this.leftChild=null;
this.rightChild=null;
}
}
二叉树的创建：
//按先序(前序)序列创建二叉树
int CreateBiTree(TreeNode T){
TreeNode newNodeB = new TreeNode(2,"B");
TreeNode newNodeC = new TreeNode(3,"C");
TreeNode newNodeD = new TreeNode(4,"D");
TreeNode newNodeE = new TreeNode(5,"E");
TreeNode newNodeF = new TreeNode(6,"F");
//创建根节点
T =new TreeNode(1,"rootNode(A)");
//构造左子树
root.leftChild=newNodeB;
//构造右子树
root.rightChild=newNodeC;
root.leftChild.leftChild=newNodeD;
root.leftChild.rightChild=newNodeE;
root.rightChild.rightChild=newNodeF;
}
二叉树的遍历：
//树的高度
public int height(TreeNode subTree){
if(subTree==null) // 递归出口
return 0;//递归结束：空树高度为0
else{
int depthLeft =height(subTree.leftChild);
int depthRight =height(subTree.rightChild);
return (depthLeft < depthRight)?(depthRight +1):(depthLeft +1);
}
}
//输出
public void visted(TreeNode subTree){
subTree.isVisted=true;
System.out.println("key:"+subTree.key+"--name:"+subTree.data);;
}
//节点个数
public int size(TreeNode subTree){
if(subTree==null){
return 0;
}else{
return 1+size(subTree.leftChild)
+size(subTree.rightChild);
}
}
//递归前序遍历
public void preOrder(TreeNode subTree){
if(subTree!=null){
//访问根节点
visted(subTree);
//访问左子结点
preOrder(subTree.leftChild);
//访问右子结点
preOrder(subTree.rightChild);
}
}
//递归中序遍历
public void inOrder(TreeNode subTree){
if(subTree!=null){
//访问左子结点
inOrder(subTree.leftChild);
//访问根节点
visted(subTree);
//访问右子结点
inOrder(subTree.rightChild);
}
}
//递归后续遍历
public void postOrder(TreeNode subTree) {
if (subTree != null) {
//访问左子结点
postOrder(subTree.leftChild);
//访问右子结点
postOrder(subTree.rightChild);
//访问根节点
visted(subTree);
}
}
//非递归先序遍历：访问T.data后，将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，再先序遍历T的右子树。
public void nonRecPreOrder(TreeNode T){
Stack<TreeNode> stack=new Stack<TreeNode>();
//node是遍历指针实例
TreeNode node=T;
//栈不空或者node不空时循环
while(node!=null||stack.size()>0){
if(node!=null){
//访问根节点
visted(node);
//存入栈中
stack.push(node);
//遍历左子树
node=node.leftChild;
}
eles if(stack.size()>0){
//退栈
node=stack.pop();
//访问右子树
node=node.rightChild;
}
}
}
//非递归中序遍历：先将T入栈，遍历左子树；遍历完左子树返回时，栈顶元素应为T，出栈，访问T.data，再中序遍历T的右子树。
public void nonRecInOrder(TreeNode T){
Stack<TreeNode> stack =new Stack<BinaryTree.TreeNode>();
TreeNode node =T;
//栈不空或者node不空时循环
while(node!=null||stack.size()>0){
//存在左子树
while(node!=null){
//存入栈中
stack.push(node);
//遍历左子树
node=node.leftChild;
}
//栈非空
if(stack.size()>0){
//退栈，访问根节点
node=stack.pop();
visted(node);
//访问右子树
node=node.rightChild;
}
}
}
//非递归后序遍历：T是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。
public void noRecPostOrder(TreeNode T){
Stack<TreeNode> stack=new Stack<BinaryTree.TreeNode>();
TreeNode node =T;
while(T!=null){
//左子树入栈
for(;T.leftChild!=null;T=T.leftChild){
stack.push(T);
}
//当前结点无右子树或右子树已经输出
while(T!=null&&(T.rightChild==null||T.rightChild==node)){
visted(T);
//纪录上一个已输出结点
node =T;
if(stack.empty())
return;
T=stack.pop();
}
//处理右子树
stack.push(T);
T=T.rightChild;
}
}
//求二叉树中的节点个数
int GetNodeNum(TreeNode pRoot)
{
if(pRoot == NULL) // 递归出口
return 0;
return GetNodeNum(pRoot.leftChild) + GetNodeNum(pRootrightChild) + 1;
}
参考：面试中的二叉树题目
网友评论