【数据结构】二叉树（一）

目录

1. 树型结构

概念

树的表示形式

​编辑

2. 二叉树（重点）

2.1 概念

2.2 二叉树的性质

2.3 二叉树的存储

2.4 二叉树的遍历

前中后序遍历

层序遍历：

2.5二叉树的基本操作

---

本篇主要理解树和二叉树相关概念，二叉树遍历及基本操作。

---

1. 树型结构

树是一种非线性的数据结构，它是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 有一个特殊的结点，称为根结点，根结点没有前驱结点。
• 除根结点外，其余结点被分成M(M > 0)个互不相交的集合T1、T2、......、Tm，其中每一个集合Ti (1 <= i <= m) 又是一棵与树类似的子树。每棵子树的根结点有且只有一个前驱，可以有0个或多个后继
• 树是由递归定义的。

树与非树的区分点：

1. 树形结构中，子树之间不能有交集，否则就不是树形结构
2. 树形结构中，除根结点外，每个节点有且仅有一个父节点，否则就不是树形结构
3. 树形结构中，一颗N个结点的树有N-1条边，否则就不是树形结构

1.1概念

树型结构里，有非常多的概念，多用用就记住了

1.2树的表示形式

class Node   {

int value ; // 树中存储的数据

Node firstChild ; // 第一个孩子引用

Node nextBrother ; // 下一个兄弟引用

 }

结构图

相关习题，练练手吧~

1. 某二叉树共有 399 个结点，其中有 199 个度为 2 的结点，则该二叉树中的叶子结点数为（ ）

A 不存在这样的二叉树

B 200

C 198

D 199

2. 在具有 2n 个结点的完全二叉树中，叶子结点个数为（ ）

A n

B n+1

C n-1

D n/2

3. 一个具有 767 个节点的完全二叉树，其叶子节点个数为（）

A 383

B 384

C 385

D 386

4. 一棵完全二叉树的节点数为 531 个，那么这棵树的高度为（ ）

A 11

B 10

C 8

D 12

// 孩子表示法

class Node {

int val ; // 数据域

Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树

Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树

}

// 孩子双亲表示法

class Node {

int val ; // 数据域

Node left ; // 左孩子的引用，常常代表左孩子为根的整棵左子树

Node right ; // 右孩子的引用，常常代表右孩子为根的整棵右子树

Node parent ; // 当前节点的根节点

}

（本文采用孩子表示法）

并且二叉树定义是递归式的，因此后序基本操作中基本都是按照该概念实现的。 

2.4 二叉树的遍历

前中后序遍历

public void createBinaryTree(){
    BTNode node1 = new BTNode(1);
    BTNode node1 = new BTNode(2);
    BTNode node1 = new BTNode(3);
    BTNode node1 = new BTNode(4);
    BTNode node1 = new BTNode(5);
    BTNode node1 = new BTNode(6);
    root = node1;
    node1.left = node2;
    node2.left = node3;
    node1.right = node4;
    node4.left = node5;
    node5.right = node6;
}

• NLR：前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
• LNR：中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树。
• LRN：后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。

 初始二叉树就到这里啦，刚了解二叉树概念性东西比较多，多看几遍就记住了。关注我，下篇讲解二叉树的多种遍历方式及多道经典面试题。不要错过喔