数据结构(C语言版)---二叉树

1、二叉树:任意一个结点的子结点个数最多两个,且子结点的位置不可更改,二叉树的子树有左右之分。

1)分类:
(1)一般二叉树
(2)满二叉树:在不增加树的层数的前提下,无法再多添加一个结点的二叉树就是满二叉树。
(3)完全二叉树:如果只是删除了满二叉树最底层最右边的连续的若干个结点,这样形成的二叉树就是完全二叉树。

(4)二叉排序树:左子树上所有结点的关键字均小于根结点的关键字,右子树上的所有结点的关键字均大于根结点的关键字。

(5)平衡二叉树:树上任一结点的左子树和右子树的深度之差不超过1。

2)性质:

(1)在二叉树的第i层上至多有2i-1个结点(i>=1)。

(2)深度为k的二叉树至多有2k-1个结点(k>=1)。

(3)对任何一棵二叉树T,如果其终端结点数为n0,度为2的结点数为n2,则n0=n2+1。

(4)具有n个结点的完全二叉树的深度为log2n+1。

(5)如果对一棵有n个结点的完全二叉树(深度为log2n+1)的结点按层序编号(从第1层到第log2n+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、线索链表

lchildltagdatartagrchild

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(log2n)。

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 = 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;
 }
}

相关推荐