二叉树知识点总结

二叉树知识点总结

树的相关术语：

结点的度：一个结点的子树的数量。

树的度：该树中结点的最大度数。

叶结点和分支结点：度为0的结点和度不为0的结点。

树的深度：树中结点的最大层数。

有序树和无序树：树中每个结点的各子树看成是从左到右有次序的称为有序树（一般都是），反之无序

森林：m（m>0）棵互不相交的树的集合。

树的表示：（A（B（E，F（I，J）），C，D（G，H）））

二叉树的常见问题及其解决程序

【递归】二叉树的先序建立及遍历

在JAVA中实现的二叉树结构

【非递归】二叉树的建立及遍历

二叉树递归实现与二重指针

二叉树先序中序非递归算法

轻松搞定面试中的二叉树题目

二叉树的概念：

1. 五种基本形态：空，仅有根结点，仅有左子树，仅有右子树，有左右子树.

2. 与树的区别：最大度为2；结点有左右之分。

3. 满二叉树：除最下一层结点外，每层都有2个子结点。

完全二叉树：除最后一层外，其他各层的结点数都达到最大个数；且最后一层从左往右结点连续。

4.  性质：

（1）在二叉树的第i层上至多有2^(i-1)个结点。

（2）深度为k的二叉树至多有2^k-1个结点(k≥1)，最少有k个结点。

（3）对任何一颗二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

（4）具有n个节点的完全二叉树的深度为[log2n]+1，其中[log2n]+1是向下取整。

（5）如果有一颗有n个节点的完全二叉树的节点按层次序编号，对任一层的节点i（1<=i<=n）有

1.如果i=1，则节点是二叉树的根，无双亲，如果i>1，则其双亲节点为[i/2]，向下取整

2.如果2i>n那么节点i没有左孩子，否则其左孩子为2i

3.如果2i+1>n那么节点没有右孩子，否则右孩子为2i+1

5.  二叉树的储存：

（1）顺序储存结构：一般按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中。

一般用于储存完全二叉树，若不是完全二叉树可以将其转化为完全二叉树（虚设结点#）。但会造成空间的大量浪费。

 

        #define Maxsize 100    //假设一维数组最多存放100个元素

        typedef char Datatype;  //假设二叉树元素的数据类型为字符

        typedef struct

        { Datatype bt[Maxsize];

          int btnum;

        }Btseq;

 

更多详情见请继续阅读下一页的精彩内容：

1 2 下一页