首页 > 其他 > 详细

数据结构--树

时间:2018-05-25 14:31:40      阅读:116      评论:0      收藏:0      [点我收藏+]

标签:创建   emp   TP   arc   true   parent   clas   arch   test   

什么是树?

树是节点的有限集合

技术分享图片

名词普及:

1、孩子:当前节点下的所有第一级节点,就是当前节点的孩子。

如上所示:

A节点的孩子有B、C、D B节点的孩子有 D、E;

C节点没有孩子 D节点的孩子有G、H

2、双亲节点(父节点):当前节点的上一级节点

如上所示:B是A的孩子,即B是A的双亲

3、祖先:从根到该节点所经分支上的所有节点;

如上所示:

E的祖先有:BAF的祖先有:BA

G的祖先有:DAH的祖先有:DA

B的祖先有:AC的祖先有:A

D的祖先有:A

4、兄弟节点:具有相同父节点的节点互称为兄弟节点;

如上所示:

BCD互为兄弟节点;EF互为兄弟节点; GH互为兄弟节点;

5、堂兄弟节点:双亲在同一层的节点互为堂兄弟;

如上所示:

EG互为堂兄弟节点; EH互为堂兄弟节点;

FG互为堂兄弟节点; FH互为堂兄弟节点;

 

6、度:当前节点下,孩子的数量就是该节点的度

如上所示:

A节点的度为3;B节点的度为2;C节点的度为0;D节点的度为2;EFGH的度为0;

7、叶子(终端节点):没有孩子的节点,即度为0的节点就是终端节点

如上所示:

C、E、F、G、H为终端节点;

8、根(非终端节点):有孩子的节点,即度不为0的节点就是根

如上所示:

A、B、D为终端节点;

9、有序树:树中任意节点的子结点之间有顺序关系,这种树称为有序树;

10、无序树:树中任意节点的子结点之间没有顺序关系,这种树称为无序树,也称为自由树;

11、二叉树:每个节点最多含有两个子树的树称为二叉树;

 

12、深度:定义一棵树的根结点层次为1,其他节点的层次是其父结点层次加1。一棵树中所有结点的层次的最大值称为这棵树的深度。

节点的深度:当前节点所在的层数

如上所示:A的深度为1;B、C、D的深度为2;E、F、G、H的深度为3

树的深度:取树中所有节点深度最大的深度

如上所示:E的深度为3,其他所有节点的深度,没有更大的,所以该树的深度为3‘

13、森林:mm>=0)棵互不相交的树(独立的树)的集合称为森林;

 

二叉树

数组实现

数组与二叉树之间的算法转换:

父节点的下标 * 2 + 1 = 左子节点;

父节点的下标 * 2 + 2 = 右子节点;

链表实现

节点要素:索引,数据,左孩子指针,右孩子指针,父节点指针

技术分享图片

前序遍历:根、左、右

中序遍历:左、根、右

后序遍历:左、右、根

 

附上二叉树的创建代码:

package util;

import test.entity.TreeNode;

public class MyBinaryTree {
    private TreeNode myBinaryTree;
    
    /**
     * 初始化二叉树
     */
    public MyBinaryTree () {
        myBinaryTree = new TreeNode();
    }
    
    /**
     * 搜索树节点
     * @param nodeIndex
     * @return
     */
    public TreeNode SearchNode (int nodeIndex){
        return myBinaryTree.SearchNode(nodeIndex);
    }
    
    /**
     * 添加树节点
     * @param nodeIndex
     * @param direction
     * @param treeNode
     * @return
     */
    public TreeNode addNode(int nodeIndex, int direction, TreeNode treeNode){
        TreeNode  node = SearchNode(nodeIndex);
        if (node == null){
            return null;
        }
        
        //如果直接使用外面传进来的对象treeNode那么当该对象在外面被进行操作时,可能会使该对象失去了所拥有的完整性,所以此处我们新申请了一个对象用于存放treeNode的值
        TreeNode newNode = new TreeNode();
        newNode.index = treeNode.index;
        newNode.data = treeNode.data;
        
        if (direction == 0){
            node.pLChild = newNode;
        }

        if (direction == 1){
            node.pRChild = newNode;
        }
        newNode.pParent = node;
        return newNode;
    }
    
    /**
     * 删除树节点
     * @param nodeIndex
     * @return
     */
    public TreeNode deleteNode(int nodeIndex){
        TreeNode  node = SearchNode(nodeIndex);
        if (node == null){
            return null;
        }
        
        TreeNode temp = new TreeNode();
        temp.index = node.index;
        temp.data = node.data;
        
        node.deleteNode();
        return temp;
    }
    
    /**
     * 前序遍历
     */
    public void preorderTraversal(){
        myBinaryTree.preorderTraversal();
    }

    /**
     * 中序遍历
     */
    public void inorderTraversal(){
        myBinaryTree.inorderTraversal();
    }
    
    /**
     * 后序遍历
     */
    public void postorderTraversal(){
        myBinaryTree.postorderTraversal();
    }
}

  

数据结构--树

标签:创建   emp   TP   arc   true   parent   clas   arch   test   

原文:https://www.cnblogs.com/fuhui-study-footprint/p/9088362.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号