常见的数据结构:树Tree

这篇具有很好参考价值的文章主要介绍了常见的数据结构:树Tree。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

目录

1.概念

1.1 满二叉树

1.2 完全二叉树

 1.3 平衡二叉树

 2.遍历方式

2.1 先序遍历

2.2 中序遍历

2.3 后序遍历

2.4 层序遍历

1.概念

原理:一种特殊的数据结构,每个节点有零个或多个子节点;没有父节点的节点称为根节点;每一个非根节点有且只有一个父节点;除了根节点外,每个子节点可以分为多个不相交的子树

二叉树的分类:满二叉树、完全二叉树、平衡二叉树

存储方式:数组或者链表实现

遍历方式:先序遍历、中序遍历、后序遍历、层序遍历

1.1 满二叉树

        二叉树的每一层节点树都达到最大值,就叫做满二叉树

数学表示:层数为 K,结点总数就为(2^k) -1常见的数据结构:树Tree,数据结构 

1.2 完全二叉树

        二叉树除了最后一层外,其余层都是满二叉树,且最后一层是满的或者是右边缺少若干节点

常见的数据结构:树Tree,数据结构

 1.3 平衡二叉树

        树的左右子树的高度差绝对值不超过1,且左右子树也为平衡二叉树

常见的数据结构:树Tree,数据结构

 

 2.遍历方式

2.1 先序遍历

        先输出根节点,然后遍历左子树,最后遍历右子树

代码示例:

public void preOrder(TreeNode root){
	if(root == null){
		return;
	}
	system.out.println(root.data);
	preOrder(root.left);
	preOrder(root.right);
}

2.2 中序遍历

        先遍历左子树,然后遍历根节点,最后遍历右子树

public void inOrder(TreeNode root){
	if(root == null){
		return;
	}
	inOrder(root.left);
	system.out.println(root.data);
	inOrder(root.right);
}

2.3 后序遍历

        先遍历左子树,然后遍历右子树,最后遍历根节点

public void postOrder(TreeNode root){
	if(root == null){
		return;
	}
	postOrder(root.left);
	postOrder(root.right);
	system.out.println(root.data);
}

2.4 层序遍历

        按照层级遍历,逐层从左到右访问所有节点文章来源地址https://www.toymoban.com/news/detail-639974.html

public List<List<Integer>> levelOrder(TreeNode root){
    //用一个二维数组存储最终层序遍历出的元素
    List<List<Integer>> result = new ArrayList<>();
    if(null == root){
        return result;
    }
    
    //创建一个队列用来存入树节点
    Queue queue = new LinkedList();
    queue.add(root);

    while(!queue.isEmpty){
        int len = queue.size();
        List<Integer> list= new ArrayList();
        while(len > 0){
            TreeNode temp = queue.poll();
            list.add(temp.val);
            
            //如果节点左右有值就加入队列
            if(temp.left != null){
                queue.add(temp.left);
            }
            if(temp.right!= null){
                queue.add(temp.right);
            }
            len --;
        }
        result.add(list);
    }
    return result;
}

到了这里,关于常见的数据结构:树Tree的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构基础】树 - 前缀树(Trie Tree)

    Trie,又称字典树、单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的

    2024年02月07日
    浏览(44)
  • 数据结构与算法 | 二叉树(Binary Tree)

    二叉树(Binary Tree)是一种树形数据结构,由节点构成,每个节点最多有两个子节点:一个左子节点和一个右子节点。 \\\"二叉树\\\"(Binary Tree)这个名称的由来是因为二叉树的每个节点最多有两个子节点,一个左子节点和一个右子节点。其中,“二叉”指的是两个,因此“二叉树

    2024年02月08日
    浏览(40)
  • Java 【数据结构】 二叉树(Binary_Tree)【神装】

        登神长阶  第五神装 二叉树 Binary-Tree 目录  🎷一.树形结构 🪗1.概念 🎸2.具体应用 🎹 二.二叉树(Binary Tree) 🎺1.概念  🎻2.表现形式 🪕3.特殊类型 🥁3.1完全二叉树(Complete Binary Tree) 🪘3.2满二叉树(Full Binary Tree) 🔋4.性质  🪫5.二叉树的遍历 💿5.1前中后序遍历

    2024年04月27日
    浏览(45)
  • 红黑树下岗,内核新数据结构上场:maple tree!

      在外界看来,Linux 内核的内部似乎变化很少,尤其是像内存管理子系统(memory-management subsystem)这样的子系统。然而,开发人员时常需要更换内部接口来解决某些长期存在的问题。比如,其中一个问题就是用来保护内存管理里的重要结构的锁的竞争问题,这些重要结构是指

    2024年02月04日
    浏览(49)
  • Element-UI控件Tree实现数据树形结构

            在前端开发中,有时会遇到所有菜单数据在同一级的情况,后端未对数据进行分级处理;但前端渲染需要是树状结构的数据,如何实现数据的树状化?将数组中通过父节点的ID与子节点的parentId关联,通过递归函数来实现。         前端框架这里使用element-ui的tree控件

    2024年02月05日
    浏览(118)
  • 区块链的数据结构(二)——默克尔树(Merkle Tree)

            区块链中的另外一个数据结构是Merkle tree,在比特币中使用的就是这种结构:         可能没有听说过Merkle tree,但一定听说过binary tree(二叉树)。         Merkle tree和binary tree的区别:Merkle tree用哈希指针代替了普通的指针         每个框内的两个哈希值

    2024年02月21日
    浏览(44)
  • Java学数据结构(2)——树Tree & 二叉树binary tree & 二叉查找树 & AVL树 & 树的遍历

    1.树的出现:解决链表线性访问时间太慢,树的时间复杂度O(logN); 2.二叉树的定义,最多两个儿子节点; 3.二叉查找树,左小,右大,中居中;remove方法,两种,只有一个儿子节点,有两个儿子节点; 4.AVL树,在二叉查找树基础上加平衡条件,旋转方法,单旋转,双旋转;

    2024年02月10日
    浏览(49)
  • 【数据结构与算法】-哈夫曼树(Huffman Tree)与哈夫曼编码

    超详细讲解哈夫曼树(Huffman Tree)以及哈夫曼编码的构造原理、方法,并用代码实现。 路径 :从树中一个结点到另一个结点之间的 分支 构成这两个结点间的路径。 结点的路径长度 :两结点间路径上的 分支数 。 树的路径长度: 从树根到每一个结点的路径长度之和。记作: TL  权

    2024年02月06日
    浏览(53)
  • 浙大数据结构第四周之04-树6 Complete Binary Search Tree

    A Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties: The left subtree of a node contains only nodes with keys less than the node\\\'s key. The right subtree of a node contains only nodes with keys greater than or equal to the node\\\'s key. Both the left and right subtrees must also be binary search trees. A Comple

    2024年02月16日
    浏览(49)
  • 数据结构英文习题解析-第五章 二叉搜索树Binary Search Tree

    前言:最近快到FDS考试了,po重刷了一下学校的题目,自己整理了一些解析orz 因为po在自己找解析和学习的过程中非常痛苦,所以在此共享一下我的题目和自己写的解题思路,欢迎各位指出错误~全章节预计会陆续更新,可在专栏查看~ HW5 1.In a binary search tree, the keys on the same

    2024年04月09日
    浏览(48)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包