二叉树

二叉树的存在是为了弥补线性表的的不足。

?

?

如上表，顺序表结构和链表结构都不有不足，其算法效率在有些时候低也是结构本身所带来的问题。而树这种半线性结构在实现得当(如avl树，红黑树)的情况下是可以鱼和熊掌皆可得的。我们知道任何树都可以转换成二叉树，对树的研究可以说是对二叉树的研究。

一. 二叉树的数据结构

typedef struct Treenode* Bintree;
typedef struct Treenode{
    int val;
    int height;    //红黑树节点初始高度为-1，因为默认插入红色节点
    RBColor color;    //实现红黑树(RBTree)使用
    Bintree parents;    //父节点指针
    Bintree left;    //左子树节点指针
    Bintree right;    //右子树节点指针
}Tnode;//二叉树节点

?

二. 二叉树的方法

1.生成新节点Node_create(int e,Bintree p)

Bintree Node_create(int e,Bintree p){
    Bintree node=(Bintree)malloc(sizeof(Tnode));
    node->val=e;    
    node->height=0;    //默认为0
    node->color=RB_RED;    //默认红色，方便后续红黑树实现
    node->parents=p;    //传入的父节点
    node->left=node->right=NULL;    //初始没有儿子
    return node;
}//生成新节点

2.先序遍历pre_trave(递归版), pre_trave_1(迭代版)

void pre_trave(Bintree root){
    if(!root) return;
    printf("%d\n", root->val);
    pre_trave(root->left);
    pre_trave(root->right);
}//先序遍历递归版 *先序遍历：先访问父节点再左子树然后右子树

void pre_trave_1(Bintree root){
    stack<Bintree> s;
    Bintree tmp=root;
    while(tmp||!s.empty()){
        while(tmp){
            printf("%d\n", tmp->val);//先序遍历，第一次经过节点即访问
            s.push(tmp);
            tmp=tmp->left;
        }
        if(!s.empty()){
            tmp=s.top();
            s.pop();
            tmp=tmp->right;
        }
    }
}//先序遍历非递归版

二叉树

原文：https://www.cnblogs.com/yhonker/p/12318084.html