二叉树遍历算法的应用 c语言实现-按字符生成二叉链表、复制二叉树、计算深度、统计结点个数

二叉树遍历操作是二叉树各种操作的基础,二叉树的遍历详见二叉树的遍历 (前序 中序 后序) 递归&非递归。通过结点的递归遍历可以实现很多功能
这里使用的二叉树的存储结构见 二叉树的链式存储结构 C语言实现

先序遍历顺序建立二叉链表

假设二叉树结点里的元素均为一个单字符,则可以用先序排列的字符串直接生成二叉树。依次读入字符,从根节点开始,递归建立二叉树。

//@param T-要生成的二叉树根结点指针
void CreatBiTree(BiTNode* T) {
    char ch = getchar();
    if (ch == '#') T = NULL;
    else {
        T = InitBiTree(ch);
        CreatBiTree(T->lchild);
        CreatBiTree(T->rchild);
    }
}

也可以通过中序和后序生成二叉树,只需调整递归的顺序即可。

复制二叉树

如果是空树,递归结束,否则执行先序递归

  • 构造新节点,复制根节点
  • 递归复制左子树
  • 递归复制右子树
//@param T-被复制的二叉树根节点指针
//@param NewT-复制后的二叉树根节点指针
void Copy(BiTNode* T, BiTNode* NewT) {
    if (T == NULL) {
        NewT == NULL;
    }
    else {
        NewT = InitBiTree(T->Data);
        Copy(T->lchild, NewT->lchild);
        Copy(T->rchild, NewT->rchild);
    }
}

计算二叉树的深度

如果是空树,递归结束,否则执行后序递归

  • 递归计算左子树深度为m
  • 递归计算右子树深度为n
  • 如果m大于n,二叉树深度为m+1,否则为n+1
//@param T-二叉树根节点指针
int Depth(BiTNode* T) {
    if (T == NULL) return 0;
    else {
        int m = Depth(T->lchild);
        int n = Depth(T->rchild);
        if (m > n) return(m + 1);
        else return(n + 1);
    }
}

统计二叉树中结点的个数

int NodeCount(BiTNode* T) {
    if (T == NULL) return 0;
    else return NodeCount(T->lchild) + NodeCount(T->rchild) + 1;
}
Muyoo

Muyoo

留下你的评论