二叉树相关操作

二叉树建立与遍历

#include <bits/stdc++.h>
using namespace std;

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

void create(BTNode *&p){
  int i;
  scanf("%d", &i);
  if(i == 0)  p = NULL;
  else{
    p = (BTNode *)malloc(sizeof(BTNode));
    p -> data = i;
    create(p -> lchild);
    create(p -> rchild);
  }
}

void preOrder(BTNode *&root){
  if(root){
    printf("%d", root -> data);
    preOrder(root -> lchild);
    preOrder(root -> rchild);
  }
}

void InOrder(BTNode *&root){
  if(root){
    InOrder(root -> lchild);
    printf("%d", root -> data);
    InOrder(root -> rchild);
  }
}

void PostOrder(BTNode *&root){
  if(root){
    PostOrder(root -> lchild);
    PostOrder(root -> rchild);
    printf("%d", root -> data);
  }
}


int main(){
  BTNode *T = NULL;
  create(T);
  printf("\n先序遍历:");
  preOrder(T);
  printf("\n中序遍历:");
  InOrder(T);
  printf("\n后序遍历:");
  PostOrder(T);
  return 0;
}

数组存储的完全二叉树,以二叉链表表示

#include <bits/stdc++.h>
using namespace std;

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;

int a[100];

void create(BTNode *&p, int n, int i){
  if(i > n || a[i] == 0)  p = NULL; //a[i] = 0 为空节点
  else{
    p = (BTNode *)malloc(sizeof(BTNode));
    p -> data = a[i];
    create(p -> lchild, n, 2 * i);
    create(p -> rchild, n, 2 * i + 1);
  }
}

int main(){
  int n;
  scanf("%d", &n);
  for(int i = 1; i <= n; i ++)
    scanf("%d", &a[i]);
  BTNode *T = NULL;
  create(T, n, 1);
  return 0;
}

两节点的最近公共祖先

思路:
三种情况:

p和q都在左子树:
如果右子树没有p或q,则说明在左子树上。

p和q都在右子树:
如果左子树上没有p或q,则说明在右子树上。

p和q分别在左右子树:
如果左右子树都有p或q,则当前节点即为所求节点。

BTNode *lowerstCommonAncesor(BTNode *root, BTNode *p, BTNode *q){
  if(root == null || root == p || root == q){
    return root;
  }
  struct BTNode *left = lowerstCommonAncesor(root->lchild, p, q);
  struct BTNode *right = lowerstCommonAncesor(root->rchild, p, q);
  return left == NULL ? right : right == NULL ? left : root;
}

判断是否是二叉搜索树

思路:
左子树的节点的值都小于根的值
右子树的节点的值都大于根的值
不断维护每个节点的最小范围和最大范围递归即可

bool dfs(BTNode *root, int mi, int mx){
  if(root == null)  return true;
  if(root -> data <= mi || root -> data >= mx)  return false;
  return dfs(root -> left, mi, root -> data) || dfs(root -> right, root -> data, mx);
}

void IsValidBST(BTNode *root, int mi, int mx){
  dfs(root, INT_MIN, INT_MAX);
}

求二叉树的最大深度

不解释,直接dfs

int MaxDepth(BTNode *bt){
  if(bt == NULL)  return 0;
  int hl = 1;
  int hr = 1;
  if(bt -> lchild)  hl += MaxDepth(bt -> lchild);
  if(bt -> rchild)  hr += MaxDepth(bt -> rchild);
  return hl > hr ? hl : hr;
}

升序链表转化为平衡二叉树

找到链表的中位数,左右递归处理就可以了

typedef struct LNode{
  int data;
  struct LNode *next;
}LNode;

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode;


LNode *GetMid(LNode *left, LNode *right){
  LNode fast = left;
  LNode slow = left;
  while(fast != right && fast -> next != right){
    fast = fast -> next -> next;
    slow = slow -> next;
  }
  return slow;
}


BTNode *BuildTree(LNode *left, LNode *right){
  if(left == right) return NULL;
  LNode *mid = GetMid(left, right);
  BTNode *root = new(BTNode);
  root -> data = mid -> data;
  root -> left = BuildTree(left, mid);
  root -> right = BuildTree(mid -> next, right);
  return root;
}


BTNode *SortedListToBST(LNode *head){
  return BuildTree(head, NULL);
}

判断是否是平衡二叉树

平衡二叉树左右子数之差绝对值不超过2

int dfs(BTNode *root){
        if(root == NULL)    return 0;
        int left = dfs(root -> lchild);
        int right = dfs(root -> rchild);
        if(left != -1 && right != -1 && abs(left - right) < 2){
            return left > right ? left + 1 : right + 1;
        }
        else{
            return -1;
        }
    }

bool isBalanced(BTNode* root) {
      int ans = dfs(root);
      return ans == -1 ? false : true;
}

检查二叉树是否是镜像的

bool check(BTNode *p, BTNode *q){
       if(!p && !q)    return true;
       if(!p || !q)    return false;
       return p -> data == q -> data && check(p->lchild,q->rchild) && check(p->rchild,q->lchild);
}

bool isSymmetric(BTNode* root) {
       return check(root, root);
}

给定目标值,求二叉树上是否有一条到根节点到叶子路径上的值为目标值

bool hasPathSum(TreeNode* root, int targetSum) {
       if(root == NULL)    return NULL;
       if(root -> lchild == NULL && root -> rchild == NULL){
           return targetSum == root -> data;
       }
       return hasPathSum(root -> lchild, targetSum - root->data) || hasPathSum(root -> rchild, targetSum - root->data);
   }

求完全二叉树的节点个数

void dfs(TreeNode *root, int &cnt){
      if(root == NULL)    return ;
      cnt ++;
      dfs(root -> lchild, cnt);
      dfs(root -> rchild, cnt);
  }

int countNodes(TreeNode* root) {
      int cnt = 0;
      dfs(root, cnt);
      return cnt;
}

判断二叉树是完全二叉树

typedef struct BTNode{
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

bool completeBTree(BTNOde *bt){
  if(bt == NULL){
    return 0;
  }
  BinTree queue[maxsize];
  BinTree left, right;
  bool leaf = false;
  int front = 0, rear = 0;
  rear = (rear + 1) % maxsize;
  queue[rear] = bt;

  while(rear != front){
    front = (front + 1) % maxsize;
    p = queue[front];
    left = p -> lchild;
    right = p -> rchild;
    //当前节点有右孩子,但没有左孩子,直接返回false
    //当前节点有左孩子,但没有右孩子,则接下来所有节点必须都是叶子节点
    if((leaf && (leaf != NULL || right != NULL)) || (leaf = NULL && right != NULL)){
      return -1;
    }
    if(leaf != NULL){
      rear = (rear + 1) % maxsize;
      queue[rear] = left;
    }
    if(right != null){
      rear = (rear + 1) % maxsize;
      queue[rear] = right;
    }
    if(left == null || right == null){
      leaf = 1;
    }
  }
  return true;
}

二叉树的平衡因子

typedef struct BTNode{
  int bf;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

int height(BinTree bt){
  int l = 0, r = 0;
  if(bt == NULL)  return 0;
  l = height(bt -> lchild);//遍历左子树
  r = height(bt -> rchild);//遍历右子树
  return (l > r ? l : r) + 1;//左子树与右子树个数多的为当前树的深度
}

void balance(BinTree bt){
  int hl = 0;
  int hr = 0;//记录左右子树的度
  if(bt != NULL){
    balance(bt -> lchild); //从树的底部开始计算
    balance(bt -> rchild);
    hl = height(bt -> lchild);  //当前节点左子树的度
    hr = height(bt -> rchild);  //当前节点右子树的度
    bt -> bf = hl - hr; //当前节点的平衡因子
  }

求树的带权路径长度

方法一:先序遍历

typedef struct BTNode{
  int weight;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

int WPL(BinTree bt){
  return wpl_PreOrder(bt, 0);
}

int wpl_PreOrder(BinTree bt, int deep){
  static wpl = 0;
  if(bt -> lchild == NULL && bt -> rchild == NULL){
    wpl += deep * bt -> weight;
  }
  if(bt -> lchild != NULL)  wpl_PreOrder(bt -> lchild);
  if(bt -> rchild != NULL)  wpl_PreOrder(bt -> rchild);
}

方法二:层序遍历

typedef struct BTNode{
  int weight;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

int wpl_levelOrder(BinTree bt){
  int L = 0;  // 当前节点到根节点的距离
  int wpl = 0;
  BinTree p;
  BinTree queue[maxsize];
  int rear = 0, front = 0;

  rear = (rear + 1) % maxsize;
  queue[rear] = bt;

  while(rear != front){
    int len = (rear - front + 1) % maxsize;
    for(int i = 0; i < len; i ++){  //循环遍历每一层节点
      front = (front + 1) % maxsize;
      p = queue[front];
      if(p -> lchild == NULL && p -> rchild == NULL){
        wpl += p -> weight * L;
      }
      if(p -> lchild != NULL){
        rear = (rear + 1) % maxsize;
        q[rear] = p -> lchild;
      }
      if(p -> rchild != NULL){
        rear = (rear + 1) % maxsize;
        q[rear] = p -> rchild;
      }
    }
    L ++;
  }
  return wpl;
}

二叉树某节点的深度

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

void Elem_depth(BinTree T, int level, int *depth, int x){
  if(T != NULL){
    level ++;
    if(T -> data == x)  depth = level;
  }
  Elem_depth(T -> lchild, level, depth, x);
  Elem_depth(T -> rchild, level, depth, x);
}

二叉树指定节点的所在层数

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

int L = 1;

void Elem_level(BinTree T, int x){
  if(T != NULL){
    if(T -> data == x){
      cout << L << endl;
      return ;
    }
    L ++;
    Elem_level(T -> lchild, x);
    Elem_level(T -> rchild, x);
    L --;
  }
}

二叉树以x节点为根的子树高度

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

int Elem_Height(BinTree bt){
  int l, r;
  if(bt == NULL){
    return 0;
  }
  else{
    l = Elem_Height(bt -> lchild);
    r = Elem_Height(bt -> rchild);
    return (l > r ? l : r) + 1;
  }
}

void Elem_Height(BinTree bt, int x){
  if(bt != NULL){
    if(bt -> data == x){
      cout << getheight(bt) << endl;
    }
    Elem_Height(bt -> lchild);
    Elem_Height(bt -> rchild);
  }
}

判断是否是二叉排序树

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

bool IsBST(BinTree bt){
  if(bt == NULL)  return true;
  else if(bt -> rchild == NULL && bt -> lchild == NULL) return true;
  else if((bt -> lchild != NULL) && (bt -> rchild == NULL)){
    if(bt -> lchild -> data <= bt -> data)  return true;
    else  return IsBST(bt -> lchild);
  }
  else if((bt -> rchild != NULL) && (bt -> lchild == NULL)){
    if(bt -> rchild -> data >= bt -> data)  return true;
    else  return IsBST(bt -> rchild);
  }
  else{
    if(bt -> lchild -> data > bt -> data || bt -> rchild -> data < bt -> data){
      return false;
    }
    else{
      return IsBST(bt -> lchild) && IsBST(bt -> rchild);
    }
  }
}

两个二叉排序树合并成一个二叉排序树

先将一棵树按后序遍历顺序插入比较
比当前节点大则插入右子树且右子树为空
比当前节点小则插入左子树且左子树为空
不为空则继续向下遍历直到找到合适的位置

typedef struct BTNode{
  int data;
  struct BTNode *lchild;
  struct BTNode *rchild;
}BTNode, *BinTree;

void BiTree_Merge(BinTree &t, BiTree &s){//s合并到t中
  if(s->lchild){
    BiTree_Merge(t, s->lchild);
  }
  if(s->rchild){
    BiTree_Merge(t, s->rchild);
  }
  insert_Node(t, s);//后序遍历插入节点
}

void insert_Node(BiTree &t, BTNode *s){//把s树上节点合并到t树中
  if(s->data > t->data){//插入的节点大于当前节点,右子树查找位置
    if(t -> rchild == NULL){
      t -> rchild = s;
    }
    else{
      insert_Node(t->rchild, s)//否则继续向右递归
    }
  }
  else if(s->data < t->data){//插入的节点小于当前节点,左子树查找位置
    if(t -> lchild != NULL){
      t -> lchid = s;
    }
    else{
      insert_Node(t->lchild, s);//否则继续向左递归
    }
  }
  s -> rchild = NULL;//插入的新节点必须与原来节点断绝关系
  s -> lchild = NULL;
}
点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注