数据结构-树

树，二叉树的定义：

二叉树是N个节点的有效集，二叉树与无序数不同，二叉树每个节点只有两个子树。

二叉树的性质：

• 二叉树的第i层最多有2的i-1次方个节点。
• 二叉树最多有2的i次方减一个节点。
• 在任意一个二叉树中，若叶子节点的个数为n，有两个子树的节点为n0，则有n=n0+1。

二叉树的两种形式：满二叉树与完全二叉树

• 满二叉树：
  满二叉树的每一个节点都有两个子树。除最下一层外不存在度数为一的节点。
  n层的满二叉树，节点数为2的k次方减一。
• 完全二叉树：
  完全二叉树的节点完全按照从上往下从左到右的顺序填补。
  最后一层总是在右部分空缺的树。
  完全二叉树是满二叉树。满二叉树不一定是完全二叉树。

二叉树的存储结构：

1. 顺序存储结构
2. 链式存储结构

二叉树的遍历：

• 遍历方案 ：(简单的递归遍历)

1. 中序遍历(InorderTraversal):

    typedef node* BinTree；
    void LNR (BinTree t){
       if (t) {
         LNR (t->left);  
         printf ("%d",t->date);
         LNR (t->right);
       }
    }
   

2. 前序遍历(PreorderTraversal):
   void NLR (BinTree t){
   if (t) {
   printf ("%d",t->date);
   NLR (t->left);
   NLR (t->right);
   }
   }

3. 后序遍历(PostorderTraversal):
   void LRN (BinTree t){
   if (t) {
   LRN (t->left);
   LRN (t->right);
   printf ("%d",t->date);
   }
   }

二叉树链式存储的构造：

• 构造运算：（前序构造）

      void creatBinTree (BinTree \*t) {//t为指向指针的指针，修改\*t既为修改指针
          char temp;//定义一个存放数据的字符型数据
          temp=getchar();
          if (temp == '')
          \*t = NULL;
          else 
          \*t = (BinTree *)malloc(sizeof(BinTree));  //生成节点
          (\*t)->date = temp;
          creatBinTree (&(\*t)->left);
          creatBinTree (&(\*t)->right);
          }
      }
      //此函数的实参为根地址的地址
  

线索二叉树：

• 定义:
  具有 n 个结点的二叉链表中，其二叉链表的 n 个结点*有 2n 个指针域，在这 2n 个指针域中，真正用于指向后件（左子结点或右子结点）的指针域只有 n-1 个，而另外的 n+1 个指针域都是空的。这样就利用二叉链表中的空指针域，存放指向结点在某种遍历次序下的前趋和后继结点的指针（这种附加的指针称为 " 线索 " ），这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树
  根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后序线索二叉树三种。
  • 注意：线索链表解决了二叉链表找左、右孩子困难的问题，出现了无法直接找到该结点在某种遍历序列中的前趋和后继结点的问题。

---

部分内容引自下列blog及网站：
http://student.zjzk.cn/course_ware/data_structure/web/main.htm
http://waret.iteye.com/blog/709779