资讯详情

二叉树基本知识

树与二叉树

二叉树是一棵有序的树。如果左右子树被逆转,它将成为另一棵不同的二叉树。即使树的节点只有一棵子树,也要区分它是左子树还是右子树。

特殊二叉树:

  1. 满二叉树:一棵高度为:h,且含有2h-一个节点的二叉树成为满二叉树,即树内每层节点最多。

2. 完全二叉树:如果将最后一层节点从二叉树中去除,最后一层节点从左到右分布,则称为完全二叉树。

  • 若i < ? n / 2 ? \lfloor n/2 \rfloor ?n/2? ,节点I为分支节点,否则为叶结点
  • 叶结点只能出现在最大层次的两层。最大层次的叶结点依次排列在该层最左边的位置
  • 如果有1度的节点,只能有一个节点,只有左孩子,没有右孩子
  • 按层序编号后,一旦出现节点(编号为i)为叶子结点或只有左孩子,则编号大于i的节点均为叶子结点
  • 若n为奇数,则每个分支节点都有左孩子和右孩子;若n为偶数,则最大节点(编号为n/2)只有左孩子,没有右孩子,左右孩子有其他分支节点。
  1. 二叉排序树:左树上所有节点的关键字都小于节点的关键字;右树上所有节点的关键字都大于节点的关键字;左右树是二叉排序树
  2. 平衡二叉树:树上任何节点左右树的深度差不超过1

二叉树的储存结构

二叉树的顺序存储是指一组地址连续存储单元从上到下,从左到右存储完全二叉树上的节点元素,即将完全二叉树上的节点元素存储在一维数组下标记为i的重量中 根据二叉树的性质,完全二叉树和满二叉树更适合顺序存放。

链式存储,用链表完成二叉树的存储。

二叉树遍历

二叉树的遍历是指根据搜索路径访问树中的每个节点,使每个节点被访问一次,只访问一次。 常见的遍历顺序:先序(NLR),中序(LNR),后序(LRN)

///先序遍历 void PreOrder(BiTree T){ 
          if(T != NULL){ 
           visit(T);   PreOrder(T->lchild);   PreOrder(T->rchild);  } } ///中序遍历 void InOrder(BiTree T){ 
          if(T != NULL){ 
           InOrder(T->lchild);   visit(T);   InOrder(T->rchild);  } }  ///后序遍历 void PostOrder(BiTree T){ 
          if(T != NULL){ 
           PostOrder(T-&g;lchild);
		PostOrder(T->rchild);
		visit(T);
	}
}

由二叉树的先序序列和中序序列可以唯一确定一棵二叉树; 由二叉树的后序序列和中序序列可以唯一确定一棵二叉树;

线索二叉树

作用:加速二叉树的遍历 规定:若无左子树,令lchild指向其前驱节点;若无右子树,令rchild指向其后继节点。 再增加两个标志域标识指针域是指向左(右)孩子还是前驱(后继)

标签: 螺栓二极管nlr506xxld

锐单商城拥有海量元器件数据手册IC替代型号,打造 电子元器件IC百科大全!

锐单商城 - 一站式电子元器件采购平台