初识二叉树

二叉树

1. 二叉树的定义 二叉树是结点的有限集合，该集合或者为空集，或者由一个根和它互不相交的、同为二叉树的左子树和右子树组成。

   特殊二叉树的定义

   • 高度为h的二叉树恰好有\(2^h-1\)个结点时称为满二叉树。
   • 一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下层的叶结点集中在靠左的若干位置上，这样的二叉树称为完全二叉树。
   • 不存在度为1的结点的二叉树称为扩充二叉树，又称为2-树。

2. 二叉树的性质

   1. 二叉树的第i层上最多有\(2^{i-1}\)个结点。
   2. 高度为h的二叉树上至多有\(2^h-1\)个结点。
   3. 包含n个结点的二叉树的高度至少为\(log_2{(n+1)}\),最高为n。
   4. 任意一棵二叉树中，若叶结点的数量为a，度为2的结点的数量为b,则a=b+1成立。
   5. 具有n个结点的完全二叉树的高度为\(log_2{(n-1)}\)。
   6. 一棵包含n个结点的完全二叉树，对树中的结点按从上到下、从左到右的顺序，从0到n-1编号，设树中某个结点的编号为i,则有以下关系成立：
      1. 当i=0时，该结点时二叉树的根；
      2. 若i>0，则该结点的双亲结点的编号为(i-1)/2；
      3. 若2i+1<n,则该结点有左孩子，该左孩子结点的编号为2i+1；
      4. 若2i+2<n,则该结点有右孩子，该右孩子结点的编号为2i+2。

3. 二叉树的存储实现和基本运算

   1. 二叉树结点结构体

      typedef struct btnode
      {
       ElemType element;
       struct btnode *lchild;
       struct btnode *rchild;
       }BTNode;

   2. 二叉树结构体

      typedef struct bianrytree
      {
         BTNode *root;
      }BianrTree;

   3. 部分二叉树运算

      void Create(BinaryTree *bt)
      {
         bt->root=NULL;
      } 
      BTNode* NewNode(ElemType x,BTNode *ln,BTNode *rn)
      {
         BTNode *p=(BTNode *)malloc(sizeof(BTNode));
         p->element=x;
         p->lchild=ln;
         p->rchild=rn;
         return p;
      }
      BOOL Root(BinaryTree *bt,ElemType *x)
      {
         if(bt->root)
         {
            x=&bt->root->element;
            return TRUE;
         }
         else
            return FALSE;
      }
      void MakeTree(BinaryTree *bt,ElemType e,BinaryTree *left,BinaryTree *right)
      {
         if(bt->root||left==right)
         return ;
         bt->root=NewNode(e,left->root,right->root);
         left->root=right->root=NULL;
      }