7.8 二叉树

树形结构是一类重要的非线性数据，树和二叉树是常用的树形结构。

• 二叉树的第i层上最多有2i-1(i>=1)个结点；
• 深度为h的二叉树中最多有2h-1个结点；
• 在任一棵二叉树中，有n0叶子结点，有n2个度为2的结点，则有n0=n2+1。

◆ 3、链式二叉树的结点类模板
先在此定义结点类模板，下一节在其基础上定义二叉树类模板。（查看源码）

◆ 1、所谓二叉树的遍历（binary tree traversal），就是遵从某种次序，查巡二叉树的所有结点，每个结点都被访问一次，而且仅访问一次。所谓“访问”指对结点施行某些操作，但不破坏它原来的数据结构。

遍历二叉树有不同次序，规定先左后右，令L，R，V分别代表遍历一个结点的左右子树和访问该结点的操作，有三种方式： 前序遍历（VLR）、 中序遍历（LVR）、 后序遍历（LRV）

◆ 2、链式二叉树类模板
templateclass BinaryTree{
        Node *root; //二叉树的根指针
        void InOrder(Node *Current); //中序遍历
        void PreOrder(Node *Current); //前序遍历
        void PostOrder(Node *Current); //后序遍历
        void Insert(const T &data,Node * &b);
                //插入结点，参数为引用！
        void Destory(Node * Current); //删除树
public:
        BinaryTree(){root=NULL;} //空树构造函数
        ~BinaryTree(){Destory(root);} //析构函数
        void Creat(T* data,int n); //建立（排序）二叉树
        void InOrder(){InOrder(root);}
                //中序遍历，公有函数为接口
        void PreOrder(){PreOrder(root);}
                //前序遍历，公有函数为接口
        void PostOrder(){PostOrder(root);}
                //后序遍历，公有函数为接口
};

详细代码参见【例7.13】

1. 令a0为二叉树的根结点。
2. 若a1
3. 如ai小于根结点，则去左子树，否则去右子树，按此法查找，直到成为空树，则安放此位置。这步就是插入算法。

【例7.15】二叉排序树查找函数。（查看源码）
算法：用中序遍历即可，但递归慢。