二叉树简介

基本概念

每个结点最多有两棵子树，左子树和右子树，次序不可以颠倒。

性质：

1、非空二叉树的第n层上至多有2^(n-1)个元素。

2、深度为h的二叉树至多有2^h-1个结点。

满二叉树

所有终端都在同一层次，且非终端结点的度数为2。

在满二叉树中若其深度为h，则其所包含的结点数必为2^h-1。

完全二叉树

除了最大的层次即成为一颗满二叉树且层次最大那层所有的结点均向左靠齐，即集中在左面的位置上，不能有空位置。

对于完全二叉树，设一个结点为i则其父节点为i/2，2i为左子节点，2i+1为右子节点。

二叉树遍历

遍历即将树的所有结点访问且仅访问一次。按照根节点位置的不同分为前序遍历，中序遍历，后序遍历。（这里的前中后指的都是根节点）
前序遍历：根节点->左子树->右子树
中序遍历：左子树->根节点->右子树
后序遍历：左子树->右子树->根节点

这里采用链式结构，数据存储结构如下

1
2
3
4
5
6
7
8
9
10
11
#define NODENUM 1000

typedef char DataType;

typedef struct Node{
	DataTpye data;
	Node *left;
	Node *right;
}Node;

typeDef Node *binTree;

递归实现遍历

void preReadNode(Node *){

}

反转二叉树

递归版本

1
2
3
4
5
6
7
8
9
10
TreeNode* invert_BinaryTree_Recursive(TreeNode* head){
    if(head==NULL) return NULL;
    
    TreeNode* node= invert_Binary_Recursive(head->left);
    
	 head->left=invert_Binary_Recursive(head->right);
	 head->right=node;
	 
	 return head;
}

非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
TreeNode* invert_BinaryTree_NonRecursive(TreeNode* head){
    if(head==NULL) return head;


    stack<TreeNode*> nodes;
    nodes.push(head);
    while(!nodes.empty()){
        TreeNode* p=nodes.top();
        nodes.pop();
        swap(p->left,p->right);
        if(p->left) nodes.push(p->left);
        if(p->right) nodes.push(p->right);
    }
    return head;

}