树与二叉树-zhynxq 博客

树与二叉树

一、树的基本概念

1.定义

树是一种非线性的数据结构。

树是若干节点的集合，是由唯一的根和若干棵互不相交的子树组成的；每一棵子树又是一课树，也是由唯一的根结点和若干棵互不相交的子树组成的。因此树的定义是递归的，即在树的定义中又用到了树的定义。

2、树的基本术语

**结点：**0、1、2、3等都是结点，结点包含数据元素以及指向子树的指针。

**结点的度：**结点拥有的子树个数或者分支的个数。

**树的度：**树中个各节点最大的度。

**叶子结点：**又叫终端结点，指度为0的结点。

**非终端结点：**又叫做分支结点，指度不为0的结点。除了根节点之外的的非终端结点，也叫做内部结点。

**孩子：**结点的子树的根。

**双亲：**与孩子的定义相对。

**兄弟：**同一个双亲的孩子之间互为兄弟。

**祖先：**从根到某结点的路径上的所有的结点，都是这个结点的祖先。

**子孙：**以某结点为根的子树中的所有的结点，都是该结点的子孙。

**层次：**以根开始，根为一层，根的孩子为第二层，根的孩子的孩子为第三层，以此类推。

**树的高度（或者深度）：**树中结点的最大层次。

结点的深度和高度：

（1）深度： 从根结点到该结点路径上的结点的个数。

（2）高度： 从某结点往下走可能到达多个叶子结点，对应了多条通往这些叶子结点的路径，其中最长的那条路径上结点的个数为该结点在树中的高度。

（3）： 根节点的高度为树的高度。

3、树的存储结构

顺序结构

链式结构

二叉树

1、定义

概念： 每个结点最多只有两棵子树，并且子树有左右顺序之分，不能颠倒。

二叉树的基本形态：

（1）： 空二叉树

（2）： 只有根结点

（3）： 只有左子树，右子树为空。

（4）： 只有右子树，左子树为空。

（5）： 既有左子树，又右子树为空。

满二叉树： 所有的分支结点都有左孩子和右孩子，并且叶子结点都集中在二叉树的最下一层。

完全二叉树： 如果对一棵深度为k、有n个结点的二叉树进行编号后，各节点的编号与深度为k的满二叉树中相同位置上的结点编号均相同。

2、主要性质

性质1 非空二叉树上的叶子结点数等于双分支结点数加1。

总分支数 = 总结点数 -1

性质2 二叉树的第i层上最多有 2^(i-1)(i>=1)个结点

性质3 高度（或者深度）为k的二叉树最多有2^k-1(k>=1)个结点

性质4

3、存储结构

（1）、顺序存储

（2）、链式存储

typedef struct BTNode
{
    char data; // int data 也可以，根据题目需要进行设置
    struct BTNode *lchild;
    struct BTNode *rchild;
}BTNode;

4、遍历算法

（1）、先序遍历（根左右）

访问根节点

先序遍历左子树

先序遍历右子树

void preorder(BTNode *p){
    if(p!=NULL){
        Visit(p);//假设Visit()函数已经定义过
      
        preorder(p->lchild);
        preorder(p->rchild);
    }
}

（2）、中序遍历（左根右）

中序遍历左子树

访问根节点

中序遍历右子树

void inorder(BTNode *p){
    if(p!=NULL){
        preorder(p->lchild);
         Visit(p);
        preorder(p->rchild);
    }
}

（3）、后序遍历（左右根）

后序遍历左子树

后序遍历右子树

访问根节点

void inorder(BTNode *p){
    if(p!=NULL){
        preorder(p->lchild);
        preorder(p->rchild);
        Visit(p);
    }
}

目录CONTENT

树与二叉树