数据结构—树、有序二叉树

————————————————————————————————

树的概述

树——>链式存储结构
注：
数组：查询简单，插入删除复杂
链表：增删改简单，查询复杂
树：即保证查找速度，又保证增删改速度根节点比要查找的数大的话，相当于根节点右边的树可以不需要查询，类似于二分查找

树的分类

二叉树的遍历

例：

有序二叉树代码

有序二叉树特点：左子节点的值小于父节点，右子节点的值大于父节点


（1）首先5做根节点，7和5比较，7比5大则作为5的右子节点；
（2）4和5比较，4比5小则作为5的左子节点；
（3）2和5比较，2比5小，则向左走，5右左子节点4，2和4比较，2比4小且4没有左子节点，则2作为4的左子节点；
（4）向后重复上述步骤

通过链表方式构建有序二叉树

—1—>创建类，创建管理类，创建新节点newNode，创建指向根节点的变量root
—2—>如果root为空，将newNode放再root上面
—3—>当root不为空时，定义游标p指向root，准备向后遍历二叉树
—4—>newNode和游标p指向的根节点进行值得比较，newNode小则向左走，newNode大则向右走
—5—>判断现在p指向是否为空，p不为空则表示有左(右)子节点，继续让newNode和p指向的节点判断大小；p为空则插入数据
—6—>p当前指向为空，该如何解决插入数据得问题？=>定义另一个游标pre指向p游标得前一个节点
—7—>在每次循环时让pre指向p当前指向的节点，后面p向后走时，pre指向不动；因为p向下走一步且指向不为空时，会进行while循环，pre再次指向p，而此时p已经指向下一个了，所以pre始终指向p的前一个。
—8—>有了pre指向p的前一个节点，因此当p指向空时，给pre的左（右）节点赋值，就完成了节点的插入操作

import java.util.LinkedList;

public class BinaryTree{
   
    TreeNode root;
    /*
     * 【1】构建有序二叉树
    * */
    public void insert(int value) {
   //传值
    //新建节点
    TreeNode newNode=new TreeNode(value);
    //判断树是否为空
    //为空
    
1
2
3
4
5
6
7
8
9
10
11
12
13
14