性质

树的性质

树的结点数等于所有结点的度数加1
度为m的树第i层上至多有$m^{i-1}$个结点
高度为h的m叉树至多有$1 + m + m^2 + … + m^{h-1} = \frac{1 - m^h}{1-m} = \frac{m^h-1}{m-1}$个结点
具有n个结点的m叉树最小高度为$\ceil(log_m(n(m-1)+1))$

二叉树的性质

非空二叉树的叶子结点数等于度为2的结点数加1
非空二叉树上第i层至多有$2^{i-1}$个结点
高度为h的二叉树至多有$2^h-1$个结点

完全二叉树的性质

$i>1$时，结点i的双亲结点编号为$floor(\frac{i}{2})$, 当i为偶数时，它是左孩子，当i为奇数时，它是右孩子。
$2i\leq n$时，结点i的左孩子编号为2i，否则无左孩子
$2i+1 \leq n$时，结点i的右孩子编号为2i+1，否则无右孩子
结点i所在的层次（深度）为$ceil(log_2(i+1))$
具有n个结点的完全二叉树高度为$ceil(log_2(n+1))$

树的遍历

先序遍历

递归算法

Status PreOrder_Recursion(BiTree &T){
    BiTNode *p = T;
    if(!p) return 0;
    else{
        cout << p->data << " ";
        PreOrder_Recursion(p->lchild);
        PreOrder_Recursion(p->rchild);
    }
    return OK;
}

非递归算法

Status PreOrder_Iteration(BiTree &T){
    BiTNode *p = T;
    stack<BiTNode*> S;
    cout << "The PreOrder_Iteration: ";
    while(p||!S.empty()){
        while(p){
            cout << p->data << " ";
            S.push(p);
            p = p->lchild;
        }
        p = S.top();
        S.pop();
        p = p->rchild;
    
    }
    cout << endl;
    return OK;
}

中序遍历

递归算法

Status InOrder_Recursion(BiTree &T){
    BiTNode *p = T;
    if(!p) return ERROR;
    else{
        InOrder_Recursion(p->lchild);
        cout << p->data << " ";
        InOrder_Recursion(p->rchild);
    }
    return OK;
}

非递归算法

Status InOrder_Iteration(BiTree &T){
    BiTNode *p = T;
    stack<BiTNode*> S;
    cout << "The InOrder_Iteration: ";
    while(p||!S.empty()){
        while(p){
            S.push(p);
            p = p->lchild;
        }
        p = S.top();
        S.pop();
        cout << p->data << " ";
        p = p->rchild;
    }
    cout << endl;
    return OK;
}

后序遍历

递归算法

Status PostOrder_Recursion(BiTree &T){
    BiTNode *p = T;
    if(!p) return ERROR;
    else{
        PostOrder_Recursion(p->lchild);
        PostOrder_Recursion(p->rchild);
        cout << p->data << " ";
    }
    return OK;
}

非递归算法

Status PostOrder_Iteration(BiTNode *T){
    BiTNode *p = T;
    stack<BiTNode*> S;
    BiTNode *pCur = T;
    BiTNode *pLast = NULL;
    while(pCur||!S.empty()){
        // 这里的思想和中序遍历线索二叉树很相似
        while(pCur){
            S.push(pCur);
            pCur = pCur->lchild;
        }
        pCur = S.top();
        S.pop();
        // 符合访问条件
        if(pCur->rchild==NULL||pCur->rchild==pLast){
            cout << pCur->data << " ";
            pLast = pCur;
            // 这个NULL很关键，是退栈的一个条件
            // 意思是告诉程序，这个节点已经被打印了，该接着退栈了
            pCur = NULL;
        }
        else{
            S.push(pCur);
            pCur = pCur->rchild;
        }
    }
    return OK;
}

主要是两个思想：

栈中的元素全都是访问到了，但是没有资格打印的节点
打印资格是什么？
1. 该结点无右孩子
1. 右孩子刚被访问过

Status PostOrder_Iteration(BiTree &T){
	BiTNode *p = T;
	stack<BiTNode*> S;
	BiTNode *pCur, *pLast;
	pCur = p;
	cout << “The PostOrder: “;
	while(pCur){
		S.push(pCur);
		pCur = pCur->lchild;
	}
	while(!S.empty()){
		pCur = S.top();
		S.pop();
		// 符合访问条件
		if(pCur->rchild==NULL||pCur->rchild==pLast){
			cout << pCur->data << “ “;
			pLast = pCur;
		}
		else{
			S.push(pCur);
			pCur = p->rchild;
			while(pCur){
				S.push(PCur);
				pCur = pCur->lchild;
			}
		}
	}
	cout << endl;
	return OK;
}

Note：所有的非递归算法，都借助了NULL元素作为退栈的条件。 while循环，不管什么遍历，他要做的一件事情都是先找到最左下角的元素，在这个过程中，在通过条件判断什么时候打印该结点。

也就是说对树的遍历，路径是一定的，变化的仅仅是打印结点的条件。

层次遍历

求二叉树的宽度：

// 层次遍历, 用NULL来标记一层遍历完毕
int Tranverse(BiTNode *root){
    int count = 0， max = 0;
    BiTNode *p = root;
    queue<BiTNode*> Q;
    if(p){
        Q.push(p);
        Q.push(NULL);
    }
    else{
        return ERROR;
    }
    while(!Q.empty()){
        p = Q.front();
        Q.pop();
        if(p){
	        count++;
            if(p->lchild) Q.push(p->lchild);
            if(p->rchild) Q.push(p->rchild);
        }
        else{
            if(Q.empty()) break;
            if(count>max) max = count;
            count = 0;
            Q.push(NULL);
        }
    }
    return max;    
}

由遍历序列构造二叉树

先序序列和中序序列

先序序列第一个结点一定是根结点
中序序列中，根结点一定将中序序列分割成两个子序列
先序序列中找到对应的左右子序列，第一个结点分别是左右子树的根结点
如此递归

后序序列和中序序列

后序序列最后一个结点一定是根结点
中序序列中，根结点一定将中序序列分割成两个子序列
后序序列中找到对应的左右子序列，最后结点分别是左右子树的根结点
如此递归

层次序列和中序序列

层次序列第一个结点一定是根结点
中序序列中，根结点一定将中序序列分割成两个子序列
先序序列中找到对应的左右子序列，第一个结点分别是左右子树的根结点
如此递归

线索二叉树

二叉树的线索化，实际上就是遍历一次二叉树，在遍历的过程中检查当前结点左右指针域是否为空，若为空，将它们改为指向前趋结点或后继结点的线索。

void InOrder(ThreadTree &p, ThreadTree &per){
	if(p!=NULL){
		InOrder(p->lchild, pre);
		if(p->lchild==NULL){
			p->lchild = pre;
			p->ltag = 1;
		}
		if(pre!=NULL&&pre->rchild==NULL){
			pre->rchild = p;
			pre->tag = 1;
		}
		pre = p;
		InTread(p->rchild,pre);
	}
}

void CreateInThread(ThreadTree &T){
	ThreadTree pre = NULL;
	if(T!=NULL){
		InOrder(T, pre);
		pre->rchild = NULL; //处理遍历的最后一个结点
		pre->rtag = 1;
	}
}

中序遍历线索二叉树

void InOrderThr(BiThrTree &T){
	BiThrTree p = T->lchild; //p指向根结点
	while(p!=T){
		while(p->late==Link) p=p->lchild;
		visit(p);
		while(p->rtag==Thread&&p->rchild!=t){
			p = p->rchild;
			visit(p);
		}
		p = p->rchild;
	}
}

假设二叉排序树以中序后继线索表作为存储结构，编写按非递减顺序输出该二叉排序树中所有大于a且小于b的关键字的算法。

//基于中序遍历线索二叉树的思想写该算法
Void f(BiThrTree &t, int a, int b){
	BiThrTree p = t->rchild;
	while(p!=t){
		while(p->ltag==Link) p = p->lchild;
		if(p->data.key>b) break;
		if(p->data.key>a){
			cout << p->data;
		}
		while(p->rtag==Thread&&p->data.key<=b&&p->rchild!=t){
			if(p->data.key>a){
				cout << p->data;
			}
			p = p->rchild;
		}
		p = p->child;
	}
}

后序遍历线索二叉树

后序遍历线索二叉树需要改变数据结构，加入父结点

(尚未验证）(在一棵二叉树上验证通过，尚未在多棵二叉树测试）

void PostOrderThrBiTree(BiTree &T){
	BiTree p = T->lchild, pre = T;
	while(p!=T){
		while(p->ltag==Link&&p->lchild!=T) p = p->lchild;
		while(p->rtag==Thread&&p->rchild!=T){
			cout << p->data;
			pre = p;
			p = p->rchild;
		}
		if(p->rchild==pre){
			cout << p->data;
			pre = p;
			p = p->parent->rchild;
			if(p==pre){
				cout << p->parent->data;
				break;
			}
		}
		else{
			p = p->rchild;
		}
	}
}

On this page

性质

树的性质

二叉树的性质

完全二叉树的性质

树的遍历

先序遍历

递归算法

非递归算法

中序遍历

递归算法

非递归算法

后序遍历

递归算法

非递归算法

层次遍历

由遍历序列构造二叉树

先序序列和中序序列

后序序列和中序序列

层次序列和中序序列

线索二叉树

中序遍历线索二叉树

后序遍历线索二叉树

树和森林的遍历

树，森林和二叉树的相互转换

树的遍历

森林的遍历

哈夫曼树