树的度就是节点的分支的数量 二叉树只有0 1 2三种度 而且有关系式
总节点数n=总度数+1 因为每个节点都可以找到一个度 来自于他的父亲 但是root节点没有父亲 自然也就是没有度的了 哈夫曼树没有度为1的节点 因此知道哈夫曼树的叶子节点的个数就可以求出哈夫曼树的总节点个数了 过程如下
n为总数 n2为度数为2的 n0为度数为0 的 也就是叶子节点
n=2*n2+1
n=n2+n0
下面的式子*2-上式 得到n=2*n0-1
假设哈夫曼树有30个叶子节点 则总结点为59
二叉树
n个节点的树 有n-1个节点可以作为孩子 树中所有节点的度之和也是n-1
@Data
@AllArgsConstructor
@NoArgsConstructor
public class BinaryTreeNode
{
private int data;
private BinaryTreeNode leftChild;
private BinaryTreeNode rightChild;
}
import lombok.AllArgsConstructor;
import lombok.Data;
import lombok.NoArgsConstructor;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
@AllArgsConstructor
@NoArgsConstructor
@Data
public class BinaryTree
{
BinaryTreeNode root;
public void preOrder(BinaryTreeNode root)
{
if (root!=null)
{
System.out.println(root.getData());
preOrder(root.getLeftChild());
preOrder(root.getRightChild());
}
}
public void preOrder()
{
preOrder(root);
}
/**
* 非递归前序遍历
*/
public void preOrderNotRecursive(BinaryTreeNode root)
{
if (root==null)return ;
Stack<BinaryTreeNode >stack =new Stack<>();
while (true)
{
while (root!=null)
{
System.out.println(root.getData());
stack.push(root);
root=root.getLeftChild();
}
if (stack.isEmpty())break;
root=stack.pop();
root=root.getRightChild();
}
}
public void preOrderNotRecursive(){preOrderNotRecursive(root);}
/**
* 中序遍历
*/
public void inOrder(BinaryTreeNode root)
{
if (root!=null)
{
inOrder(root.getLeftChild());
System.out.println(root.getData());
inOrder(root.getRightChild());
}
}
public void inOrder(){inOrder(root);}
/**
* 非递归中序遍历
*/
public void inOrderNotRecursive(BinaryTreeNode root)
{
if (root==null) return ;
Stack<BinaryTreeNode >stack=new Stack<>();
while (true)
{
while (root!=null)
{
stack.push(root);
root = root.getLeftChild();
}
if (stack.isEmpty())break;
root=stack.pop();
System.out.println(root.getData());
root=root.getRightChild();
}
}
public void inOrderNotRecursive(){inOrderNotRecursive(root);}
/**
* 后序遍历
* @param root
*/
public void postOrder(BinaryTreeNode root)
{
if (root!=null)
{
postOrder(root.getLeftChild());
postOrder(root.getRightChild());
System.out.println(root.getData());
}
}
public void postOrder()
{
postOrder(root);
}
/**
* 非递归后序遍历
*/
/**
* 二叉树后序遍历：单栈写法
* 实际上，我们可以只使用一个栈去模拟后序遍历，但是会比较麻烦。为了避免问题变得复杂，我们可以先考虑一下能不能借鉴一下前序遍历的思路。
*
* 首先，我们很确定的是，后序遍历的开头和前序遍历是可以一样的，都是先经过二叉树的最左分支，直到经过的节点是个叶子节点（没有左右孩子）为止。
*
* 代码如下：
*
* while(root!=null) { // 经过所有左节点
* s.push(root);
* root = root.left;
* }
* 接下来很关键，我们得考虑什么时候才能访问节点。首先我们可以很确定一种情况：发现是叶子节点，必然会访问。这是第一种情况。
*
* 我们回想前序遍历和中序遍历的时候，它们经过的路径都是左根右，对于前序和中序来说，访问路径基本上跟经过路径是一致的。但是在后序遍历中，我们先经过根节点，但是我们不会去访问它，而是会选择先访问它的右子节点。所以在这种情况下，我们会将根节点留在栈中不弹出，等到需要访问它的时候再出。
*
* 那么，什么时候才需要访问根节点呢？答案当然就是访问完右子节点之后了。我们如何获取这个信息？这并不难，我们可以记录一下上一次访问的节点，然后判断一下当前经过的节点和上一次访问的节点是什么关系就好了。如果当前经过的节点的右子节点是上一次访问的节点，显然我们需要访问当前节点了。这是第二种情况。
*
* 总结起来，我们什么时候才能访问节点。有如下两种情况：
*
* 当前经过节点是叶子节点。
* 当前经过节点的右子节点是上一次访问的节点。
* @param root
*/
public void postOrderNotRecursive(BinaryTreeNode root)
{
if (root!=null)
{
Stack<BinaryTreeNode> stack=new Stack<>();
BinaryTreeNode pre= null;
while (true)
{
while (root!=null)
{
stack.push(root);
root=root.getLeftChild();
}
if (stack.isEmpty())break;
root=stack.pop();
//判断访问条件
if (root.getRightChild()==null||pre==root.getRightChild())
{
System.out.println(root.getData());
pre=root;
root=null;
}
else
{
stack.push(root);
root = root.getRightChild();
}
}
}
}
/**
* 层次遍历
* @param root
*/
public void levelOrder(BinaryTreeNode root)
{
BinaryTreeNode temp=root;
Queue<BinaryTreeNode>queue=new ArrayDeque<>();
if (root==null)return ;
queue.add(root);
while (!queue.isEmpty())
{
temp=queue.poll();
System.out.println(temp.getData());
BinaryTreeNode left=temp.getLeftChild();
BinaryTreeNode right=temp.getRightChild();
if (left!=null)queue.add(left);
if (right!=null)queue.add(right);
}
}
public void levelOrder()
{
levelOrder(root);
}
/**
* 找到最大值
* @param root
* @return
*/
public int findMax(BinaryTreeNode root)
{
int rootValue,leftChildTreeValue,rightChildTreeValue,maxValue=Integer.MIN_VALUE;
if (root!=null)
{
rootValue=root.getData();
leftChildTreeValue=findMax(root.getLeftChild());
rightChildTreeValue=findMax(root.getRightChild());
maxValue=Integer.max(rootValue,Integer.max(leftChildTreeValue,rightChildTreeValue));
}
return maxValue;
}
public int findMax()
{
return findMax(root);
}
/**
* 因为给定的树是二叉树，所以能在任意地方插入元素。为了插入一个元素，
* 可以使用层次遍历方法找到-一个左孩子或右孩子结点为空的结点，然后插人该元素。
*/
/**
* 插入元素
*/
public void insertInBinaryTree(int data)
{
Queue<BinaryTreeNode> queue=new ArrayDeque<>();
BinaryTreeNode temp=root;
BinaryTreeNode newNode = new BinaryTreeNode();
newNode.setData(data);
newNode.setLeftChild(null);
newNode.setRightChild(null);
if (root==null)
{
root=newNode;
return ;
}
queue.add(root);
while (!queue.isEmpty())
{
temp=queue.poll();
BinaryTreeNode left = temp.getLeftChild();
if (left==null)
{
temp.setLeftChild(newNode);
return ;
}
else
{
queue.add(left);
}
BinaryTreeNode right = temp.getRightChild();
if (temp.getRightChild()==null)
{
temp.setRightChild(newNode);
return ;
}
else
{
queue.add(right);
}
}
}
public void postOrderNotRecursive()
{
postOrderNotRecursive(root);
}
}