数据结构：树与树算法_数据结构中左子树的根节点怎么求

一、树、二叉树、满二叉树、完全二叉树、不完全二叉树的性质

1.树（英语：tree）是一种抽象数据类型（ADT）或是实作这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>=1）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

• 每个节点有零个或多个子节点；
• 没有父节点的节点称为根节点；
• 每一个非根节点有且只有一个父节点；
• 除了根节点外，每个子节点可以分为多个不相交的子树；
  
  二叉树

二叉树的基本概念

• 二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”（left subtree）和“右子树”（right subtree）

二叉树的性质(特性)

• 性质1: 在二叉树的第i层上至多有2^(i-1)个结点（i≥1）

  证明：下面用"数学归纳法"进行证明。
  (01) 当i=1时，第i层的节点数目为2{i-1}=2{0}=1。因为第1层上只有一个根结点，所以命题成立。
  (02) 假设当i>1，第i层的节点数目为2{i-1}。这个是根据(01)推断出来的！
  下面根据这个假设，推断出"第(i+1)层的节点数目为2{i}“即可。
  由于二叉树的每个结点至多有两个孩子，故"第(i+1)层上的结点数目” 最多是 “第i层的结点数目的2倍”。即，第(i+1)层上的结点数目最大值=2×2{i-1}=2{i}。
  故假设成立，原命题得证！

• 性质2: 深度为k的二叉树至多有2^k - 1个结点（k≥1）

  证明：在具有相同深度的二叉树中，当每一层都含有最大结点数时，其树中结点数最多。利用"性质1"可知，深度为k的二叉树的结点数至多为：
  20+21+…+2k-1=2k-1
  故原命题得证！

• 性质3: 对于任意一棵二叉树，如果其叶结点数为N0，而度数为2的结点总数为N2，则N0=N2+1;

• 性质4:具有n个结点的完全二叉树的深度必为 log2(n+1)

  证明：根据"性质2"可知，高度为h的二叉树最多有2{h}–1个结点。反之，对于包含n个节点的二叉树的高度至少为log2(n+1)。

• 性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2（i＝1 时为根,除外）

(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。

满二叉树
高度为h，并且由2{h} –1个结点的二叉 树，被称为满二叉树。
满二叉树的性质：

1. 满二叉树的第i层的节点数为2n-1个。
2. 深度为k的满二叉树必有2^k-1个节点 ，叶子数为2^k-1。
3. 满二叉树中不存在度为1的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
4. 具有n个节点的满二叉树的深度为log2(n+1)。

完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。

特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

完全二叉树的性质：

1. 满二叉树是一棵特殊的完全二叉树，但完全二叉树不一定是满二叉树。
2. 在满二叉树中最下一层，连续删除若干个节点得到完全二叉树。
3. 在完全二叉树中，若某个节点没有左子树，则一定没有有子树。
4. 若采用连续储存的方式存放二叉树，则节点下标之间的关系（根节点下标为0）：

若某个节点的下标为 i ，则这个节点的父节点的下标为 i / 2。
　　
　　若某个节点下标为 i ，且节点的度为2，则这个节点的左子节点的下标为 2 * i + 1 ，右子节点的下标为 2 * i + 2 。
　　
　　除了根节点外，左子树的下标为基数，右子树的下标为偶数。

二、树的其他知识–节点

树的术语

• 节点的度：一个节点含有的子树的个数称为该节点的度；
• 树的度：一棵树中，最大的节点的度称为树的度；
• 叶节点或终端节点：度为零的节点；
• 父亲节点或父节点：若一个节点含有子节点，则这个节点称为其子节点的父节点；
• 孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
• 兄弟节点：具有相同父节点的节点互称为兄弟节点；
• 节点的层次：从根开始定义起，根为第1层，根的子节点为第2层，以此类推；
• 树的高度或深度：树中节点的最大层次；
• 堂兄弟节点：父节点在同一层的节点互为堂兄弟；
• 节点的祖先：从根到该节点所经分支上的所有节点；
• 子孙：以某节点为根的子树中任一节点都称为该节点的子孙。
• 森林：由m（m>=0）棵互不相交的树的集合称为森林；

三、二叉树的遍历（广度优先、深度优先—中序遍历）

树的遍历是树的一种重要的运算。所谓遍历是指对树中所有结点的信息的访问，即依次对树中每个结点访问一次且仅访问一次，我们把这种对所有节点的访问称为遍历（traversal）。那么树的两种重要的遍历模式是深度优先遍历和广度优先遍历,深度优先一般用递归，广度优先一般用队列。一般情况下能用递归实现的算法大部分也能用堆栈来实现。

深度优先遍历
对于一颗二叉树，深度优先搜索(Depth First Search)是沿着树的深度遍历树的节点，尽可能深的搜索树的分支。
那么深度遍历有重要的三种方法。这三种方式常被用于访问树的节点，它们之间的不同在于访问每个节点的次序不同。这三种遍历分别叫做先序遍历（preorder），中序遍历（inorder）和后序遍历（postorder）。

下面着重说一下，中序遍历。

中序遍历 在中序遍历中，我们递归使用中序遍历访问左子树，然后访问根节点，最后再递归使用中序遍历访问右子树

左子树->根节点->右子树
例如：

中序遍历就是 7381940526

广度优先遍历
从树的root开始，从上到下从从左到右遍历整个树的节点

def breadth_travel(self, root):
        """利用队列实现树的层次遍历"""
        if root == None:
            return
        queue = []
        queue.append(root)
        while queue:
            node = queue.pop(0)
            print node.elem,
            if node.lchild != None:
                queue.append(node.lchild)
            if node.rchild != None:
                queue.append(node.rchild)
1
2
3
4
5
6
7
8
9
10
11
12
13