首页 > 代码库 > 二叉树

二叉树

2024-07-17 05:43:00   226人阅读

二叉树相关概念：

  1. 路径：对于节点n1 n2 n3….nk从n1到nk的路径长度为k-1
  2. 节点的层数：只有一个根节点，则层数为1，其余节点的层数为双亲节点的层数加1
  3. 树的深度：树中所有节点的最大层数称为树的深度，只有根节点深度为1。
  4. 满二叉树：所有分支节点存在左子树和右子树，并且所有的叶子节点都在同一层上。
  5. 完全二叉树：对于树中的节点从上至下、从左到右顺序进行编号，且与满二叉树的位置编号相同。完全二叉树特点：叶子节点只能出现在最下层和次下层，且最下层的叶子节点集中在树的左边，满二叉树肯定是完全二叉树，反之不一定。如果完全二叉树中子节点个数分别为0、1、2的节点数分别用n0 n1 n2表示，节点总数n=n0+n1=n2,且n1只能为0或者1。

二叉树相关性质：

  1. 一颗深度为k的二叉树中，最多有2的k次方-1个节点（满二叉树），最少有k个节点
  2. 对于一颗非空二叉树，度为0的节点总是比度为2的几点多一个，即：n0=n2+1;
  3. 具有n个节点的完全二叉树的深度为【logn】+1，【】为向下取整；
  4. 对于n个节点从1开始编号的完全二叉树，对于节点编号i的节点：

　　　　（1）如果2i<=n，则序号为i的节点的左孩子节点的序号为2i；如果2i>n，则序号为i的节点无左孩子;

　　　    (2)如果2i+1<=n,则i节点有孩子序号为2i+1，如果2i+1>n,则i无右孩子。

                                                                                                                                                                 

二叉树的遍历：

　　1、先序遍历：先序遍历是先输出根节点，再输出左子树，最后输出右子树。上图的先序遍历结果就是：ABCDEF

　　2、中序遍历：中序遍历是先输出左子树，再输出根节点，最后输出右子树。上图的中序遍历结果就是：CBDAEF

　　3、后序遍历：后序遍历是先输出左子树，再输出右子树，最后输出根节点。上图的后序遍历结果就是：CDBFEA

#include <stdio.h> #include <stdlib.h> typedef char TelemType;         typedef struct TNode{         TelemType data;         struct TNode *lchild,*rchild; } BitNode; //声明BitNode* createTree(void); void preOrderTraverse(BitNode *); void inOrderTraverse(BitNode *);void lastOrderTraverse(BitNode *);int main(int agrc,char *argv[]){         BitNode *root=NULL;         root=createTree();           printf("\n先序遍历二叉树:");         preOrderTraverse(root);         printf("\n中序遍历二叉树:");         inOrderTraverse(root);        printf("\n后序遍历二叉树:");        lastOrderTraverse(root);              return 0; }//创建二叉树 BitNode* createTree(void){         BitNode *b;         TelemType ch;         scanf("%c",&ch);         if(ch==‘#‘)    {                b=NULL;         }    else    {                 b=(BitNode *)malloc(sizeof(BitNode));        b->data=http://www.mamicode.com/ch;        b->lchild=createTree();        b->rchild=createTree();    }                 return b;}  //先序遍历 void preOrderTraverse(BitNode *root){     if(root)    {                 printf("%c",root->data);        preOrderTraverse(root->lchild);        preOrderTraverse(root->rchild);     } }//中序遍历 void inOrderTraverse(BitNode *root){         if(root)    {                 inOrderTraverse(root->lchild);        printf("%c",root->data);        inOrderTraverse(root->rchild);    } }         //后序遍历 void lastOrderTraverse(BitNode *root){         if(root)    {                 lastOrderTraverse(root->lchild);        lastOrderTraverse(root->rchild);        printf("%c",root->data);         } }

 输出结果如下图：


联系
我们