二叉树基本知识

几种特殊的二叉树

二叉搜索(查找)树

• 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；

• 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

满二叉树

• 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点二叉树;

性质：满二叉树的深度为k=log2^(n+1);

完全二叉树

• 所有的叶结点都出现在第k层或k-l层(层次最大的两层);

• 对任一结点，如果其右子树的最大层次为L，则其左子树的最大层次为L或L+l;

性质：具有n个节点的完全二叉树的深度为[log2^n]+1(向下取整);

二叉树遍历

前序遍历(根–>左–>右)

递归方案

void forwardSearch(TreeNode * root)
{
	if (root==NULL) return ;
	cout<<root->val<<endl;
	forwardSearch(root->left);
	forwardSearch(root->right);
}

非递归方案

/*
 * 1. 根节点入栈；
 * 2. 循环非空栈
 * 3. 		将节点的右、左子节点分别入栈；
 * 3. 		打印节点val
 */
  void forwardSearchNoRec(TreeNode * root)
  {
    stack<TreeNode*> st;
    if (root == NULL)
      return ;
    st.push(root);
    while(!st.empty())
      {
        TreeNode *tmpNode = st.top();
        st.pop();
        if (tmpNode->right!=NULL)
          st.push(tmpNode->right);
        if (tmpNode->left!=NULL)
          st.push(tmpNode->left);
        cout<<tmpNode->val<<endl;
      }
  }

中序遍历(左–>根–>右)

递归方案：

  void middleSearch(TreeNode * root)
  {
    if (root == NULL)return;
    forwardSearch(root);
    cout<<root->val<<endl;
    forwardSearch(root);
  }

非递归方案：

/*
 * 1. 根节点入栈；
 * 2. 将左边界压入栈中，即不停的令 root = root->left，st.push(root)；
 * 3. 若 root 为空，则从栈中弹出一个结点并访问，并令 root = root->right，继续重复步骤2；
 * 4. 当栈为空并且 root 也为空时，循环结束；
 */
  void middleSearchNoRec(TreeNode * root)
  {
    stack<TreeNode*> st;
    if (root == NULL)
      {
        return;
      }
    TreeNode * tmpRoot = root;
    while( !st.empty() || tmpRoot!=NULL)
      {
        while(tmpRoot!=NULL)
          {
            st.push(tmpRoot);
            tmpRoot = tmpRoot->left;
          }
        tmpRoot = st.top();
        st.pop();
        cout<<tmpRoot->val<<endl;
        tmpRoot = tmpRoot->right;
      }
  }

后序遍历(左–>右–>根)

递归方案：

  void backSearch(TreeNode * root)
  {
    if (root == NULL)return;
    backSearch(root->left);
    backSearch(root->right);
    cout<<root->val<<endl;
  }

非递归方案：

 /*
 * 思路：结合前序遍历+双栈
 * 1. 前序遍历：打印当前节点；右孩子进栈；左孩子进栈；输出：根-->左-->右；
 * 2. 参考前序的方法，输出：根-->右-->左；入另一个栈
 * 3. 遍历另一个栈即为后续遍历
 */
  void forwardSearchNoRec(TreeNode * root)
  {
    stack<TreeNode*> st;
    if (root == NULL)
      return ;
    st.push(root);
    while(!st.empty())
      {
        TreeNode *tmpNode = st.top();
        st.pop();
        if (tmpNode->right!=NULL)
          st.push(tmpNode->right);
        if (tmpNode->left!=NULL)
          st.push(tmpNode->left);
        cout<<tmpNode->val<<endl;
      }
  }