最近国内外重大新闻事件,南昌seo推广方式,青岛栈桥景区,广东seo推广方案一、树的基本术语
结点:树中的一个独立单元
结点的度:结点下分支的个数
树的度:树中所有结点中度的最大值
非终端结点:度不为0的结点
双亲和孩子:结点下的子树称为该结点的孩子.相应地,该结点称为孩子的双亲
兄弟:同一个双亲的孩子之间
祖先:从根到该结点所经分支上的所…一、树的基本术语
结点:树中的一个独立单元
结点的度:结点下分支的个数
树的度:树中所有结点中度的最大值
非终端结点:度不为0的结点
双亲和孩子:结点下的子树称为该结点的孩子.相应地,该结点称为孩子的双亲
兄弟:同一个双亲的孩子之间
祖先:从根到该结点所经分支上的所有结点
子孙:从某结点为根,其下直接或间接的结点
层次:从根开始,根的孩子为第二层,依次类推
堂兄弟:双亲在同一层的结点
树的深度:树中结点的最大层次称为树的深度或高度
有序树和无序树:如果将树中所有结点的各子树看成从左至右是有次序的,反之无序的为无序树(在有序树中最左边的子树的根称为第一个孩子最右边称为最后一个孩子)
森林m(m0)棵互不相交的树的集合 二、二叉树(Binary Tree)
1有且仅有一个称为根的结点
2除叶子结点,剩余每个结点可能有左孩子或右孩子(最多有两个)
二叉树具有天然递归结构
每个结点的左子树也是二叉树
每个结点的右子树也是二叉树 性质1:在二叉树的第i层上至多有2^(i-1)个结点(i1)
性质2:深度为k的二叉树至多有2^k-1个结点(k1)
性质3:对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0 n21(度为0的结点数比度为2的结点数多1) 三、二分搜索树
二分搜索树是二叉树
二分搜索树的每个结点的值(大于其左子树的所有结点的值|小于其右子树的所有结点的值)
每一棵子树也是二分搜索树 二分搜索树的相关操作
创建二分搜索树的类
// 保存在树中的结点必须具有可比性
public class BinearySearchTreeT extends ComparableT {}创建树的结点 private class NodeT {private T ele;// 结点的值private int frequence;// 频率private NodeT left, right;// 分别指向左右孩子的索引public Node(T ele) {this.ele ele;this.frequence 1;this.right this.left null;}} 树对应的属性 private NodeT root;// 树的根节点private int size;// 书中结点的个数
构建树 public BinearySearchTree() {this.root null;this.size 0;} 获取树中结点数
public int getSize() {return this.size;} 向树中添加结点
public void add(T ele) {// 更新根节点this.root addDG(this.root, ele);}// 语义:向以root为根的二分搜索树中添加元素eleprivate Node addDG(NodeT root, T ele) {// 递归终止条件if (root null) {this.size;return new NodeT(ele);}// 递归操作if (root.ele.compareTo(ele) 0) {root.left addDG(root.left, ele);} else if (root.ele.compareTo(ele) 0) {root.right addDG(root.right, ele);} else {// 更新频率root.frequence;}return root;}
查询某个值在树中是否存在
public boolean search(T ele) {return searchDG(this.root, ele);}// 语义:从以root为根的二分搜索树中查找元素eleprivate boolean searchDG(NodeT root, T ele) {// 递归终止条件if (root null) {return false;}// 递归操作if (root.ele.compareTo(ele) 0) {return true;} else if (root.ele.compareTo(ele) 0) {return searchDG(root.left, ele);} else {return searchDG(root.right, ele);}}
二分搜索树的先序遍历
public void preTravel() {ListAbstractMap.SimpleEntryT, Integer list new ArrayList();preTravelDG(this.root, list);String resStr list.stream().map(item - [ item.getKey() : item.getValue() ]).collect(Collectors.joining(-));System.out.println(resStr);}// 先序遍历以root为根的树,将结果保存在list中private void preTravelDG(NodeT root, ListAbstractMap.SimpleEntryT, Integer list) {// 递归终止条件if (root null) {return;}// 递归操作list.add(new AbstractMap.SimpleEntry(root.ele, root.frequence));// 遍历左子树preTravelDG(root.left, list);// 遍历右子树preTravelDG(root.right, list);}
二分搜索树的中序遍历
public void midTravel() {ListAbstractMap.SimpleEntryT, Integer list new ArrayList();midTravelDG(this.root, list);String resStr list.stream().map(item - [ item.getKey() : item.getValue() ]).collect(Collectors.joining(-));System.out.println(resStr);}// 中序遍历以root为根的树,将结果保存在list中private void midTravelDG(NodeT root, ListAbstractMap.SimpleEntryT, Integer list) {// 递归终止条件if (root null) {return;}// 递归操作// 遍历左子树midTravelDG(root.left, list);list.add(new AbstractMap.SimpleEntry(root.ele, root.frequence));// 遍历右子树midTravelDG(root.right, list);}
二分搜索树的后序遍历 public void sufTravel() {ListAbstractMap.SimpleEntryT, Integer list new ArrayList();sufTravelDG(this.root, list);String resStr list.stream().map(item - [ item.getKey() : item.getValue() ]).collect(Collectors.joining(-));System.out.println(resStr);}// 后序遍历以root为根的树,将结果保存在list中private void sufTravelDG(NodeT root, ListAbstractMap.SimpleEntryT, Integer list) {// 递归终止条件if (root null) {return;}// 递归操作// 遍历左子树sufTravelDG(root.left, list);// 遍历右子树sufTravelDG(root.right, list);list.add(new AbstractMap.SimpleEntry(root.ele, root.frequence));}
层序遍历(依赖队列)
public void levelTravel() {// 判断树是否为空if (this.isEmpty()) {return;}QueueAbstractMap.SimpleEntryNodeT, Integer queue new LinkedList();// 1.现将根节点入队queue.add(new AbstractMap.SimpleEntry(this.root, 1));// 2.遍历队列while (!queue.isEmpty()) {// 2-1 出队AbstractMap.SimpleEntryNodeT, Integer pair queue.poll();// 结点NodeT node pair.getKey();// 层int level pair.getValue();System.out.println([val: node.ele ,level: level ]);// 2-2 判断左右子树是否为空if (node.left ! null) {queue.add(new AbstractMap.SimpleEntry(node.left, level 1));}if (node.right ! null) {queue.add(new AbstractMap.SimpleEntry(node.right, level 1));}}}
判断是否为空
public boolean isEmpty() {return this.size 0;}
寻找树中最小元素
public T getMinValue() {if (this.isEmpty()) {return null;}OptionalNodeT optional getMinNode(this.root);return optional.get().ele;}// 语义:在以Node为根结点的树中查找最小结点private OptionalNodeT getMinNode(NodeT node) {// 递归终止的条件if (node.left null) {return Optional.of(node);}// 递归操作return getMinNode(node.left);}
寻找树中最大元素 public T getMaxValue() {if (this.isEmpty()) {return null;}OptionalNodeT optional getMaxNode(this.root);return optional.get().ele;}// 语义:在以Node为根结点的树中查找最大结点private OptionalNodeT getMaxNode(NodeT node) {// 递归终止的条件if (node.right null) {return Optional.of(node);}// 递归操作return getMaxNode(node.right);}
删除最小结点 public T removeMinNode() {T result getMinValue();if (result null) {return null;}// 更新根节点this.root removeMinNode(this.root);return result;}/*** 语义:从以node为根的二分搜索树中删除元素最小的结点** param node 树的根结点* return 删除最小结点之后的树的根结点*/private NodeT removeMinNode(NodeT node) {// 递归终止条件if (node.left null) {// 删除操作// 1.记录右子树NodeT rightTree node.right;// 2.失去关联关系node.right null;// 3.更新sizethis.size--;return rightTree;}// 递归操作node.left removeMinNode(node.left);return node;}
删除最大结点 public T removeMaxNode() {T result getMaxValue();if (result null) {return null;}// 更新根节点this.root removeMaxNode(this.root);return result;}/*** 语义:从以node为根的二分搜索树中删除元素最大的结点** param node 树的根结点* return 删除最大结点之后的树的根结点*/private NodeT removeMaxNode(NodeT node) {// 递归终止条件if (node.right null) {// 删除操作// 1.记录左子树NodeT leftTree node.left;// 2.失去关联关系node.left null;// 3.更新sizethis.size--;return leftTree;}// 递归操作node.right removeMaxNode(node.right);return node;} 删除任意结点 public void remove(T ele) {// 根据值查找结点this.root remove(this.root, ele);}private NodeT remove(NodeT node, T ele) {// 递归终止条件// 没有找到的情况if (node null) {return null;}// 找到了删除的结点if (node.ele.compareTo(ele) 0) {this.size--;// node就是要删除的结点 // 1.左子树空,右子树不为空if (node.left null) {NodeT rightNode node.right;node.right null;return rightNode;} else if (node.right null) {// 2.右子树空,左子树不为空NodeT leftNode node.left;node.left null;return leftNode;} else {// 3.左右子树都不为空// 3-1从右子树中找最小结点NodeT suffixNode getMinNode(node.right).get();// 从右子树中删除最小结点suffixNode.right removeMinNode(node.right);suffixNode.left node.left;// 将node结点的左右子树失去关联关系node.left node.right null;this.size;return suffixNode;}}// 递归操作if (node.ele.compareTo(ele) 0) {node.left remove(node.left, ele);} else {node.right remove(node.right, ele);}return node;} 删除根结点 public void removeRoot() {if (this.root null) {return;}remove(this.root.ele);}
