二叉树

Author : 张一极

22:32-20201103

性质

1.二叉树的第i层至多有$2^{i-1}$个结点,i>=1

2.深度为k的二叉树至多有$2^k-1$个结点,至少有k个结点

3.任何叶子节点为$n_0$,度为2的结点为$n_2$,则$n_0=n_2+1$,总边数为B,B = n-1

4.n个结点的二叉树高度至少为log(2n)+1

线性表示(遍历)

前序遍历

到达结点,输出结点,访问左子结点,最后访问右子节点

前序遍历的递归实现

xxxxxxxxxx
10
1
void preOrder(bt T)
2
{
3
  if (T == NULL)
4
          {
5
            return;
6
          }
7
      cout<<T.data;
8
      preOrder(T.left);
9
      preOrder(T.right);
10
}

前序遍历非递归实现

x
1
void preorder(bt T)
2
{
3
//用一个栈数据结构来储存待访问的右子树
4
stack<bt>iterm//临时储存BinaryTree类型的结构
5
  while(T!=Null)
6
  {
7
    cout<<T.data<<endl;
8
    if(T.right!=Null)
9
    {
10
      iterm.push(T.right);//压栈
11
    }
12
    if(T.left!=Null)
13
    {
14
      T=T.left;//赋值完毕后下一次循环访问此次赋值的左子树
15
    }
16
    else{
17
      //无左子树的情况
18
        //应该给予弹栈,获取最近的右子树
19
        T=iterm.top();//开始循环栈顶右子树
20
        iterm.pop();//清除
21
    }
22
  }
23
}

中序遍历

到达结点,先访问左子结点,再输出该节点,最后访问右子结点

递归实现

8
1
void centerOrder(BT T) {
2
  if (T == NULL) {
3
    return;
4
  }
5
  centerOrder(T.left);
6
  std::cout << T.data;
7
  centerOrder(T.right);
8
}

非递归实现

xxxxxxxxxx
1
20
1
void centerOrder(BinTree *root)      //非递归中序遍历
2
{
3
    stack<BT*> s;
4
    BT *p=root;
5
    while(p!=NULL  or  !s.empty())
6
    {
7
        if(p!=NULL)
8
        {
9
            s.push(p);
10
            p=p->lchild;
11
          //每次左子树压栈后下一次左子树为空的时候将会弹栈往上查找
12
        }
13
        else       
14
       {
15
            p=s.top();
16
            cout<<p->data<<"";
17
            s.pop();
18
            p=p->rchild;
19
        }
20
    }    
21
} 

后序遍历

先访问子树,后访问节点的访问顺序

xxxxxxxxxx
1
void postOrder(bt tree)
2
{
3
    if(NULL == tree)
4
        return;
5
    postOrder(tree.left);
6
    postOrder(tree.right);
7
    cout<<tree.value;
8
}

x
1
void postOrder(BT root)    //非递归后序遍历
2
{
3
    stack<BT*> s;
4
    BT *p=root;
5
    BTNode *temp;
6
    while(p!=NULL||!s.empty())
7
    {
8
        while(p!=NULL)              //寻找所有左子树 
9
         {
10
            BTNode *btn=(BTNode *)malloc(sizeof(BTNode));
11
            btn->btnode=p;
12
            btn->isFirst=true;
13
            s.push(btn);
14
            p=p->lchild;
15
        }
16
        if(!s.empty())
17
        {
18
            temp=s.top();
19
            s.pop();
20
            if(temp->isFirst==true)     //表示是第一次出现在栈顶 
21
             {
22
                temp->isFirst=false;
23
                s.push(temp);
24
                p=temp->btnode->rchild;    
25
            }
26
            else//第二次出现在栈顶 ,两次出现在栈顶表示左右都没有子树
27
             {
28
                cout<<temp->btnode->data<<"";
29
                p=NULL;
30
            }
31
        }
32
    }    
33
} 

Reference from https://www.cnblogs.com/dolphin0520/archive/2011/08/25/2153720.html

层次遍历

非递归实现

x
1
void list_order(bt tree)
2
{
3
  que=init_que();
4
  bt tree;
5
  while(isempty(que))
6
  {
7
      outque();//包括输出出队的节点
8
      if(tree.l!=null)
9
        {
10
          inque(tree.l);
11
        }
12
      if(tree.r!=null)
13
      {
14
        inque(tree.r);
15
      }
16
  }
17
}

End

21:00-20201104