新手学做网站图纸,网盟推广的优势,个人怎么开通微信小程序,观光农业规划设计一、二叉树的链式存储
二叉树的存储分为顺序存储和链式存储
#xff08;本文主要讲解链式存储#xff09;
二叉树的链式存储是通过一个一个节点引用起来的#xff0c;常见的表示方式有二叉三叉 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用…一、二叉树的链式存储
二叉树的存储分为顺序存储和链式存储
本文主要讲解链式存储
二叉树的链式存储是通过一个一个节点引用起来的常见的表示方式有二叉三叉 // 孩子表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 } // 孩子双亲表示法 class Node { int val; // 数据域 Node left; // 左孩子的引用常常代表左孩子为根的整棵左子树 Node right; // 右孩子的引用常常代表右孩子为根的整棵右子树 Node parent; // 当前节点的根节点 } 孩子双亲表示法在后续介绍本文采用孩子表示法来构建二叉树 二、二叉树的遍历
前序遍历根 左 右
中序遍历左 根 右
后序遍历左 右 根
层序遍历从上到下 从左到右 依次遍历
所有的遍历都是沿着某条路线进行的 上图二叉树的各遍历分别是
前序A B D C E F
中序D B A E C F
后序D B E F C A
层序A B C D E F
例题
1.某完全二叉树按层次输出同一层从左到右的序列为 ABCDEFGH 。该完全二叉树的前序序列为()
A: ABDHECFG B: ABCDEFGH C: HDBEAFCG D: HDEBFGCA 题解 前序ABDHECFG 2.二叉树的前序遍历和中序遍历如下前序遍历EFHIGJK;中序遍历HFIEJKG.则二叉树根结点为()
A: E B: F C: G D: H 题解 后序遍历H I F K J G E 3.设一课二叉树的中序遍历序列badce后序遍历序列bdeca则二叉树前序遍历序列为()
A: adbce B: decab C: debac D: abcde 题解 前序遍历a b c d e 4.某二叉树的后序遍历序列与中序遍历序列相同均为 ABCDEF 则按层次输出(同一层从左到右)的序列为()
A: FEDCBA B: CBAFED C: DEFCBA D: ABCDEF 题解 根据前几道题目的方法能画出二叉树 层序遍历F E D C B A 注意根据前序和后序不能创建二叉树只能确定根的位置无法确定左右子树的位置
三、二叉树的基本操作与图解 public class MyBinaryTree {static class TreeNode{public char val;public TreeNode left;public TreeNode right;public TreeNode(char val){this.val val;}}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;//根节点}// 前序遍历void preOrder(TreeNode root){if(root null){return;}System.out.print(root.val );preOrder(root.left);preOrder(root.right);}//中序遍历void inOrder(TreeNode root){if(root null){return;}inOrder(root.left);System.out.print(root.val );inOrder(root.right);}//后序遍历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(rootnull){return 0;}int ret size(root.left)size(root.right)1;return ret;//子问题思路}public int nodeSize;public void size2(TreeNode root){if(rootnull){return ;}nodeSize;size2(root.left);size2(root.right);}//整棵树的叶子节点个数public int getLeafNodeCount(TreeNode root){if(rootnull){return 0;}//左子树的叶子节点右子树的叶子节点就是整棵树的叶子if(root.leftnullroot.rightnull){return 1;}return getLeafNodeCount(root.left)getLeafNodeCount(root.right);}//遍历思路public int leafSize;public void getLeafNodeCount2(TreeNode root){if(rootnull){return ;}//左子树的叶子节点右子树的叶子节点就是整棵树的叶子if(root.leftnullroot.rightnull){leafSize;}getLeafNodeCount2(root.left);getLeafNodeCount2(root.right);}// 获取第K层节点的个数int getKLevelNodeCount(TreeNode root,int k){if(rootnull){return 0;}if(k1){return 1;}return getKLevelNodeCount(root.left,k-1)getKLevelNodeCount(root.right,k-1);}// 获取二叉树的高度int getHeight(TreeNode root){if(rootnull){return 0;}//整棵树的高度左树高度和右树高度的最大值1int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);return leftHeight rightHeight ? leftHeight1 : rightHeight1;}// 检测值为value的元素是否存在TreeNode find(TreeNode root, int val){if(rootnull){return null;}if(root.valval){return root;}TreeNode ret find(root.left,val);if(ret !null){return root;}ret find(root.right,val);if(ret !null){return root;}return null;}
}递归遍历代码讲解以前序遍历为例 求节点个数代码图解 获取k层节点的个数图解 获取二叉树的高度图解 检测为value的值是否存在图解
