|
目录
1、判断完全二叉树
2、遍历
1）前序遍历
递归
?非递归
2）中序遍历
递归
非递归
3）后序遍历
递归
非递归
3、层级遍历
4、获取二叉树节点数
5、获取叶子节点数
6、获取第k层的节点数
树节点?
package com.mzp.tree;
/**
* 平衡二叉树节点
*/
public class AVLTreeNode {
private int data;
//高度
private int height;
//左子节点
private AVLTreeNode left;
//右子节点
private AVLTreeNode right;
public AVLTreeNode(int data) {
this.data = data;
this.height = 1;
}
public int getData() {
return data;
}
public void setData(int data) {
this.data = data;
}
public int getHeight() {
return height;
}
public void setHeight(int height) {
this.height = height;
}
public AVLTreeNode getLeft() {
return left;
}
public void setLeft(AVLTreeNode left) {
this.left = left;
}
public AVLTreeNode getRight() {
return right;
}
public void setRight(AVLTreeNode right) {
this.right = right;
}
}
1、判断完全二叉树
public static void main(String[] args) {
AVLTreeNode root = new AVLTreeNode(1);
AVLTreeNode left = new AVLTreeNode(2);
AVLTreeNode right = new AVLTreeNode(3);
root.setLeft(left);
root.setRight(right);
System.out.println(isBinaryTreeComplete(root));
}
/**
* 判断二叉树是否是完全二叉树
* @param root
* @return true表示该树是完全二叉树
*/
public static boolean isBinaryTreeComplete(AVLTreeNode root){
Queue<AVLTreeNode> queue = new LinkedList<>();
if(root != null){
queue.add(root);
}else{
return false;
}
while (!queue.isEmpty()){
AVLTreeNode poll = queue.poll();
if(poll == null){
break;
}
queue.add(poll.getLeft());
queue.add(poll.getRight());
}
while (!queue.isEmpty()){
AVLTreeNode poll = queue.poll();
if(poll != null){
return false;
}
}
return true;
}
2、遍历
1）前序遍历
递归
//递归遍历 前序
public void preTraversal(AVLTreeNode node){
if(node == null){
return;
}else{
System.out.print(node.getData() + " ");
preTraversal(node.getLeft());
preTraversal(node.getRight());
}
}
?非递归
/*
* 非递归前序遍历
*/
public void preTrasersal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
stack.add(current);
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getData()+ " ");
if (current.getRight() != null) {
stack.add(current.getRight());
}
if (current.getLeft() != null) {
stack.add(current.getLeft());
}
}
}
}
2）中序遍历
递归
//递归遍历 中序
public void inTraversal(AVLTreeNode node){
if(node == null){
return;
}else{
inTraversal(node.getLeft());
System.out.print(node.getData() + " ");
inTraversal(node.getRight());
}
}
非递归
/*
* 非递归中序遍历
*/
public void inTrasersal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
while (current != null) {
stack.add(current);
current = current.getLeft();
}
while (!stack.isEmpty()) {
current = stack.pop();
System.out.print(current.getData() + " ");
current = current.getRight();
while (current != null) {
stack.add(current);
current = current.getLeft();
}
}
}
}
3）后序遍历
递归
//递归遍历 后序
public void postTraversal(AVLTreeNode node){
if(node == null){
return;
}else{
postTraversal(node.getLeft());
postTraversal(node.getRight());
System.out.print(node.getData() + " ");
}
}
非递归
/*
* 非递归后序遍历
*/
public void postTraversal () {
if (root != null) {
Stack<AVLTreeNode> stack = new Stack<AVLTreeNode>();
AVLTreeNode current = root;
AVLTreeNode preNode = null;
while (current != null) {
stack.add(current);
current = current.getLeft();
}
while (!stack.isEmpty()) {
current = stack.pop();
if (current.getRight() == null || current.getRight() == preNode) {
System.out.print(current.getData() + " ");
preNode = current;
} else {
stack.add(current);
current = current.getRight();
while (current != null) {
stack.add(current);
current = current.getLeft();
}
}
}
}
}
3、层级遍历
//层级遍历
public void levelTraversal(AVLTreeNode root){
Queue<AVLTreeNode> queue = new LinkedList<>();
if(root != null){
queue.offer(root);
while(!queue.isEmpty()){
AVLTreeNode node = queue.poll();
System.out.print(node.getData() + " ");
AVLTreeNode left = node.getLeft();
if(left != null){
queue.offer(left);
}
AVLTreeNode right = node.getRight();
if(right != null){
queue.offer(right);
}
}
}
}
4、获取二叉树节点数
/**
* 获取二叉树节点数
* @param root
* @return
*/
public static int binaryTreeNodeSize(AVLTreeNode root){
if(root == null){
return 0;
}
return binaryTreeNodeSize(root.getLeft()) + binaryTreeNodeSize(root.getRight()) + 1;
}
5、获取叶子节点数
public static int binaryTreeLeafSize(AVLTreeNode root){
if(root == null){
return 0;
}
if(root.getLeft() == null && root.getRight() == null){
return 1;
}
return binaryTreeLeafSize(root.getLeft()) + binaryTreeLeafSize(root.getRight());
}
6、获取第k层的节点数
/**
* 获取第k层的节点数
* @param root
* @param k
* @return
*/
public static int nodeSizeLeaveK(AVLTreeNode root, int k){
if(root == null){
return 0;
}
if(k == 1){
return 1;
}
return nodeSizeLeaveK(root.getLeft(), k -1) + nodeSizeLeaveK(root.getRight(), k - 1);
}
参考地址：
数据结构--二叉树--详解_清欢有道的博客-CSDN博客_二叉树
|