数据结构学习-二叉树

一、基本概念

每个结点最多有两棵子树，左子树和右子树。

二、普通二叉树

• 非空二叉树的第n层上至多有2^(n-1)个元素。
• 深度为h的二叉树至多有2^h-1个结点。

三、满二叉树

所有终端都在同一层次，且非终端结点的度数为2。
在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。

四、完全二叉树

除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。

对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。

五、二叉树的遍历

遍历二叉树的所有结点且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。

前序遍历：根节点->左子树->右子树（根节点在前面）
中序遍历：左子树->根节点->右子树（根节点在中间）
后序遍历：左子树->右子树->根节点（根节点在后边）

六、代码实现

• 辅助函数

  //节点数据结构
  typedef struct BinNode{
      int data;
      struct BinNode* lchild;
      struct BinNode* rchild;
  }BinNode;
  
  //栈数据结构
  #define SIZE 100
  typedef struct SeqStack{
      BinNode* data[SIZE];
      int tag[SIZE];   //为后续遍历准备的
      int top;     //top为数组的下标
  }SeqStack;
  
  //入栈操作
  void push(SeqStack *s,BinNode* t){
  
      if(s->top == SIZE){
          printf("the stack is full\n");
      }else{
          s->top++;
          s->data[s->top]=t;
      }
  }
  
  //出栈操作
  BinNode* pop(SeqStack *s){
  
      if(s->top == -1){
          return NULL;
      }else{
          s->top--;
          return s->data[s->top+1];
      }
  }
  

• 递归实现

  /**递归方式遍历**/
  //前序递归遍历
  void preOrder(BinNode *root)
  {
      if (root != NULL)
      {
          printf("%d->", root->data);
          preOrder(root->lchild);
          preOrder(root->rchild);
      }
  }
  
  //中序递归遍历
  void inOrder(BinNode *root)
  {
      if (root != NULL)
      {
          inOrder(root->lchild);
          printf("%d->", root->data);
          inOrder(root->rchild);
      }
  }
  
  //后序递归遍历
  void postOrder(BinNode *root)
  {
      if (root != NULL)
      {
          postOrder(root->lchild);
          postOrder(root->rchild);
          printf("%d->",root->data);
      }
  }
  

• 非递归实现

  //前序递归遍历
  void preOrder_dev(BinNode* t){
  
      SeqStack s;
      s.top = -1;     //因为top在这里表示了数组中的位置，所以空为-1
      if(!t){
          printf("the tree is empty\n");
      }else{
          while(t || s.top != -1){
              while(t){    //只要结点不为空就应该入栈保存，与其左右结点无关
                  printf("%d->",t->data);
                  push(&s,t);
                  t= t->lchild;
              }
              t=pop(&s);
              t=t->rchild;
          }
      }
  }
  
  //中序递归遍历
  void inOrder_dev(BinNode* t){
      SeqStack s;
      s.top = -1;
      if(!t){
          printf("the tree is empty!\n");
      }else{
          while(t ||s.top != -1){
              while(t){
                  push(&s,t);
                  t= t->lchild;
              }
              t=pop(&s);
              printf("%d->",t->data);
              t=t->rchild;
          }
      }
  }
  
  //后序递归遍历
  void postOrder_dev(BinNode* t){
      SeqStack s;
      s.top = -1;
      if(!t){
          printf("the tree is empty!\n");
      }else{
          while(t || s.top != -1){    //栈空了的同时t也为空。
              while(t){
                  push(&s,t);
                  s.tag[s.top] = 0;   //设置访问标记，0为第一次访问，1为第二次访问
                  t= t->lchild;
              }
              if(s.tag[s.top] == 0){  //第一次访问时，转向同层右结点
                  t= s.data[s.top];   //左走到底时t是为空的，必须有这步！
                  s.tag[s.top]=1;
                  t=t->rchild;
              }else {
                  while (s.tag[s.top] == 1){ //找到栈中下一个第一次访问的结点，退出循环时并没有pop所以为其左子结点
                      t = pop(&s);
                      printf("%d->",t->data);
                  }
                  t = NULL; //必须将t置空。跳过向左走，直接向右走
              }
          }
      }
  }
  

• 测试验证

  BinNode *root = (BinNode*)malloc(sizeof(BinNode));
  creatBiTree(&root);
    
  preOrder(root);
  printf("\n");
  inOrder(root);
  printf("\n");
  postOrder(root);
  printf("\n");
    
  preOrder_dev(root);
  printf("\n");
  inOrder_dev(root);
  printf("\n");
  postOrder_dev(root);
  printf("\n");
  

结果.png