java求二叉树的高度-树和二叉树的主要区别

树 1、树的表示形式

5.1树型表示

5.2的（a）是嵌套集合，（b)是广义表形式，（c)凹入表示法

2、树的结构（非线性型）

1、节点之间有分支

2、具有层次关系

3、使用范围：

自然界：树

人类社会： 家谱、行政组织机构

计算机领域：

编译：用树表示源程序的语法结构

数据库系统：用树组织信息

算法分析：用树描述执行过程

3、树的定义

树（Tree）是n(n>=0)个结点的有限集。n=0为空树

1、 有且仅有一个称之为根的节点

2、除了根节点以外的其余结点可分为m(m>0）个互不相交的有限集T1，T2，T3......Tm，其中每一个集合本身又是一棵树，并且称为根的子树

4、树的基本情况

1.森林：是m(m>=0)棵互不相交的树的集合 ` 注意树一定是森林，森林不一定是树

2.结点（node）: 树的结点由数据元素及其若干分支组成

3.子树：以根结点为根的树为全树（或树），以其他结点作为根结点的树为子数

4.结点的度：该结点分支数量

5.树的度：树中所有结点的度的最大值

6.叶子结点(leaf node)：无分支的结点

7.双亲结点、孩子结点：一个结点下的所有分支结点称为孩子结点java求二叉树的高度，该结点成为他们的双亲结点。

8.兄弟结点：具有共同的双亲

9.堂兄弟：在同一层，具有公共祖先

10.树的深度、高度：深度：根节点从0开始计算java求二叉树的高度，高度：最底层结点从0开始计算

二叉树（二叉树不是一种特殊的树，而是树的特殊情形） 1. 二叉树的结点定义

typedef struct Node{

char data; /*数据域*/

struct Node *lchild, *rchild; /*左子树和右子树*/

} * BiTree, BiNode;

2、二叉树的创建和遍历以及测试方式

typedef struct Node{
	char val;                    /*数据域*/
	struct Node *lchild, *rchild; /*左子树和右子树*/
} * BiTree, BiNode;
void CreateBiTree(BiTree *T)
{
    char ch;
    ch=gerchar();
    if (ch == '#')
        T = NULL;
    else
    {
        T = new BiNode; /*创建一个新节点*/
        T->data = ch;
        CreateBiTree(T->lchild);
        CreateBiTree(T->rchild);
    }
    /*递归创建*/
}
// 前序遍历
void preOrder(BiTree* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preOrder(root->left);
    preOrder(root->right);
}
// 中序遍历
void inOrder(BiTree* root) {
    if (root == NULL) {
        return;
    }
    inOrder(root->left);
    printf("%d ", root->val);
    inOrder(root->right);
}
// 后序遍历
void postOrder(BiTree* root) {
    if (root == NULL) {
        return;
    }
    postOrder(root->left);
    postOrder(root->right);
    printf("%d ", root->val);
}
// 主函数
int main() {
    TreeNode* root = createTree();
    printf("前序遍历结果：");
    preOrder(root);
    printf("\n中序遍历结果：");
    inOrder(root);
    printf("\n后序遍历结果：");
    postOrder(root);
    printf("\n");
    return 0;
}

二叉树的特殊情形 1、满二叉树：

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

2、完全二叉树

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

3、完全二叉树的性质

1）叶节点只可能在最下两层

2）最下层的叶子一定集中在左部连续位置

3）结点度为 1，则该结点只有左孩子。

4）倒数第二层，如果有叶节点，则一定位于右部连续位置。

5）相同结点的二叉树，完全二叉树的深度最小

二叉树的相关内容

B树、B+树、B-树

红黑树

线段树

哈夫曼树

BST树、BBST树