赞
踩
树是一种非线性的数据结构,由n(n>=0)个有限节点组成一个具有层次关系的集合
特点:
有一个特殊的节点,称为根节点,根节点没有前驱节点
树是递归定义的
树形结构中,子树之间不能有交集,否则就不是树形结构
除了根节点外,每个节点有且仅有一个父节点
一棵 N 个节点的树有 N-1 条边
节点的度:一个节点含有子树的个数称为该节点的度,上图A的度为6
树的度:一棵树中,所有节点度的最大值称为树的度,上图树的度为6
叶子节点或终端节点:度为0的节点称为叶子节点,上图B、C、H、I、...等节点为叶子节点
双亲节点或父节点:若一个 节点含有子节点,则这个节点称为其子节点的父节点,上图A是B的父节点
孩子节点或子节点:一个节点含有的子树的根节点称为该节点的子节点,上图B是A的孩子节点
根节点:一棵树中,没有双亲节点的节点,上图A为根节点
节点的层次:从根节点开始,根为第一层,根的子节点为第二层,以此类推
树的高度和深度:数值相同,高度从下往上数,深度从上往下数,上图高度为4
一棵二叉树是节点的一个有限集合,该集合:或者为空;或者由一个根节点加上两棵别称为左子树和右子树的二叉树组成
性质:
二叉树不存在度大于2的节点
二叉树的子树有左右之分,次序不能颠倒,因此二叉树是有序树
1. 满二叉树:一棵二叉树,如果每层的节点数都达到最大值,则这棵二叉树就是满二叉树,即:如果一棵二叉树的层数为K,且节点总数是,则它就是满二叉树
2. 完全二叉树:一棵深度为K的有n个结点的二叉树,对树中的结点按从上至下、从左到右的顺序进行编号,如果编号为i(1≤i≤n)的结点与满二叉树中编号为i的结点在二叉树中的位置相同,则这棵二叉树称为完全二叉树。满二叉树是一种特殊的完全二叉树
若i>0,双亲序号:(i-1)/2,i=0,i为根节点编号,无双亲节点
若2i+1<n,左孩子序号:2i+1,否则无左孩子
若2i+2<n,右孩子序号:2i+2,否则无右孩子
例题:
1. 某二叉树共有 399 个结点,其中有 199 个度为 2 的结点,则该二叉树中的叶子结点数为( )
A 不存在这样的二叉树 B 200 C 198 D 199
解析:n0 = n2+1,选B
2.在具有 2n 个结点的完全二叉树中,叶子结点个数为( )
A n B n+1 C n-1 D n/2
解析:
3.一个具有767个节点的完全二叉树,其叶子节点个数为()
A 383 B 384 C 385 D 386
解析:
该题为奇数个节点,根据上题中公式:767 = 2n0 - 1,n0 = 384,选B
4.一棵完全二叉树的节点数为531个,那么这棵树的高度为( )
A 11 B 10 C 8 D 12
解析:根据公式:高度 =
二叉树的存储结构分为:顺序存储和类似于链表的链式存储
这里介绍链式存储
二叉树的链式存储是通过一个一个的节点引用起来的,常见的表示方法有二叉和三叉的表示方式,如下:
- // 孩子表示法
- class Node {
- int val; // 数据域
- Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
- Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
- }
-
- // 孩子双亲表示法
- class Node {
- int val; // 数据域
- Node left; // 左孩子的引用,常常代表左孩子为根的整棵左子树
- Node right; // 右孩子的引用,常常代表右孩子为根的整棵右子树
- Node parent; // 当前节点的根节点
- }
本文采用孩子表示法来构建二叉树
假设N代表根节点,L代表根节点的左子树,R代表根节点的右子树,根据遍历根节点的先后次序有以下遍历方式:
- // 前序遍历
- void preOrder(Node root);
-
- // 中序遍历
- void inOrder(Node root);
-
- // 后序遍历
- void postOrder(Node root);
设二叉树的根节点所在层数为1,层序遍历就是从所在二叉树的根节点出发,首先访问第一层的树根节点,然后从左至右访问第二层的节点,然后第三层的节点,以此类推,自上而下,自左至右逐层访问树的节点的过程就是层序遍历
1.某完全二叉树按层次输出(同一层从左到右)的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA
解析:
2.二叉树的先序遍历和中序遍历如下:先序遍历:EFHIGJK;中序遍历:HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H
解析:A
3.设一课二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde
答案:D
4.某二叉树的后序遍历序列与中序遍历序列相同,均为 ABCDEF ,则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF
答案:A
穷举法创建一个二叉树,便于理解,并不是真正创建二叉树的方式
- public class TestBinaryTree {
- static class TreeNode {
- public char val;
- public TreeNode left;//左孩子的引用
- public TreeNode right;//右孩子的引用
-
- public TreeNode(char data) {
- this.data = data;
- }
- }
-
- public TreeNode createTree() {
- TreeNode A = new TreeNode('A');
- TreeNode B = new TreeNode('B');
- TreeNode C = new TreeNode('C');
- TreeNode D = new TreeNode('D');
- TreeNode E = new TreeNode('E');
- TreeNode F = new TreeNode('F');
- TreeNode G = new TreeNode('G');
- TreeNode H = new TreeNode('H');
-
- A.left = B;
- A.right = C;
- B.left = D;
- B.right = E;
- C.left = F;
- C.right = G;
- E.right = H;
-
- return A;//根节点
- }
- }
该树图形:
操作实现:
- //前序遍历
- public void perOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- System.out.print(root.val + " ");
- //遍历左子树
- perOrder(root.left);
- //遍历右子树
- perOrder(root.right);
- }
-
- //中序遍历
- public void inOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- inOrder(root.left);
- System.out.print(root.val + " ");
- inOrder(root.right);
- }
-
- //后序遍历
- public void postOrder(TreeNode root) {
- if(root == null) {
- return;
- }
- postOrder(root.left);
- postOrder(root.right);
- System.out.print(root.val + " ");
- }
- public int size(TreeNode root) {
- if(root == null) {
- return 0;
- }
- return size(root.left) + size(root.right) +1;
- }
- public int getLeafNodeCount(TreeNode root) {
- if(root == null) {
- return 0;
- }
- if(root.left == null && root.right == null) {
- return 1;
- }
- return getLeafNodeCount(root.left) + getLeafNodeCount(root.right);
- }
- public int getKLevelNodeCount(TreeNode root,int k) {
- if(root == null) {
- return 0;
- }
- if(k == 1) {
- return 1;
- }
- return getKLevelNodeCount(root.left,k-1) +
- getKLevelNodeCount(root.right,k-1);
- }
- public int getHeight(TreeNode root) {
- if(root == null) {
- return 0;
- }
- int leftHigh = getHeight(root.left);
- int rightHigh = getHeight(root.right);
-
- return leftHigh > rightHigh ? leftHigh+1 : rightHigh+1;
- /*不推荐这种写法,重复计算太多,时间复杂度太大
- return getHeight(root.left) > getHeight(root.right) ?
- getHeight(root.left)+1:getHeight(root.right)+1;*/
- }
- public TreeNode find(TreeNode root, int val) {
- if(root == null) {
- return null;
- }
- if(root.val == val) {
- return root;
- }
- //遍历左子树
- TreeNode ret = find(root.left,val);
- if(ret != null) {
- return ret;
- }
- //遍历右子树
- ret = find(root.right,val);
- if(ret != null) {
- return ret;
- }
- return null;
- }
- class Solution {
- public boolean isSameTree(TreeNode p, TreeNode q) {
- //1.判断两树结构不同,一个为空,一个不为空
- if(p == null & q != null || p != null && q == null) {
- return false;
- }
- //2.第一步走完,两树要么都为空,要么都不为空
- if(p == null && q == null) {
- return true;
- }
- //3.走完第二步,两树都不为空,判断值是否相同
- //这里的判断条件一定是 不等于 ,否则将不会进入递归!!!
- if(p.val != q.val) {
- return false;
- }
- return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
- }
- }
- //O(N)
- //用到上个题的判断两树是否相同
- class Solution {
- public boolean isSubtree(TreeNode root, TreeNode subRoot) {
- //若root为空,或者递归到了最底层节点的左右空子树都没有和subRoot匹配上,false
- if(root == null) {
- return false;
- }
- //使用isSameTree函数判断当前两个树是否相同
- if(isSameTree(root,subRoot)) {
- return true;
- }
- //递归调用判断root树的左子树是否与subRoot相同
- if(isSubtree(root.left,subRoot)) {
- return true;
- }
- //递归调用判断root树的右子树是否与subRoot相同
- if(isSubtree(root.right,subRoot)) {
- return true;
- }
- return false;
- }
- public boolean isSameTree(TreeNode p, TreeNode q) {
- //1.判断两树结构不同,一个为空,一个不为空
- if(p == null & q != null || p != null && q == null) {
- return false;
- }
- //2.第一步走完,两树要么都为空,要么都不为空
- if(p == null && q == null) {
- return true;
- }
- //3.走完第二步,两树都不为空,判断值是否相同
- //这里的判断条件一定是 不等于 ,否则将不会进入递归!!!
- if(p.val != q.val) {
- return false;
- }
- return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
- }
- }
- class Solution {
- public TreeNode invertTree(TreeNode root) {
- if(root == null) {
- return null;
- }
-
- //减少一些不必要的递归和交换次数
- if(root.left == null && root.right == null) {
- return root;
- }
-
- TreeNode ret = root.left;
- root.left = root.right;
- root.right = ret;
-
- invertTree(root.left);
- invertTree(root.right);
-
- return root;
- }
- }
- class Solution {
- public int maxDepth(TreeNode root) {
- if(root == null) {
- return 0;
- }
- int leftHigh = maxDepth(root.left);
- int rightHigh = maxDepth(root.right);
-
- return Math.max(leftHigh,rightHigh)+1;
- }
- }
平衡二叉树 是指该树所有节点的左右子树的深度相差不超过 1。
- class Solution {
-
- public boolean isBalanced(TreeNode root) {
- if(root == null) {
- return true;
- }
- int leftHigh = maxDepth(root.left);
- int rightHigh = maxDepth(root.right);
-
- //要判断是否为平衡树,需满足三个条件
- //1.当前root的左子树和右子树的高度差 <= 1
- //2.root的左子树平衡
- //3.root的右子树平衡
- return Math.abs(leftHigh - rightHigh) <= 1
- && isBalanced(root.left)
- && isBalanced(root.right);
- }
-
- //求树的深度
- public int maxDepth(TreeNode root) {
- if(root == null) {
- return 0;
- }
- int leftHigh = maxDepth(root.left);
- int rightHigh = maxDepth(root.right);
-
- return leftHigh > rightHigh ? leftHigh+1 : rightHigh+1;
- }
- }
解析:
上述代码的时间复杂度为,有大量重复计算,下面进行优化
以 O(N) 实现:
- class Solution {
-
- public boolean isBalanced(TreeNode root) {
- if(root == null) return true;
-
- //若是返回一个小于1的值,说明该树不平衡
- return maxDepth(root) >= 1;
- }
-
- //求树的深度
- public int maxDepth(TreeNode root) {
- if(root == null) {
- return 0;
- }
- //判断左子树深度,当接收到的值为负数时,说明该树不平衡,返回-1,不再继续递归
- int leftHigh = maxDepth(root.left);
- if(leftHigh < 0) {
- return -1;
- }
- //判断右子树深度
- int rightHigh = maxDepth(root.right);
- if(rightHigh < 0) {
- return -1;
- }
-
- //当左子树深度-右子树深度的绝对值,小于等于1,说明该树平衡,返回左右子树深度中的最大值+1
- //若差值大于1,说明不是平衡树,返回-1
- if(Math.abs(leftHigh - rightHigh) <= 1) {
- return Math.max(leftHigh,rightHigh)+1;
- }else {
- return -1;
- }
- }
- }
- class Solution {
- public boolean isSymmetric(TreeNode root) {
- if(root == null) return true;
- return isSameTree(root.left,root.right) && isSameTree(root.right,root.left);
- }
- public boolean isSameTree(TreeNode p, TreeNode q) {
- //1.判断两树结构不同,一个为空,一个不为空
- if(p == null & q != null || p != null && q == null) {
- return false;
- }
- //2.第一步走完,两树要么都为空,要么都不为空
- if(p == null && q == null) {
- return true;
- }
- //3.走完第二步,两树都不为空,判断值是否相同
- //这里的判断条件一定是 不等于 ,否则将不会进入递归!!!
- if(p.val != q.val) {
- return false;
- }
- return isSameTree(p.left,q.right) && isSameTree(p.right,q.left);
- }
- }
- import java.util.Scanner;
-
- class TreeNode {
- public char val;
- public TreeNode left;
- public TreeNode right;
-
- public TreeNode(char val) {
- this.val = val;
- }
- }
-
- public class Main {
- public static int i = 0;
- public static TreeNode cretateTree(String str) {
- TreeNode root = null;
- if(str.charAt(i) != '#') {
- root = new TreeNode(str.charAt(i));
- i++;
- root.left = cretateTree(str);
- root.right = cretateTree(str);
- }else {
- i++;
- }
- return root;
- }
- public static void inorder(TreeNode root) {
- if(root == null) {
- return;
- }
- inorder(root.left);
- System.out.print(root.val + " ");
- inorder(root.right);
-
- }
- public static void main(String[] args) {
- Scanner in = new Scanner(System.in);
- // 注意 hasNext 和 hasNextLine 的区别
- while (in.hasNextLine()) { // 注意 while 处理多个 case
- String str = in.nextLine();
- TreeNode root = cretateTree(str);
- inorder(root);
- }
- }
- }
循环实现:
- public void levelOrder(TreeNode root) {
- Queue<TreeNode> queue = new LinkedList<>();
- if(root == null) {
- return;
- }
- queue.offer(root);//将根节点放入队列
- while(!queue.isEmpty()) {//当队列不为空进入循环
- TreeNode cur = queue.poll();//cur获取队列队首节点
- System.out.print(cur.val + " ");//打印cur存储节点的值
- if(cur.left != null) {//当cur存储节点的左子树不为空,将左子树节点添加到队列中
- queue.offer(cur.left);
- }
- if(cur.right != null) {
- queue.offer(cur.right);
- }
- }
- System.out.println();
- }
二维表实现
用size来计算每层元素个数
- class Solution {
- public List<List<Integer>> levelOrder(TreeNode root) {
- List<List<Integer>> ret = new ArrayList<>();
- if(root == null) {
- return ret;
- }
- Queue<TreeNode> queue = new LinkedList<>();
- queue.offer(root);
- while(!queue.isEmpty()) {
- int size = queue.size();//计算树每层元素个数
- List<Integer> list = new ArrayList<>();//生成每层
- while(size > 0) {
- TreeNode cur = queue.poll();
- list.add(cur.val);//将val放入List<Integer>
- if(cur.left != null) {
- queue.offer(cur.left);
- }
- if(cur.right != null) {
- queue.offer(cur.right);
- }
- size--;
- }
- ret.add(list);//将List<Integer>放入List<List<Integer>>
- }
- return ret;
- }
- }
层序遍历变种OJ题:二叉树的右视图
- public boolean isCompleteTree(TreeNode root) {
- Queue<TreeNode> queue = new LinkedList<>();
- if(root == null) return true;
- queue.offer(root);
-
- while (!queue.isEmpty()) {
- TreeNode cur = queue.poll();
- if(cur == null) {
- break;
- }
- queue.offer(cur.left);
- queue.offer(cur.right);
- }
- while (!queue.isEmpty()) {
- TreeNode node = queue.poll();
- if(node != null) {
- return false;
- }
- }
- return true;
- }
- class Solution {
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root == null) {
- return null;
- }
- if(root == p || root == q) {
- return root;
- }
-
- TreeNode leftTree = lowestCommonAncestor(root.left,p,q);
- TreeNode rightTree = lowestCommonAncestor(root.right,p,q);
-
- if(leftTree != null && rightTree != null) {
- return root;
- }else if(leftTree != null) {
- return leftTree;
- }else {
- return rightTree;
- }
- }
- }
另一种思路
-
- class Solution {
- public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
- if(root == null) {
- return root;
- }
-
- //1.把root节点到指定节点之间的所有节点入栈
- Stack<TreeNode> stackP = new Stack<>();
- pushElement(root,p,stackP);
-
- Stack<TreeNode> stackQ = new Stack<>();
- pushElement(root,q,stackQ);
-
- //2.使两栈中元素个数相等
- int sizeP = stackP.size();
- int sizeQ = stackQ.size();
-
- if(sizeP > sizeQ) {
- int size = sizeP - sizeQ;
- while(size != 0) {
- stackP.pop();
- size--;
- }
- }else {
- int size = sizeQ - sizeP;
- while(size != 0) {
- stackQ.pop();
- size--;
- }
- }
-
- //3.让两栈中元素同时出栈对比,若相同即为公共祖先
- while(!stackP.empty() && !stackQ.empty()) {
- if(stackP.peek() == stackQ.peek()) {
- return stackP.peek();
- }else {
- stackP.pop();
- stackQ.pop();
- }
- }
- return null;
- }
-
- //把root节点到指定节点之间的所有节点入栈
- public boolean pushElement(TreeNode root, TreeNode node, Stack<TreeNode> stack) {
- if(root == null) {
- return false;
- }
- stack.push(root);
- if(root == node) {
- return true;
- }
- boolean flg = pushElement(root.left,node,stack);
- if(flg) {
- return true;
- }
- boolean flg2 = pushElement(root.right,node,stack);
- if(flg2) {
- return true;
- }
- stack.pop();
- return false;
- }
- }
- public void perOrderNonRecursive(TreeNode root) {
- Stack<TreeNode> stack = new Stack<>();
- TreeNode cur = root;
-
- while (cur != null || !stack.isEmpty()) {
- while (cur != null) {
- stack.push(cur);
- System.out.print(cur.val + " ");
- cur = cur.left;
- }
- TreeNode top = stack.pop();
- cur = top.right;
- }
- }
- public void inOrderNonRecursive(TreeNode root) {
- Stack<TreeNode> stack = new Stack<>();
- TreeNode cur = root;
-
- while (cur != null || !stack.isEmpty()) {
- while (cur != null) {
- stack.push(cur);
- cur = cur.left;
- }
- TreeNode top = stack.pop();
- System.out.print(top.val + " ");
- cur = top.right;
- }
- }
- public void postOrderNonRecursive(TreeNode root) {
- Stack<TreeNode> stack = new Stack<>();
- TreeNode cur = root;
- TreeNode prev = null;
- while(cur != null || !stack.isEmpty()) {
- while(cur != null) {
- stack.push(cur);
- cur = cur.left;
- }
- TreeNode top = stack.peek();
- if(top.right == null || top.right == prev) {
- //打印当前top,并弹出
- stack.pop();
- System.out.print(top.val + " ");
- prev = top;
- }else {
- cur = top.right;
- }
- }
- }
- class Solution {
-
- public int preIndex;
-
- public TreeNode buildTree(int[] preorder, int[] inorder) {
- return bulidTreeChilder(preorder,inorder,0,inorder.length-1);
- }
-
- private TreeNode bulidTreeChilder(int[] preorder,int[] inorder,int inBegin,int inEnd) {
- if(inBegin > inEnd) {
- return null;
- }
- TreeNode root = new TreeNode(preorder[preIndex]);
-
- int rootIndex = findRootIndex(inorder,inBegin,inEnd,preorder[preIndex]);
-
- preIndex++;
-
- root.left = bulidTreeChilder(preorder,inorder,inBegin,rootIndex-1);
- root.right = bulidTreeChilder(preorder,inorder,rootIndex+1,inEnd);
-
- return root;
- }
-
- private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
- for(int i = inBegin;i <= inEnd;i++) {
- if(inorder[i] == key) {
- return i;
- }
- }
- return -1;
- }
- }
- class Solution {
-
- public int postIndex = 0;
-
- public TreeNode buildTree(int[] inorder, int[] postorder) {
- postIndex = postorder.length-1;
- return buildTreeChild(inorder,postorder,0,inorder.length-1);
- }
-
- private TreeNode buildTreeChild(int[] inorder,int[] postorder,int inBegin,int inEnd) {
- if(inBegin > inEnd) {
- return null;
- }
- TreeNode root = new TreeNode(postorder[postIndex]);
-
- int rootIndex = findRootIndex(inorder,inBegin,inEnd,postorder[postIndex]);
-
- postIndex--;
-
- root.right = buildTreeChild(inorder,postorder,rootIndex+1,inEnd);
- root.left = buildTreeChild(inorder,postorder,inBegin,rootIndex-1);
-
- return root;
- }
-
- private int findRootIndex(int[] inorder,int inBegin,int inEnd,int key) {
- for(int i = inBegin; i <= inEnd;i++) {
- if(inorder[i] == key) {
- return i;
- }
- }
- return -1;
- }
- }
- class Solution {
- public String tree2str(TreeNode root) {
- StringBuilder stringBuilder = new StringBuilder();
- tree2strChild(root,stringBuilder);
- return stringBuilder.toString();
- }
- private void tree2strChild(TreeNode root,StringBuilder stringBuilder) {
- if(root == null) return;
- stringBuilder.append(root.val);
- if(root.left != null) {
- stringBuilder.append("(");
- tree2strChild(root.left,stringBuilder);
- stringBuilder.append(")");
- }else {
- //左边为空,右边也为空
- if(root.right == null) {
- return;
- }else {
- stringBuilder.append("()");
- }
- }
- //处理root右子树的情况
- if(root.right == null) {
- return;
- }else {
- stringBuilder.append("(");
- tree2strChild(root.right,stringBuilder);
- stringBuilder.append(")");
- }
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。