1.树结构1.数组和链表数组结构数组存储通过下标访问元素，查询速度快。如果数组元素是有序的，也可以使用二分法搜索提高检索速度；添加新元素可能会导致多个下标移动，效率低下；链表结构链表存储元素，增删元素效率高，但遍历元素每次都需要从起始节点开始，效率特别低；树形结构可以同时相对提高数据存储和读取的效率。2、树结构概念根节点：树的根，没有父节点的节点，如上图中的节点A；兄弟节点：具有相同父节点的子节点。图中B、C点；叶节点：没有子节点的节点。DEFG节点如图；treeheight：最大层数，如图为3层；path：查找从根节点到指定节点的路由；树结构是一层嵌套结构。树结构的外层和内层具有相似的结构，因此可以递归地表示这种结构。经典数据结构中的各种树状图都是典型的树结构：一棵树可以简单表示为根、左子树、右子树。左子树和右子树有自己的子树。2、二叉树模型树的种类很多。二叉树（BinaryTree）是一种重要的树结构。每个节点最多只能有两个子节点的形式称为二叉树。二叉树的子节点分为左节点和右节点，从许多实际问题中抽象出来的数据结构往往是二叉树的形式。完全二叉树的所有叶子节点都在最后一层或倒数第二层，最后一层的叶子节点在左边是连续的，倒数第二层的叶子节点是右侧连续。我们称它为满二叉树的完全二叉树。当一棵二叉树的所有叶子节点都在最后一层，且节点总数=2^n-1，n为层数时，称为满二叉树。平衡二叉树平衡二叉树是指任意节点的子树之间的高度差的绝对值小于等于1，左右子树都是平衡二叉树。常见的符合平衡树的有B树（多路平衡搜索树）、AVL树（二叉平衡搜索树）等。二叉搜索树（BinarySearchTree）不仅是二叉树，还满足一个一定顺序：一个节点的左子节点比自己小，右子节点比自己大。三、二叉树编码1、基本代码节点代码}树结构代码classBinaryTree01{privateTreeNoderoot;}2。遍历和搜索Preordertraversalsearch先处理当前节点的数据，然后递归依次遍历左子树和右子树；publicvoidprevTraverse(){//输出父节点System.out.println(this);//递归前序遍历到左子树if(this.leftNode!=null){this.leftNode.prevTraverse();}//递归前序遍历右子树if(this.rightNode!=null){this.rightNode.prevTraverse();}}publicTreeNodeprevSearch(Stringnum){//比较当前节点if(this.num.equals(num)){returnthis;}//递归遍历左子树找到TreeNodefindNode=null;if(this.leftNode!=null){findNode=this.leftNode.prevSearch(num);}//左子树遍历命中if(findNode!=null){returnfindNode;}//递归遍历右子树Findif(this.rightNode!=null){findNode=this.rightNode.prevSearch(num);}returnfindNode;}中序遍历搜索先递归遍历左子树，然后处理父节点，然后递归遍历右子树publicvoidmidTraverse(){//左子树递归中序遍历if(this.leftNode!=null){this.leftNode.midTraverse();}//输出parentnodeSystem.out.println(this);//右子树递归中序遍历if(this.rightNode!=null){this.rightNode.midTraverse();}}publicTreeNodemidSearch(Stringnum){//递归遍历左子树寻找TreeNodefindNode=null;if(this.leftNode!=null){findNode=this.leftNode.midSearch(num);}if(findNode!=null){returnfindNode;}//比较当前节点if(this.num.equals(num)){returnthis;}//递归遍历右边子树搜索if(this.rightNode!=null){findNode=this.rightNode.midSearch(num);}returnfindNode;}后序遍历搜索先递归遍历左子树，再递归遍历右子树，最后处理父节点；publicvoidlastTraverse(){//递归后序遍历到左子树if(this.leftNode!=null){this.leftNode.lastTraverse();}//递归后序遍历到右子树if(this.rightNode!=null){this.rightNode.lastTraverse();}//输出父节点System.out.println(this);}publicTreeNodelastSearch(Stringnum){//递归遍历左子树寻找TreeNodefindNode=null;if(this.leftNode!=null){findNode=this.leftNode.lastSearch(num);}if(findNode!=null){returnfindNode;}//递归遍历右子树寻找if(this.rightNode!=null){找到节点=这个。rightNode.lastSearch(num);}if(findNode!=null){returnfindNode;}//比较当前节点if(this.num.equals(num)){returnthis;}returnnull;}3.删除节点如果是当前被删除的节点是叶子节点，可以直接删除该节点；如果删除如果节点是非叶子节点，则删除节点树publicvoiddeleteNode(Stringnum){//判断左节点是否删除if(this.leftNode!=null&&this.leftNode.num.equals(num)){this.左节点=空；返回；}//判断右节点是否删除if(this.rightNode!=null&&this.rightNode.num.equals(num)){this.rightNode=null;return;}//遍历左子树递归删除if(this.leftNode!=null){this.leftNode.deleteNode(num);}//遍历到右子树进行递归删除if(this.rightNode!=null){this.rightNode.deleteNode(num);}}四、more叉树多叉树是指一个父节点可以有多个子节点，但一个子节点仍然遵循一个父节点的规律。通常，二叉树的实际应用高度太高，可以使用多叉树来简化数据关系。描述。例如：Linux文件系统、组织结构关系、角色菜单权限管理系统等，通常都是基于多叉树来描述的。
