二叉树基本操作的实现（java）

定义节点类：

public class PTNode {
	int data;
	PTNode LeftChild;
	PTNode RightChild;
	public PTNode(int data) {
		this.data = data;
		this.LeftChild = null;
		this.RightChild = null;
	}
	public int getData() {
		return data;
	}
	public void setData(int data) {
		this.data = data;
	}
	public PTNode getLeftChild() {
		return LeftChild;
	}
	public void setLeftChild(PTNode leftChild) {
		LeftChild = leftChild;
	}
	public PTNode getRightChild() {
		return RightChild;
	}
	public void setRightChild(PTNode rightChild) {
		RightChild = rightChild;
	}
	
}

一求二叉树的最大深度：根节点到最远叶子结点的距离

int getMaxDeath(PTNode root) {
		if(null == root) {
			return 0;
		}
		int left = getMaxDeath(root.LeftChild);
		int right = getMaxDeath(root.RightChild);
		return Math.max(left, right)+1;
	}

二求二叉树的最小深度：根节点到最近叶子结点的距离

int getMinDepth(PTNode root) {
		if(null == root) {
			return 0;
		}
		
		if(null == root.LeftChild) {
			return getMinDepth(root.RightChild)+1;
		}
		if(null == root.RightChild) {
			return getMinDepth(root.LeftChild)+1;
		}
		
		int left = getMaxDeath(root.LeftChild)+1;
		int right = getMaxDeath(root.RightChild)+1;
		return Math.min(left, right);
	}

三求二叉树的节点个数

int getNumOfTreeNode(PTNode root) {
		if(null == root) {
			return 0;
		}
		return getNumOfTreeNode(root.LeftChild)+getNumOfTreeNode(root.RightChild)+1;
	}

四求二叉树叶子节点个数

int getNumOfChildNode(PTNode root) {
		if(null == root) {
			return 0;
		}
		if(null == root.LeftChild && null == root.RightChild) {
			return 1;
		}
		return getNumOfChildNode(root.LeftChild)+getNumOfChildNode(root.RightChild);
	}

五求二叉树中第k层节点的个数

int getNumOfLevelNode(PTNode root,int k) {
		if(null == root || k<1) {
			return 0;
		}
		if(1 == k) {
			return 1;
		}
		
		int numleft = getNumOfLevelNode(root.LeftChild,k-1);
		int numright = getNumOfLevelNode(root.RightChild,k-1);
		return numleft + numright;
	}

六判断二叉树是否为平衡二叉树

对于每一个节点，它的右子树深度减去左子树的深度的绝对值必须小于2

boolean isBalancedTree(PTNode root) {
		if(null == root) {
			return true;
		}
		
		int left = getMaxDeath(root.LeftChild);
		int right = getMaxDeath(root.RightChild);
		if(Math.abs(left-right) > 1) {
			return false;
		}
		return isBalancedTree(root.LeftChild) && isBalancedTree(root.RightChild);
	}

七判断是否为完全二叉树

除第h层外其他各层的节点数都达到最大个数，且第h层所有的节点都连续集中在最左边

boolean isCompleteTree(PTNode root) {
		if(null == root) {
			return false;
		}
		Queue<PTNode> queue = new LinkedList<PTNode>();
		queue.add(root);
		boolean result = true;
		boolean hasChild = true; 
		while(!queue.isEmpty()) {
			PTNode currentNode = queue.remove();
			if(!hasChild) {//没有叶子节点
				if(null != currentNode.LeftChild || null != currentNode.RightChild) {
					result = false;
					break;
				}
			}else {//有叶子节点
				if(null != currentNode.LeftChild && null != currentNode.RightChild) {
					queue.add(currentNode.LeftChild);
					queue.add(currentNode.RightChild);
				}else if(null != currentNode.LeftChild && null == currentNode.RightChild) {
					queue.add(currentNode.LeftChild);
					hasChild = false;
				}else if(null == currentNode.LeftChild && null != currentNode.RightChild) {
					result = false;
					break;
				}else {
					hasChild = false;
				}
			}
		}
		return result;
	}

八判断两个二叉树是否相等

boolean isSameTree(PTNode t1,PTNode t2) {
		if(null == t1 && null == t2) {
			return true;
		}else if(null == t1 || null == t2) {
			return false;
		}
		if(t1.data != t2.data) {
			return false;
		}
		return isSameTree(t1.LeftChild,t2.LeftChild)&&isSameTree(t1.RightChild,t2.RightChild);
	}

九判断两个二叉树是否为镜像

boolean isMirrorTree(PTNode t1,PTNode t2) {
		if(null == t1 && null == t2) {
			return true;
		}else if(null == t1 || null == t2) {
			return false;
		}
		if(t1.data != t2.data) {
			return false;
		}
		return isMirrorTree(t1.LeftChild,t2.RightChild)&&isMirrorTree(t1.RightChild,t2.LeftChild);
	}

十翻转二叉树（镜像二叉树）

PTNode mirrorTree(PTNode root) {
		if(null == root) {
			return null;
		}
		PTNode left = mirrorTree(root.LeftChild);
		PTNode right = mirrorTree(root.RightChild);
		root.LeftChild = left;
		root.RightChild = right;
		return root;
	}

十一二叉树的前序遍历

void PreOrderTraverse(PTNode root,ArrayList<Integer> result) {
		if(null == root) {
			return ;
		}
		result.add(root.data);
		System.out.print(root.data + " ");
		PreOrderTraverse(root.LeftChild,result);
		PreOrderTraverse(root.RightChild,result);
	}

十二二叉树的中序遍历

void InOrderTraverse(PTNode root,ArrayList<Integer> result) {
		if(null == root) {
			return ;
		}		
		InOrderTraverse(root.LeftChild,result);
		result.add(root.data);
		System.out.print(root.data + " ");
		InOrderTraverse(root.RightChild,result);
	}

十三二叉树的后序遍历

void PostOrderTraverse(PTNode root,ArrayList<Integer> result) {
		if(null == root) {
			return ;
		}		
		PostOrderTraverse(root.LeftChild,result);
		PostOrderTraverse(root.RightChild,result);
		result.add(root.data);
		System.out.print(root.data + " ");
	}

十四二叉树的层次遍历

先将根节点入队，当前节点是队头节点，将其出队并访问，如果当前节点的左节点不为空将左节点入队，如果当前节点的右节点不为空将其入队。所以出队顺序也是从左到右依次出队。

ArrayList<ArrayList<Integer>> levelOrderTree(PTNode root) {
		ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		if(null == root) {
			return result;
		}
		Queue<PTNode> queue = new LinkedList<PTNode>();
		PTNode current = null;
		queue.offer(root);
		while(!queue.isEmpty()) {
			int size = queue.size();
			ArrayList<Integer> arr = new ArrayList<Integer>();
			for(int i=0;i<size;i++) {
				current = queue.poll();
				arr.add(current.data);
				if(current.LeftChild != null) {
					queue.offer(current.LeftChild);
				}
				if(current.RightChild != null) {
					queue.offer(current.RightChild);
				}
			}			
			result.add(arr);
		}
		return result;
	}

十五判断二叉树是否是合法的二叉查找树（BST）

一棵BST定义为：
* 节点的左子树中的值要严格小于该节点的值。
* 节点的右子树中的值要严格大于该节点的值。
* 左右子树也必须是二叉查找树。

* 一个节点的树也是二叉查找树。

boolean isValidBST(PTNode root,long minVal,long maxVal) {
		if(null == root) {
			return true;
		}
		if(root.data >= maxVal || root.data <=minVal) {
			return false;
		}
		
		return isValidBST(root.LeftChild,minVal,root.data)&&isValidBST(root.RightChild,root.data,maxVal);		
	}

十六创建二叉树

* 已知前序遍历和中序遍历可以唯一确定一颗二叉树
* 已知后序遍历和中序遍历可以唯一确定一颗二叉树

* 已知中序遍历和后序遍历不能唯一确定一颗二叉树

void createBinaryTree(int[] datas,List<PTNode>nodelist) {
		for(int nodeindex=0;nodeindex<datas.length;nodeindex++) {
			PTNode node = new PTNode(datas[nodeindex]);
			nodelist.add(node);
		}
		
		for(int index=0;index<nodelist.size()/2-1;index++) {
			//编号为n的节点他的左子节点编号为2*n 右子节点编号为2*n+1 但是因为list从0开始编号
			nodelist.get(index).setLeftChild(nodelist.get(index*2+1));
			nodelist.get(index).setRightChild(nodelist.get(index*2+2));
		}
		
		int index = nodelist.size()/2-1;
		nodelist.get(index).setLeftChild(nodelist.get(index*2+1));
		
		if(nodelist.size()%2 == 1) {
			nodelist.get(index).setRightChild(nodelist.get(index*2+2));
		}
	}

参考博客：https://www.jianshu.com/p/0190985635eb

秒客网

二叉树基本操作的实现（java）

相关文章