如何建立的网站能争钱,58同城最新消息招聘,在线教学网站开发,六安论坛六安杂谈本文旨作于收集整理使用#xff01;#xff01;导航一、树树(Tree)是n(n≥0)个结点的有限集#xff0c;n0称之为空树。在非空树种#xff1a;当有且仅有一个特定的称为根(Root)的结点#xff1b; 其余结点可以划分为m(m#xff1e;0)个互不相交的有限集T1、T2 、…、Tm导航一、树树(Tree)是n(n≥0)个结点的有限集n0称之为空树。在非空树种当有且仅有一个特定的称为根(Root)的结点 其余结点可以划分为m(m0)个互不相交的有限集T1、T2 、…、Tm每个集Ti(1≤i≤m)均为树且称为树的子树(SubTree) 如下图所示。根节点根节点指没有双亲结点的结点一棵树中最多有一个根节点(如A)叶子结点没有孩子结点的结点叫作叶子结点(如L、M、F)兄弟结点拥有相同双亲结点的所有孩子结点叫作兄弟结点(L、M是E的兄弟结点I、J、K是D的兄弟结点)结点的深度是指从根节点到该节点的路径长度(O点的深度为3A—C—G—O)树的高度是树中所有结点高度的最大值树的深度是树中所有结点深度的最大值对于同一棵树其深度和高度是相同的但是对于各个结点其深度和高度不一定相同二、二叉树二叉树(Binary Tree)是n(n0)个节点的有限集合该集合或为空集或为由一个根节点和两颗互不相交的分别称为根节点的左子树和右子树的二叉树组成。二叉树所有节点只有左子树的二叉树称为左斜树只有右子树的二叉树称为右斜树。所有节点均含左子树和右子树这样的二叉树称为满二叉树。满二叉树完全二叉树若设二叉树的深度为h除第 h 层外其它各层 (1h-1) 的结点数都达到最大个数第 h 层所有的结点都连续集中在最左边这就是完全二叉树。完全二叉树二叉树的应用编译器中的表达式树、用于数据压缩算法中的赫夫曼编码树、支持在集合中查找、插入和删除其平均时间复杂度为O(lognn)的二叉搜索树(BST)、优先队列(PQ)它支持以对数时间(最坏情况下)对集合中的最小(或最大)数据元素进行搜索和删除1、二叉树的存储结构基本了解了二叉树的组成后我们学习怎么样去存储二叉树了解二叉树的存储结构。1.1、满二叉树存储满二叉树可以使用数组我们将上图中的满二叉树存储为数组为[A,B,C,D,E,F,G]),当然我们通过数组复原二叉树时也可以按照顺序复原二叉树。1.2、完全二叉树完全二叉树和满二叉树的存储方法相同上图中的完全二叉树转换为数组([A,B,C,D,E,F,G,H,I])(图中最后的H为I)。1.2、其他二叉树有的二叉树既不是满二叉树又不是完全二叉树该如何存储我们可以将缺少的二叉树的叶子节点用一些特殊的符号存储将其转换为完全二叉树如下图所示。则如上图中的二叉树转换为数组([A,B,C,D,E,F,G,#.#,H,#,#,#,I,J])2二叉树的遍历二叉树的遍历分为前序遍历、中序遍历和后序遍历3.1 前序遍历先遍历左子树再遍历右子树2.2、 中序遍历从根结点开始(注意并不是先访问根结点)中序遍历根结点的左子树然后是访问根结点最后中序遍历右子树2.3 后序遍历从左到右先叶子后结点的方式遍历访问左右子树最后是访问根结点3、实现二叉树如下需要构建如下二叉树并实现其三种遍历方法/*** 构造如下二叉树* A* B C* D E G**/import java.util.List;/*** 构造如下二叉树* A* B C* D E G*/public class BinaryTree {TreeNode root null;public BinaryTree() {root new TreeNode(0, A);}/*** 传统方法构造二叉树*/public void createBinaryTree() {TreeNode nodeB new TreeNode(2, B);TreeNode nodeC new TreeNode(3, C);TreeNode nodeD new TreeNode(4, D);TreeNode nodeE new TreeNode(5, E);TreeNode nodeF new TreeNode(6, F);root.leftChild nodeB;root.rightChild nodeC;nodeB.leftChild nodeD;nodeB.rightChild nodeE;nodeC.rightChild nodeF;}/*** 出入二叉树的数组创建二叉树** param size 二叉树所有节点的数量和* param datas 二叉树的List集合* return 返回创建的节点*/public TreeNode createBinerTree(int size, List datas) {TreeNode node null;if (datas.size() 0) {return null;}String data datas.get(0);if (#.equals(data)) {datas.remove(0);return node;}int index size - datas.size();node new TreeNode(index, data);if (index 0) {root node;}datas.remove(0);node.leftChild createBinerTree(size, datas);node.rightChild createBinerTree(size, datas);return node;}/*** 前序遍历*/public void preOrder(TreeNode node) {if (node null) {return;} else {System.out.println(preOrder data: node.getData());preOrder(node.leftChild);preOrder(node.rightChild);}}/*** 中序遍历*/public void midOrder(TreeNode node) {if (node null) {return;} else {midOrder(node.leftChild);System.out.println(midOrder data: node.getData());midOrder(node.rightChild);}}/*** 后序遍历*/public void postOrder(TreeNode node) {if (node null) {return;} else {preOrder(node.leftChild);preOrder(node.rightChild);System.out.println(postOrder data: node.getData());}}class TreeNode {private int index;private String data;private TreeNode leftChild;private TreeNode rightChild;public TreeNode(int index, String data) {this.index index;this.data data;}public TreeNode getLeftChild() {return leftChild;}public void setLeftChild(TreeNode leftChild) {this.leftChild leftChild;}public TreeNode getRightChild() {return rightChild;}public void setRightChild(TreeNode rightChild) {this.rightChild rightChild;}public int getIndex() {return index;}public void setIndex(int index) {this.index index;}public String getData() {return data;}public void setData(String data) {this.data data;}}}传入数组测试public class test {public static void main(String[] args) {BinaryTree binaryTreenew BinaryTree();String data[]{A,B,C,D,E,#,F};ArrayListdatasnew ArrayList(Arrays.asList(data));binaryTree.createBinerTree(datas.size(), datas);binaryTree.preOrder(binaryTree.root);}}结果preOrder data:ApreOrder data:BpreOrder data:CpreOrder data:DpreOrder data:EpreOrder data:F三、搜索二叉树二叉查找树(又二叉搜索树二叉排序树)它或者是一棵空树或者是具有下列性质的二叉树 若它的左子树不空则左子树上所有结点的值均小于它的根结点的值 若它的右子树不空则右子树上所有结点的值均大于它的根结点的值 它的左、右子树也分别为二叉排序树。二叉排序树的查找过程和次优二叉树类似通常采取二叉链表作为二叉排序树的存储结构中序遍历二叉排序树可得到一个关键字的有序序列一个无序序列可以通过构造一棵二叉排序树变成一个有序序列构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点在进行插入操作时不必移动其它结点只需改动某个结点的指针由空变为非空即可1、搜索二叉树的实现/*** Author: Active_Loser* Date: 2018/7/30 23:17* Content: 实现搜索二叉树的建立、添加、删除等操作*/public class SearchBinryTree {public TreeNode root;public TreeNode put(int data) {TreeNode node;TreeNode parent null;if (root null) {node new TreeNode(data);root node;return node;}node root;while (node ! null) {parent node;if (data parent.data) {node parent.rightChild;} else if (data parent.data) {node parent.leftChild;} else {return node;}}node new TreeNode(data);if (data parent.data) {parent.leftChild node;node.parent parent;} else if (data parent.data) {parent.rightChild node;node.parent parent;}return node;}public TreeNode search(int value) {TreeNode node root;while (node ! null node.data ! value) {if (node.data value) {node node.rightChild;} else if (node.data value) {node node.leftChild;}}return node;}/*** param value 删除的数值* return 返回删除的节点*/public TreeNode delete(int value) {//判断是否包含需要删除的数TreeNode deleteNode search(value);if (null deleteNode) {return null;}else {delete(deleteNode);}}private void delete(TreeNode node) {if (nodenull){return null;}TreeNode parentnode.parent;//做节点与有节点皆为NULLif (node.leftChildnullnode.rightChildnull){if (parent.leftChildnode){parent.leftChildnull;}else {parent.rightChildnull;}return;}//有左节点没有右节点1.父节点的左节点2.父节点的右节点if (node.leftChild!nullnode.rightChildnull){if (parent.leftChildnode){parent.leftChildnode.leftChild;}else if (parent.rightChildnode){parent.rightChildnode.leftChild;}return;}//有右节点没有左节点1.父节点的左节点2.父节点的右节点if (node.leftChild!nullnode.rightChildnull){if (parent.leftChildnode){parent.leftChildnode.rightChild;}else if (parent.rightChildnode){parent.rightChildnode.rightChild;}return;}//既有左节点也有右节点//获取删除节点的后继节点TreeNode nextgetNextNode(node);delete(next);node.datanext.data;}private TreeNode getNextNode(TreeNode node) {if (nodenull){return null;}else {if (node.rightChild!null){return getMinTreeNode(node.rightChild);}else {TreeNode parentnode.parent;while (parent!nullnodeparent.rightChild){nodeparent;parentparent.parent;}return parent;}}return null;}//右子树最小值左子树最大值public TreeNode getMinTreeNode(TreeNode node){if (nodenull){return null;}else {while (node.leftChild !null){nodenode.leftChild;}}return node;}public void midOrder(TreeNode node) {if (node null) {return;} else {midOrder(node.leftChild);System.out.println(midOrder: node.data);midOrder(node.rightChild);}}class TreeNode {private TreeNode leftChild;private TreeNode rightChild;private TreeNode parent;private int data;public TreeNode(int data) {this.data data;}public TreeNode getLeftChild() {return leftChild;}public void setLeftChild(TreeNode leftChild) {this.leftChild leftChild;}public TreeNode getRightChild() {return rightChild;}public void setRightChild(TreeNode rightChild) {this.rightChild rightChild;}public TreeNode getParent() {return parent;}public void setParent(TreeNode parent) {this.parent parent;}public int getData() {return data;}public void setData(int data) {this.data data;}}}
