資料結構（C語言版）---二叉樹

1、二叉樹：任意一個結點的子結點個數最多兩個，且子結點的位置不可更改，二叉樹的子樹有左右之分，

1）分類：
（1）一般二叉樹
（2）滿二叉樹：在不增加樹的層數的前提下，無法再多添加一個結點的二叉樹就是滿二叉樹，
（3）完全二叉樹：如果只是洗掉了滿二叉樹最底層最右邊的連續的若干個結點，這樣形成的二叉樹就是完全二叉樹，

（4）二叉排序樹：左子樹上所有結點的關鍵字均小于根結點的關鍵字，右子樹上的所有結點的關鍵字均大于根結點的關鍵字，

（5）平衡二叉樹：樹上任一結點的左子樹和右子樹的深度之差不超過1，

2）性質：

（1）在二叉樹的第i層上至多有2^i-1個結點（i>=1)，

（2）深度為k的二叉樹至多有2^k-1個結點(k>=1)，

（3）對任何一棵二叉樹T，如果其終端結點數為n₀，度為2的結點數為n₂，則n₀=n₂+1，

（4）具有n個結點的完全二叉樹的深度為log₂n+1，

（5）如果對一棵有n個結點的完全二叉樹（深度為log₂n+1）的結點按層序編號（從第1層到第log₂n+1層，每層從左到右），則對任一結點i(1<=i<=n)，有

          如果i=1，則結點i是二叉樹的根，無雙親；如果i>1，則其雙親Parent(i)是結點i/2；

          如果2i>n，則結點i無左孩子（結點i為葉子結點）；否則其左孩子LeftChild(i)是結點2i；

          如果2i+1>n，則結點i無右孩子；否則其右孩子LRightChild(i)是結點2i+1，

3）二叉樹和度為2的有序樹的區別：

（1）度為2 的樹至少有3個結點，而二叉樹為空，

（2）度為2的有序樹的孩子結點的左右次序是相對于另一個孩子結點而言的，

4）存盤
（1）順序存盤【完全二叉樹】：用一組地址連續的存盤單元依次自上而下、自左至右存盤完全二叉樹上的結點元素，
                 優點：查找某個節點的父節點和子節點速度很快（也包括判斷有沒有子節點），
                 缺點：耗用記憶體空間，
（2）鏈式存盤：用一個鏈表來存盤二叉樹，設定不同的指標域，二叉鏈表至少包含3個指標域：資料域、左指標域、右指標域，

5）遍歷
（1）先序遍歷
                先訪問根結點、再先序訪問左子樹、再先序訪問右子樹，
（2）中序遍歷
                先中序遍歷左子樹、再訪問根結點、再中序遍歷右子樹，
（3）后序遍歷
                先后序遍歷右子樹、再后序遍歷左子樹、再訪問根結點，

6）已知兩種遍歷序列求原始二叉樹
             通過先序和中序、中序和后序都可以還原出原始的二叉樹，但是通過先序和后序無法還原出原始的二叉樹，

2、線索鏈表

ltag=0,lchild域指示結點的左孩子；ltag=1,lchild域指示結點的前驅，

rtag=0,rchild域指示結點的右孩子；rtag=1,rchild域指示結點的后繼，

1）線索：指向結點前驅和后繼的指標，

2）線索二叉樹：加上線索的二叉樹，

3）線索化：對二叉樹以某種次序遍歷使其變成線索二叉樹的程序，

3、二叉排序樹（BST）（二叉查找樹）

1）性質：左子樹為空，則左子樹上所有結點關鍵字值均小于根結點的關鍵字值，

           右子樹為空，則右子樹上所有結點關鍵字值均大于根結點的關鍵字值，

           左右子樹本身也是一棵二叉排序樹，

2）左子樹結點值<根結點值<右子樹結點值，進行中序遍歷時，可以得到遞增的有序序列，

3）二叉排序樹的洗掉

（1）洗掉結點為葉結點，則直接洗掉，

（2）若結點只有一棵左子樹或右子樹，則讓該結點的子樹成為該結點父結點的子樹，

（3）若結點有左右兩棵子樹，則令該結點的直接后繼（直接前驅）替代該結點，洗掉直接后繼（直接前驅），

4）只有左（右）孩子的單支樹的二叉排序樹，平均查找長度為O(n)，

5）左、右子樹的高度差的絕對值不超過1的二叉排序樹，即平衡二叉樹，平均查找長度為O(log₂n)，

4、平衡二叉樹(AVL)

1）平衡因子：左子樹與右子樹的高度差，平衡二叉樹結點的平衡因子的值只可能是-1、0、1.

2）性質：左右子樹都是平衡二叉樹，且左右子樹的高度差的絕對值不超過1

5、二叉樹的基本操作

1）InitBiTree(&T)：構造空樹

2）DestroyBiTree(&T)：銷毀樹

3）CreateBiTree(&T,definition)：按definition構造樹

4）ClearBiTree(&T)：清空樹

5）BiTreeEmpty(T)：判斷樹是否為空

6）BiTreeDepth(T)：回傳樹的深度

7）Root(T)：回傳樹的根

8）Value(T,cur_e)：回傳結點cur_e的值

9）Assign(T,cur_e,value)：將結點cur_e賦值為value

10）Parent(T,cur_e)：若cur_e為非根節點，則回傳雙親，否則函式值為空

11）LeftChild(T,cur_e)：若cur_e為非葉子結點，則回傳左孩子，否則函式值為空

12）RightChild(T,cur_e)：若cur_e為非葉子結點，則回傳右孩子，否則函式值為空

13）LeftSibling(T,cur_e)：若cur_e有左兄弟，則回傳，否則函式值為空

14）RightSibling(T,cur_e)：若cur_e有右兄弟，則回傳，否則函式值為空

15）InsertChild(&T,&p,i,e)：插入c為T中p所指結點的第i棵子樹

16）DeleteChild(&T,&p,i)：洗掉T中p所指結點的第i棵子樹

6、二叉樹的順序存盤結構型別描述
#define Maxsize 100
typedef int SqBiTree[Maxsize];
7、在二叉樹中查找結點i和結點j的最近公共祖先結點
int commancestor(SqBiTree T, int i, int j)
{
 if (T[i] != '#'&&T[j] != '#')
 {
  while (i!=j)
  {
   if (i > j)
   {
    i = i / 2;
   }
   else
   {
    j = j / 2;
   }
  }
  return T[i];
 }
}

8、二叉樹的鏈式存盤結構型別描述
typedef struct BiTNode {
 int data;
 struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;
9、此部分程式中涉及到堆疊和佇列的部分在前面幾篇中提到，在這里就不詳細給出咯，

1）先序遍歷
void preorder(BiTree T)
{
 if (T != NULL)
 {
  visit(T);
  preorder(T->lchild);
  preorder(T->rchild);
 }
}
2）中序遍歷
void inorder(BiTree T)
{
 if (T != NULL)
 {
  inorder(T->lchild);
  visit(T);
  inorder(T->rchild);
 }
}
3）中序遍歷利用堆疊
void inorder1(BiTree T)
{
 Sqstack S;
 initstack(S);
 BiTree p = T;
 while (p||!stackempty(S))
 {
  if (p)
  {
   push(S, p->data);
   p = p->lchild;
  }
  else
  {
   pop(S, p->data);
   visit(p);
   p = p->rchild;
  }
 }
}
4）后序遍歷
void postorder(BiTree T)
{
 if (T != NULL)
 {
  postorder(T->lchild);
  postorder(T->rchild);
  visit(T);
 }
}
5）后序遍歷非遞回
void postorder1(BiTree T)
{
 Sqstack S;
 BiTNode *r,*p;
 //BiTree p;
 initstack(S);
 p = T;
 r = NULL;
 while (p||!stackempty(S))
 {
  if (p)
  {
   push(S, p->data);
   p = p->lchild;
  }
  else
  {
   pop(S, p->data);
   if (p->rchild&&p->rchild != r)
   {
    p = p->rchild;
    push(S, p->data);
    p = p->lchild;
   }
   else
   {
    pop(S, p->data);
    visit(p);
    r = p;
    p = NULL;
   }
  }
 }
}
6）層序遍歷
void levelorder(BiTree T)
{
 Sqstack S;
 SqQueue Q;
 initqueue(Q);
 initstack(S);
 if(T!=NULL)
 {
  enqueue(Q, T->data);
  while (!queueempty(Q))
  {
   dequeue(Q,T->data);
   push(S, T->data);
   if (T->lchild != NULL)
   {
    enqueue(Q, T->lchild->data);
   }
   if (T->rchild != NULL)
   {
    enqueue(Q, T->rchild->data);
   }
  }
  while (!stackempty(S))
  {
   pop(S, T->data);
   visit1(T->data);
  }
 }
}

10、二叉排序樹非遞回演算法
BiTNode *bstsearch(BiTree T, int key, BiTNode *&p)
{
 p = NULL;
 while (T!=NULL&&key!=T->data)
 {
  p = T;
  if (key < T->data)
  {
   T = T->lchild;
  }
  else
  {
   T = T->rchild;
  }
 }
 return T;
}
11、二叉排序樹的插入
int bstinsert(BiTree &T, int k)
{
 if (T == NULL)
 {
  T = (BiTree)malloc(sizeof(BiTNode));
  T->data = https://www.cnblogs.com/xqy1874/p/k;
  T->lchild = T->rchild = NULL;
  return 1;
 }
 else if (k == T->data)
 {
  return 0;
 }
 else if (k < T->data)
 {
  return bstinsert(T->lchild, k);
 }
 else
 {
  return bstinsert(T->rchild, k);
 }
}
12、二叉排序樹的構造
void bstcreate(BiTree &T, int str[], int n)
{
 T = NULL;
 int i = 0;
 while (i<n)
 {
  bstinsert(T, str[i]);
  i++;
 }
}

13、線索二叉樹的存盤結構
typedef struct ThreadNode {
 int data;
 struct ThreadNode *lchild, *rchild;
 int ltag, rtag;
}ThreadNode,*ThreadTree;
void visit(ThreadTree T)
{
 printf("遍歷樹");
 return;
}
1）求中序線索二叉樹中中序序列下的第一個結點
ThreadNode *firstnode(ThreadNode *p)
{
 while (p->ltag==0)
 {
  p = p->lchild;
 }
 return p;
}
2）求中序線索二叉樹中結點p在中序序列下的后繼結點
ThreadNode *nextnode(ThreadNode *p)
{
 if (p->rtag == 0)
 {
  return firstnode(p->rchild);
 }
 else
 {
  return p->rchild;
 }
}
3）不含頭結點的中序線索二叉樹的中序遍歷
void inorder(ThreadNode *p)
{
 for (ThreadNode *t = firstnode(p); t != NULL; t = nextnode(p))
 {
  visit(p);
 }
}
4）中序遍歷對二叉樹線索化的遞回演算法
void inthread(ThreadTree &t, ThreadTree &pre)
{
 if (t != NULL)
 {
  inthread(t->lchild, pre);
  if (t->lchild == NULL)
  {
   t->lchild = pre;
   t->ltag = 1;
  }
  if (pre != NULL && pre->rchild == NULL)
  {
   pre->rchild = t;
   pre->rtag = 1;
  }
  pre = t;
  inthread(t->rchild, pre);
 }
}
5）中序遍歷建立中序線索二叉樹
void createinthread(ThreadTree T)
{
 ThreadTree pre = NULL;
 if (T != NULL)
 {
  inthread(T, pre);
  pre->rchild = NULL;
  pre->rtag = 1;
 }
}

標籤：其他

上一篇：剪繩子

下一篇：滑動視窗的最大值