树之二叉树

谁践踏了优雅 2023-07-08 02:55 14阅读 0赞

## 二叉树 ##

二叉树是每个结点最多有两个子树的有序树。通常子树的根被称作“左子树”（left subtree）和“右子树”（right subtree）。  
二叉树常被用作二叉查找树和二叉堆或是二叉排序树。

满二叉树：在二叉树的第i 层上有2^(i-1)个结点, 深度为k的二叉树有2^k-1个结点的二叉树。则此二叉树称为“满二叉树”  
完全二叉树：深度为k的二叉树,第i (1<=i<=k-1) 层上有2^(i-1)个结点, 第k层的结点都集中在该层最左边的若干位置上，则此二叉树称为“完全二叉树”。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]

## 二叉树的性质 ##

①在二叉树的第i (i>0)层上至多有2i-1个结点。  
②深度为k的二叉树中至多有2k-1个结点(k>0)。  
③对任何一棵二叉树T，如果其终端结点数为n0,度为2的结点数为n2，则 n0=n2+1。  
PS：在此处，可理解为度为2的结点数为0时有1个终端结点，而某个结点度加1时  
就会增加一个分支，从而使终端结点数加1。  
④有n个结点的完全二叉树的深度k为: （向下取整）log2n +1。  
⑤有n个结点的完全二叉树各结点如果用顺序方式存储，则结点之间有如下关系：  
若i为结点编号则 如果i>1，则其父结点的编号为I/2；  
如果2*i<=n，则其左儿子（即左子树的根结点）的编号为2*I；若2*I>N，则无左儿子；  
如果2*i+1<=n，则其右儿子的结点编号为2*I+1；若2*I+1>N，则无右儿子。

## 二叉树基本运算 ##

①创建、初始化  
②求某个指定结点  
③二叉树的遍历

## 二叉树的存储结构 ##

（1）顺序存储  
可使用顺序表对完全二叉树进行存储，数据存储位置和性质⑤相对应  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]  
（2）非顺序存储  
①二叉链，定义结点，使用链式结构进行存储。

②静态二叉链，即建立结点数组，左右孩子存储数组索引。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]

## 实例使用三元组初始化链表 ##

以三元组形式输入 (x,p,lr) , 其中 x:data , p: x的父结点数据, lr: x是p的左孩子(l)或是右孩子(\\r)。  
①主创建函数

/**
      * 根据一个二维数组，产生树的结构
      * @param a   结点信息存储的二维数组
      */
     public void CreateTree(String[][] a) {
      	//初始化根结点
     	 rootNode = new TreeNode();
      	//第一个数值赋给根结点
      	if(rootNode.getData() == null) {
      		 rootNode.setData(a[0][0]);
      	}
      	TreeNode moveNode;
      	//遍历数组对数据进行存储
     	 for(int i=1; i < a.length; i++) {
       		TreeNode midNode = new TreeNode();
       		midNode.setData(a[i][0]);
       		moveNode = seekFaNode(a[i][1], this.rootNode);
       		if(moveNode != null) {
        			if(a[i][2].equals("left")) {
         			moveNode.setLeChild(midNode);
        			}else {
        			moveNode.setRiChild(midNode);
        			}
       		}   
     	 }
     }

②查找父结点的函数

/**
      * 递归遍历树找到父结点
      * @param d   用以定位的父结点数据
      * @return    父结点
      */
     public TreeNode seekFaNode(String d,TreeNode startNode) {
      	if(startNode == null) {
       		return null;
     	 }
      	TreeNode seekNode = startNode;
     	 if(seekNode.getData().equals(d)) {
       		return seekNode;
      	}else {
       		//遍历左孩子，若返回值不为空，表示查找到
      		 if((seekNode=seekFaNode(d, startNode.getLeChild()))!= null){
        			return seekNode;
       		}
       		//遍历右孩子
      		if((seekNode=seekFaNode(d, startNode.getRiChild()))!= null) {
       			 return seekNode;
       		}
      	}
      //未查找到
      return null;
     }

③测试主函数

public static void main(String[] args) {
      	String[][] data = {
       {"root",null,null},
             			  {"zhangsan","root","left"},
            			 {"lisi","root","right"},
             			 {"wangwu","zhangsan","left"}};
      	CreateBinary cBinary = new CreateBinary();
      	cBinary.CreateTree(data);
     }

④我用DEBUG查看了变量内存  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200224225426723.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200224225532890.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200224225639837.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200224230758125.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODkxODA1,size_16,color_FFFFFF,t_70