常见树形结构

  created  by  鱼鱼 {{tag}}
创建于 2019年03月07日 00:09:42 最后修改于 2019年03月15日 20:21:51

常见树形结构

常见树形结构

树形结构

相关术语

  1. 结点(Node):表示树中的数据元素,由数据项和数据元素之间的关系组成。在图中,共有10个结点

  2. 结点的度(Degree of Node):结点所拥有的子树的个数,在图中,结点A的度为3

  3. 树的度(Degree of Tree):树中各结点度的最大值。在图中,树的度为3

  4. 叶子结点(Leaf Node):度为0的结点,也叫终端结点。在图中,结点E、F、G、H、I、J都是叶子结点

  5. 分支结点(Branch Node):度不为0的结点,也叫非终端结点或内部结点。在图中,结点A、B、C、D是分支结点

  6. 孩子(Child):结点子树的根。在图中,结点B、C、D是结点A的孩子

  7. 双亲(Parent):结点的上层结点叫该结点的双亲。在图中,结点B、C、D的双亲是结点A

  8. 祖先(Ancestor):从根到该结点所经分支上的所有结点。在图中,结点E的祖先是A和B

  9. 子孙(Descendant):以某结点为根的子树中的任一结点。在图中,除A之外的所有结点都是A的子孙

  10. 兄弟(Brother):同一双亲的孩子。在图5.1中,结点B、C、D互为兄弟

  11. 结点的层次(Level of Node):从根结点到树中某结点所经路径上的分支数称为该结点的层次。根结点的层次规定为1,其余结点的层次等于其双亲结点的层次加1。 

  12. 堂兄弟(Sibling):同一层的双亲不同的结点。在图中,G和H互为堂兄弟

  13. 树的深度(Depth of Tree):树中结点的最大层次数。在图5.1中,树的深度为3。 

  14. 无序树(Unordered Tree):树中任意一个结点的各孩子结点之间的次序构成无关紧要的树。通常树指无序树。 

  15. 有序树(Ordered Tree):树中任意一个结点的各孩子结点有严格排列次序的树。二叉树是有序树,因为二叉树中每个孩子结点都确切定义为是该结点的左孩子结点还是右孩子结点。 

  16. 森林(Forest):m(m≥0)棵树的集合。自然界中的树和森林的概念差别很大,但在数据结构中树和森林的概念差别很小。从定义可知,一棵树有根结点和m个子树构成,若把树的根结点删除,则树变成了包含m棵树的森林。当然,根据定义,一棵树也可以称为森林。 

二叉树

    二叉树是最简单的树形结构,其特点为:

    所以,有如下几个特性:

    满二叉树,表示所有的节点都同时拥有左右子树,叶子节点在同一层中,比如:

满二叉树

    完全二叉树,表示按从上至下,从左至右的顺序排序,不会出现空位,比如:

图2 完全二叉树

    二叉树的存储顺序,是从上到下,从左到右,空置的节点也会耗费空间,比如上面的二叉树都是按照从A到G的顺序存储的

    二叉树的java实现

    在这里介绍一些java中二叉树的实现的关键点。

    定树节点部分:

public class TreeNode
{
        private String data = null;// 数据部分,多用两个参数的键值对表示,此处简化为单个值
        private TreeNode left;// 左节点的引用
        private TreeNode right;// 右节点的引用
        //……sth.
}

    二叉树的遍历

    二叉树的遍历方试有前中后序,对应代码:

    /**
     * 前序遍历
     * 
     * @param node
     */
    public void preOrder(TreeNode node)
    {
        if (node != null)
        {
            System.out.println(node.getData());
            preOrder(node.getLeft());
            preOrder(node.getRight());
        }
    }

    /**
     * 中序遍历
     * 
     * @param node
     */
    public void inOrder(TreeNode node)
    {
        if (node != null)
        {
            inOrder(node.getLeft());
            System.out.println(node.getData());
            inOrder(node.getRight());
        }
    }

    /**
     * 后续遍历
     * 
     * @param node
     */
    public void postOrder(TreeNode node)
    {
        if (node != null)
        {
            postOrder(node.getLeft());
            postOrder(node.getRight());
            System.out.println(node.getData());
        }
    }

    我们按照上图中完全二叉树的顺序推演就是前序遍历ABDECF,中序遍历DBEAFC,后序遍历DEBFCA。

    还有层次遍历(提供两种类似的实现,请注意考虑空子树的情况):

public void order(TreeNode node){
    Queue<TreeNode> queue= new ArrayBlockingQueue<TreeNode>(20);
    queue.add(node);
    while(!queue.isEmpty()){
        node=queue.poll();
        System.out.println(node.getData());
        if(node.getLeft()!=null){
            queue.add(node.getLeft());
        }
        if(node.getRight()!=null){
            queue.add(node.getRight())
        }
    }
}

private ArrayList<Integer> list=new ArrayList<Integer>();
public void orderTree2(TreeNode node,int p){
    for(int i=0;i<size;i++){
        list.add(-1);
    }
    list.set(p,node.getData());
    if(node.getLeft()!=null){
        readTree(node.getLeft(),p*2);
    }
    if(node.getRight()!=null){
        readTree(node.getRight(),p*2+1);
    }
}
//后者的list就是层次树结构,空位为-1

    二叉查找树

    当我们开始代入树中的数据时,便诞生了二叉查找树,这是二叉树的基本应用,二叉查找树是满足如下几点条件的二叉树:

    例如:

    使用时,遍历二叉树,若值大于节点,则遍历右子树,反之左子树,直到查到值或无结果。简单谈一下代码实现:

查找节点:

public Node find(int key) {
        Node currentNode = root;            //root为定值 记录根节点
        while (currentNode != null && currentNode.key != key) {
            if (key < currentNode.key) {
                currentNode = currentNode.leftChild;
            } else {
                currentNode = currentNode.rightChild;
            }
        }
        return currentNode;
}

插入节点:

public void insert(int key, int value) {
        if (root == null) {
            root = new Node(key, value);
            return;
        }
        Node currentNode = root;
        Node parentNode = root;
        boolean isLeftChild = true;
        while (currentNode != null) {        //遍历过程 这里需要已经确定key值不在树中
            parentNode = currentNode;
            if (key < currentNode.key) {
                currentNode = currentNode.leftChild;
                isLeftChild = true;
            } else {
                currentNode = currentNode.rightChild;
                isLeftChild = false;
            }
        }
        Node newNode = new Node(key, value);     //currentNode为空,需插入
        if (isLeftChild) {
            parentNode.leftChild = newNode;
        } else {
            parentNode.rightChild = newNode;
        }
}

删除节点:

    删除节点的操作非常复杂,分为两部分。

public boolean delete(int key) {
    Node currentNode = root;//用来保存待删除节点
    Node parentNode = root;//用来保存待删除节点的父亲节点
    boolean isLeftChild = true;//用来确定待删除节点是父亲节点的左孩子还是右孩子
    while (currentNode != null && currentNode.key != key) {
        parentNode = currentNode;
        if (key < currentNode.key) {
            currentNode = currentNode.leftChild;
            isLeftChild = true;
        } else {
            currentNode = currentNode.rightChild;
            isLeftChild = false;
        }
    }
    if (currentNode == null) {
        return false;
    }
    if (currentNode.leftChild == null && currentNode.rightChild == null) {//要删除的节点为叶子节点
        if (currentNode == root)
            root = null;
        else if (isLeftChild)
            parentNode.leftChild = null;
        else
            parentNode.rightChild = null;
    }else if (currentNode.rightChild == null) {//要删除的节点只有左子树
          if (currentNode == root)
             root = currentNode.leftChild;
        else if (isLeftChild)
            parentNode.leftChild = currentNode.leftChild;
        else
            parentNode.rightChild = currentNode.leftChild;
    }else if (currentNode.leftChild == null) {//要删除的节点只有右子树
        if (currentNode == root)
            root = currentNode.rightChild;
        else if (isLeftChild)
            parentNode.leftChild = currentNode.rightChild;
        else
               parentNode.rightChild = currentNode.rightChild;
    }else { 
       //要删除的节点既有左子树又有右子树
             
        }
        return true; 
}

    当要删除的节点含有左右子树时:

             //要删除的节点既有左子树又有右子树
             //思路:用待删除节点右子树中的key值最小节点的值来替代要删除的节点的值,然后删除右子树中key值最小的节点
             //右子树key最小的节点一定不含左子树,所以删除这个key最小的节点一定是属于叶子节点或者只有右子树的节点
                Node directPostNode = getDirectPostNode(currentNode);
                currentNode.key = directPostNode.key;
                currentNode.value = directPostNode.value;
                
                ……
private Node getDirectPostNode(Node delNode) {
//方法作用为得到待删除节点的直接后继节点
        
        Node parentNode = delNode;//用来保存待删除节点的直接后继节点的父亲节点
        Node direcrPostNode = delNode;//用来保存待删除节点的直接后继节点
        Node currentNode = delNode.rightChild;
        while (currentNode != null) {
            parentNode = direcrPostNode;
            direcrPostNode = currentNode;
            currentNode = currentNode.leftChild;
        }
        if (direcrPostNode != delNode.rightChild) {//从树中删除此直接后继节点
            parentNode.leftChild = direcrPostNode.rightChild;
            direcrPostNode.rightChild = null;
        }
        return direcrPostNode;//返回此直接后继节点   
}

B Tree

参考链接:百度百科-树形结构深度学习二叉树


2019-03-15鱼鱼