[数据结构与算法]二叉树(二叉链表）

定义

n个结点的有限集合 由一个根节点以及两棵互不相交的 分别称为左子树 和 右子树的二叉树组成

逻辑结构

一对二

基本特征

每个结点最多只有两棵子树（不存在大于2的结点）
左子树和右子树次序不能颠倒

基本形态

性质

1） 二叉树的第i层上 至多有2的i-1次方个结点
2）深度为K的二叉树至多有2的K次方-1个结点
3）对于二叉树 2度的结点数有n个 则叶子有n+1个
4）具有n个结点的完全二叉树 其深度必为以二为底n的对数+1
5） 对完全二叉树 从上到下 从左到右 编号 则编号为i的结点 其左孩子编号 必为2i 右孩子编号必为2i+1
其双亲的编号必为i/2

二叉链表法

typedef struct BiTNode
{
   int data;
   struct BiTNode *lchild,*rchild; //左右孩子指针
}BiTNode,*BiTree;
void main()
{
 /* BiTNode t1,t2,t3,t4,t5;
  t1.data=1;
  t2.data=2;
  t3.data=3;
  t4.data=4;
  t5.data=5;
  
  t1.lchild=&t2;
  t1.rchild=&t3;
  t2.lchild=&t4;
  t3.lchild=&t5;
  */
  BiTNode *p1,*p2,*p3,*p4,*p5;
  p1->data=1;
  p2->data=2;
  p3->data=3;
  p4->data=4;
  p5->data=5;
  
  p1->lchild = p2;
  p1->rchild = p3;
  p2->lchild = p4;
  p3->lchild = p5;
  
}