M叉树

Author : 张一极
22:32-20201103

m=2 性质

$2^{i-1}$ 个结点,i>=1

$2^k-1$ 个结点,至少有k个结点

$n_0$ $n_2$ $n_0=n_2+1$ ,总边数为B,B = n-1

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

m!=2 性质

$\frac{m^h-1}{m-1}$ 个结点

完全二叉树

每一个节点都能在满二叉树上找到对应相同的编号和位置

$i\leq \frac{n(二叉树结点数)}{2}$ , 为分支结点,如果大于它,即为叶子结点,因为满二叉树的编号中,叶子结点的一半取下界,必然为父结点的编号,故最后一个叶结点的编号除以二,得到的是其父节点的编号,更大的话,就是父结点的相邻结点,这个相邻结点必然没有子结点(如果有的话,最后一个叶子结点的位置应该在他下面),所以大于这个数值的节点,一定是叶子结点.

度为1的结点只能有一个,因为是完全二叉树

并且一定是编号最大的叶子结点的父节点.

平衡二叉树(AVL)

左右子树高度相差不超过1的树称为平衡二叉树

这种高度差称为平衡因子.

以类实现二叉树


2
1
def binaryTree(r):
2
  return [r,[],[]]

简单实现了一个具有根节点和子列表的嵌套列表,此时,添加左子树到root,需要在第二个地方插入新列表

python实现


30
1
'''
2
创建一个根,并且有左右子树的二叉树类
3
'''
4
class binarytree:
5
    def __init__(self,root_obj):
6
        self.key=root_obj
7
        self.lchild=None
8
        self.rchild=None
9
    def insert_l_child_tree(self,new_node):
10
        if self.lchild==None:
11
            self.lchild=binarytree(new_node)
12
        else:
13
            t=binarytree(new_node)
14
            t.lchild=self.lchild
15
            self.lchild=t
16
    def insert_r_child_tree(self,new_node):
17
        if self.rchild==None:
18
            self.rchild=binarytree(new_node)
19
        else:
20
            t=binary_tree(new_node)
21
            t.rchild=self.rchild
22
            self.rchild=t
23
    def getl(self):
24
        return self.lchild
25
    def getr(self):
26
        return self.rchild
27
    def set_root(self,obj):
28
        self.key=obj
29
    def get_root(self):
30
        return self.key

线性表示(遍历)

前序遍历

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

前序遍历的递归实现


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
}

前序遍历非递归实现


xxxxxxxxxx
23
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
}

中序遍历

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

递归实现


xxxxxxxxxx
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
21
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
8
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

层次遍历

非递归实现


xxxxxxxxxx
17
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