二叉树的详细实现 (含递归展开图)

作者：lovevivi

2022-10-23
吉林
本文字数：1329 字
阅读完需：约 4 分钟

@TOC

一、二叉树

1. 概念

一颗二叉树是结点的有限集合，该集合或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树的组成

2.特点

每个结点最多有两棵子树，即二叉树不存在大于 2 的结点二叉树的子树有左右之分其子树次序不能颠倒

3.特殊二叉树

1.满二叉树

一个二叉树，如果每一个层的结点都达到最大值，则这个二叉树就是满二叉树，也就是说如果一个二叉树的层数为 k,结点总数为(2^k)-1，则就为满二叉树

2.完全二叉树

对于深度为 k 的，有 n 个结点的二叉树，且仅当其每一个结点与深度为 k 的满二叉树中编号从 1 到 n 的结点，称为完全二叉树

4.性质

性质 1.

若规定根节点的层数为 1，则一颗非空二叉树的第 i 层上最多有 2^(i-1)个结点

性质 2.

若规定根节点的层数为 1，则深度为 h 的二叉树的最大结点数是(2^h)-1

性质 3.

对于任何一颗二叉树，如果度为 0 其叶结点个数为 n0,度为 2 的分支节点个数为 n2,则 n0=n2+1(有几个子树，度就为多少)

性质 4.

若规定根节点的层数为 1，具有 n 个结点的满二叉树的深度 h=log N2^h -1=N2^h=N+1h= log 2 N+1 但是由于大 O 渐进表示法的省略，时间复杂度化成 O(log N)不太懂大 O 渐进表示法的 :时间复杂度与空间复杂度

二、二叉树整体实现

1.前序的实现

void  prevorder(BTnode* root)//前序  根 左子树 右子树{  if (root == NULL)  {    printf("NULL ");    return;  }  printf("%c ", root->data);  prevorder(root->left);  prevorder(root->right);}

复制代码

递归展开图

2.中序的实现

void  inorder(BTnode* root)//中序 左子树 根 右子树{  if (root == NULL)  {    printf("NULL ");    return;  }  inorder(root->left);  printf("%c ", root->data);  inorder(root->right);}

复制代码

递归展开图

3.后序的实现

void  postorder(BTnode* root)//后序 左子树 右子树 根{  if (root == NULL)  {    printf("NULL ");    return;  }  postorder(root->left);  postorder(root->right);  printf("%c ", root->data);}

复制代码

递归展开图

4. 节点个数

int treesize(BTnode* root)//节点个数{  if (root == NULL)  {    return 0;  }  return treesize(root->left) + treesize(root->right) + 1;}

复制代码

递归展开图

5. 叶节点个数

int treeleafsize(BTnode* root)//叶子节点的个数{  if (root == NULL)  {    return 0;  }  if (root->left == NULL && root->right == NULL)//只有当左右子树都为NULL时才会返回1  {    return  1;  }   return treeleafsize(root->left)+ treeleafsize(root->right);}

复制代码

递归展开图

6.层序遍历

void levelorder(BTnode* root)//层序遍历 需要借助数据结构栈来实现{  queue q;  queueinit(&q);//初始化栈  if (root)  {    queuepush(&q, root);//将根结点入栈  }  while (!queueempty(&q))  {     datatype front=queuefront(&q);//出栈     queuepop(&q);//删除栈顶元素     printf("%c ", front->data);     if (front->left != NULL)     {       queuepush(&q, front->left);//判断此时该结点的左子树是否为空 若不空则入栈     }     if (front->right != NULL)     {       queuepush(&q, front->right);//判断此时该结点的右子树是否为空 若不空则入栈     }  }  queuedestroy(&q);//销毁内存}

复制代码

发布于: 刚刚阅读数: 3

原文链接:【http://xie.infoq.cn/article/8e769060efb11c7a02da6af46】。文章转载请联系作者。

lovevivi

关注

还未添加个人签名 2022-10-12 加入

还未添加个人简介

发布

暂无评论

创作场景

二叉树的详细实现 (含递归展开图)

一、二叉树

1. 概念

2.特点

3.特殊二叉树

1.满二叉树

2.完全二叉树

4.性质

性质 1.

性质 2.

性质 3.

性质 4.

二、二叉树整体实现

1.前序的实现

递归展开图

2.中序的实现

递归展开图

3.后序的实现

递归展开图

4. 节点个数

递归展开图

5. 叶节点个数

递归展开图

6.层序遍历

lovevivi

评论