二叉树正确输入方法
什么是不平衡二叉树?
什么是不平衡二叉树?
它或者是一颗空树,或者具有以下性质的二叉树:它的左子树和右子树的深度之差的绝对值不超过1,且它的左子树和右子树都是一颗平衡二叉树。
平衡因子(bf):结点的左子树的深度减去右子树的深度,那么显然-1bf1;
很显然,平衡二叉树是在二叉排序树(BST)上引入的,就是为了解决二叉排序树的不平衡性导致时间复杂度大大下降,那么AVL就保持住了(BST)的最好时间复杂度O(logn),所以每次的插入和删除都要确保二叉树的平衡
二叉搜索树怎么构建?
动态创建二叉树就是将数组变成一个二叉树,往往动态创建二叉树都是创建二叉搜索树。创建二叉搜索树的过程就是不断的向二叉树中插入节点的过程。在插入节点过程中保证二叉搜索树的特性:任意一节点的左子树的所有节点都小于该节点,并且其右子树的所有节点都大于该节点。
例如用数组[10, 6, 8, 15, 13, 17, 11, 14]来创建二叉搜索树。
什么是层次遍历序列?
编一个程序,读入用户输入的一串先序遍历字符串,根据输入建立一棵二叉树, 并输出该二叉树的层次遍历序列。层次遍历是指逐层访问,每一层又按从左到右的次序访问结点。
输入
输入包括1行字符串,长度不超过100。
输出
输出二叉树的层次遍历序列。每个结点先输出一个空格,然后再跟着输出结点的数据。
样例输入 Copy
12##3##
样例输出 Copy
1 2 3
二叉排序树怎么显示?
在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”(left subtree)和“右子树”(right subtree)。二叉树常被用于实现二叉查找树和二叉堆。 二叉排序树(Binary Sort Tree)又称二叉查找树(Binary Search Tree),亦称二叉搜索树。 二叉排序树或者是一棵空树,或者是具有下列性质的二叉树:
(充分必要条件) (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值;
(2)若右子树不空,则右子树上所有结点的值均大于或等于它的根结点的值;
(3)左、右子树也分别为二叉排序树;
(4)没有键值相等的节点。 每个结点的C(i)为该结点的层次数。
最坏情况下,当先后插入的关键字有序时,构成的二叉排序树蜕变为单支树,树的深度为其平均查找长度(n 1)/2(和顺序查找相同),最好的情况是二叉排序树的形态和折半查找的判定树相同,其平均查找长度和log 2 (n)成正比。