网站后台管理系统怎么上传,网站建设微企,建盏的好处,鹤壁市城乡一体化示范区网站二叉树基本知识#xff1a;
一、树的定义
树是一种数据结构#xff0c;它是由n#xff08;n1#xff09;个有限结点组成一个具有层次关系的集合。 树具有的特点有#xff1a;
#xff08;1#xff09;每个结点有零个或多个子结点
#xff08;2#xff09;没有…二叉树基本知识
一、树的定义
树是一种数据结构它是由nn1个有限结点组成一个具有层次关系的集合。 树具有的特点有
1每个结点有零个或多个子结点
2没有父节点的结点称为根节点
3每一个非根结点有且只有一个父节点
4除了根结点外每个子结点可以分为多个不相交的子树。
树的基本术语有
若一个结点有子树那么该结点称为子树根的“双亲”子树的根称为该结点的“孩子”。有相同双亲的结点互为“兄弟”。一个结点的所有子树上的任何结点都是该结点的后裔。从根结点到某个结点的路径上的所有结点都是该结点的祖先。
结点的度结点拥有的子树的数目
叶子结点度为0的结点
分支结点度不为0的结点
树的度树中结点的最大的度
层次根结点的层次为1其余结点的层次等于该结点的双亲结点的层次加1
树的高度树中结点的最大层次
森林0个或多个不相交的树组成。对森林加上一个根森林即成为树删去根树即成为森林。
二、二叉树
1、二叉树的定义
二叉树是每个结点最多有两个子树的树结构。它有五种基本形态二叉树可以是空集根可以有空的左子树或右子树或者左、右子树皆为空。 2、二叉树的性质
性质1二叉树第i层上的结点数目最多为2i-1(i1)
性质2深度为k的二叉树至多有2k-1个结点k1
性质3包含n个结点的二叉树的高度至少为(log2n)1
性质4在任意一棵二叉树中若终端结点的个数为n0度为2的结点数为n2则n0n21
3、性质4的证明
性质4在任意一棵二叉树中若终端结点的个数为n0度为2的结点数为n2则n0n21
证明因为二叉树中所有结点的度数均不大于2不妨设n0表示度为0的结点个数n1表示度为1的结点个数n2表示度为2的结点个数。三类结点加起来为总结点个数于是便可得到nn0n1n2 (1)
由度之间的关系可得第二个等式nn00n11n2*21即nn12n21 (2)
将12组合在一起可得到n0n21
三、满二叉树、完全二叉树和二叉查找树
1、满二叉树
定义高度为h并且由2h-1个结点组成的二叉树称为满二叉树 2、完全二叉树
定义一棵二叉树中只有最下面两层结点的度可以小于2并且最下层的叶结点集中在靠左的若干位置上这样的二叉树称为完全二叉树。
特点叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左部。显然一棵满二叉树必定是一棵完全二叉树而完全二叉树未必是满二叉树。 面试题如果一个完全二叉树的结点总数为768个求叶子结点的个数。
由二叉树的性质知n0n21将之带入768n0n1n2中得768n12n21因为完全二叉树度为1的结点个数要么为0要么为1那么就把n10或者1都代入公式中很容易发现n11才符合条件。所以算出来n2383所以叶子结点个数n0n21384。
总结规律如果一棵完全二叉树的结点总数为n那么叶子结点等于n/2当n为偶数时或者(n1)/2当n为奇数时
3、二叉查找树
定义二叉查找树又被称为二叉搜索树。设x为二叉查找树中的一个结点x结点包含关键字key结点x的key值计为key[x]。如果y是x的左子树中的一个结点则key[y]key[x]如果y是x的右子树的一个结点则key[y]key[x] 在二叉查找树种
1若任意结点的左子树不空则左子树上所有结点的值均小于它的根结点的值。
2任意结点的右子树不空则右子树上所有结点的值均大于它的根结点的值。
3任意结点的左、右子树也分别为二叉查找树。
4没有键值相等的结点。
要求将一个数组中的数以二叉树的存储结构存储并遍历打印。
import java.util.ArrayList;
import java.util.List;public class bintree {public bintree left;public bintree right;public bintree root;
// 数据域private Object data;// 存节点public Listbintree datas;public bintree(bintree left, bintree right, Object data){this.leftleft;this.rightright;this.datadata;}
// 将初始的左右孩子值为空public bintree(Object data){this(null,null,data);}public bintree() {}public void creat(Object[] objs){datasnew ArrayListbintree();// 将一个数组的值依次转换为Node节点for(Object o:objs){datas.add(new bintree(o));}
// 第一个数为根节点rootdatas.get(0);
// 建立二叉树for (int i 0; i objs.length/2; i) {
// 左孩子datas.get(i).leftdatas.get(i*21);
// 右孩子if(i*22datas.size()){//避免偶数的时候 下标越界datas.get(i).rightdatas.get(i*22);}}}
//先序遍历
public void preorder(bintree root){if(root!null){System.out.println(root.data);preorder(root.left);preorder(root.right);}
}
//中序遍历public void inorder(bintree root){if(root!null){inorder(root.left);System.out.println(root.data);inorder(root.right);}}
// 后序遍历public void afterorder(bintree root){if(root!null){System.out.println(root.data);afterorder(root.left);afterorder(root.right);}}public static void main(String[] args) {bintree bintreenew bintree();Object []a{2,4,5,7,1,6,12,32,51,22};bintree.creat(a);bintree.preorder(bintree.root);}
}要求从键盘输入数存为二叉树结构并打印。
import java.util.Scanner;public class btree {private btree left,right;private char data;public btree creat(String des){Scanner scannernew Scanner(System.in);System.out.println(des:des);String strscanner.next();if(str.charAt(0)a)return null;btree rootnew btree();root.datastr.charAt(0);root.leftcreat(str.charAt(0)左子树);root.rightcreat(str.charAt(0)右子树);return root;}public void midprint(btree btree){
// 中序遍历if(btree!null){midprint(btree.left);System.out.print(btree.data );midprint(btree.right);}}public void firprint(btree btree){
// 先序遍历if(btree!null){System.out.print(btree.data );firprint(btree.left);firprint(btree.right);}}public void lastprint(btree btree){
// 后序遍历if(btree!null){lastprint(btree.left);lastprint(btree.right);System.out.print(btree.data );}}public static void main(String[] args) {btree tree new btree();btree newtreetree.creat(根节点);tree.firprint(newtree);System.out.println();tree.midprint(newtree);System.out.println();tree.lastprint(newtree);}
}输出结果
des:根节点 a des:a左子树 e des:e左子树 c des:c左子树 1 des:c右子树 1 des:e右子树 b des:b左子树
1 des:b右子树 1 des:a右子树 d des:d左子树 f des:f左子树 1 des:f右子树 1 des:d右子树 1 a e c b d f 先序 c e b a f d 中序 c b e f d a 后序
二叉树的遍历次序
前序顺序是根节点排最先然后同级先左后右中序顺序是先左后根最后右后序顺序是先左后右最后根。
例如 比如上图二叉树遍历结果
前序遍历ABCDEFGHK
中序遍历BDCAEHGKF
后序遍历DCBHKGFEA
分析中序遍历如下图中序比较重要java很多树排序是基于中序后面讲解分析
