亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

1. 前序遍歷：根-左節點-右節點
2. 中序遍歷：左節點-根-右
3. 后序遍歷：左-右-根

前序遍歷：根左右：根>根（左）>左>右（左）>根（右）>左（右）>右

中序遍歷：左根右：左>根（左）>右（左）>根>左（右）>根（右）>右

后序遍歷：左右根：左>右（左）>根（左）>左（右）>右>根（右）>根

對于數組表示的二叉樹：簡單遍歷，無前中后序

函數：

創造函數和析構函數——創建和銷毀樹

SearchNode（Tree *pTree，int nodeIndex）：搜索節點，要指定數組下標

AddNode（Tree *pTree，int nodeIndex，int direction，Node *pNode）：指定往哪一個下標的節點上去添加節點；指定方向：添加的是左孩子還是右孩子；指定要添加的節點：把要添加的節點掛在指定的位置上（相對于根節點而言）

樹的節點的搜索：指定當前節點的索引（下標）即可找到對應的數據

完全可以把一個數組看作一個二叉樹

一個節點若只有右子樹而沒有左子樹，則用 0表達當前位置不存在節點的情況。

索引是與數組與生俱來的。

對于父節點來說，其下標*2+1：左孩子? ；? 其下標*2+2：右孩子

樹的用途：

壓縮軟件--赫夫曼樹

搜索--人機對戰

二叉樹：

1、所有結點的度都小于等于2

二叉樹的遍歷：（ 相對于二叉樹的根來說）

前序遍歷：先訪問根，再訪問左右節點--根左右

中序遍歷：先訪問左節點，再訪問根，再訪問右節點--左根右

后序遍歷：先訪問左右節點，再訪問根（訪問根的操作在最后）--左右根

樹是節點的有限集合

每一個元素都是一個節點

根節點：雙親（一個節點，父節點）

度：當前節點的直接孩子個數

A接著三個節點，度為3，BCD的雙親就是A 節點，A 的孩子就是BCD

對于一棵樹來說，終端節點：葉子（EFGHC）；非終端節點根：（相對于葉子來說）

有序樹：節點不可換順序；無序樹：節點可換順序而不影響邏輯

祖先：當前節點向上的節點直至總根均為其祖先；子孫：從該節點向下伸出的連接的節點均屬于其子孫（A的子孫為BCDEFGH）

深度：結點深度&樹的深度

結點深度：與所在層數有關，在第幾層深度就為幾；

樹的深度：當前樹中結點所具有的最大深度

森林：多顆獨立的樹放在一起成為森林；也可孤木成林

樹

二叉樹的遍歷分為前序，中序，后續?

前中后是訪問根節點順序分為前中后而定義

按照樹的結構遍歷輸出：

遞歸刪除子節點

關于樹的遍歷，在遞歸中，一直往下層走，是如何返回上一層的？

cout << this->Index << endl;????//先輸出當前結點。

this->pLchild->ProTraversal();????//在左結點中，先輸出左結點，如果沒有左右結點，結束語句（跳出函數）。

this->pRchild->ProTraversal();????//在右結點中，先輸出右結點，如果沒有左右結點，結束語句（跳出函數）。

函數有執行順序的，先執行最最最里層的函數，再跳出該函數繼續執行倒第二層函數接下來的函數。以此類推，最后一次執行的是第一次調用此函數的return。

用數組表達二叉樹。? ?沒有節點的地方用0表示。父節點下標*2+1 表示左孩子。? 父節點下標*2+2表示右孩子

我們在構建樹的時候一般都不會用數組，因為我們一開始不會知道樹有多少個節點，用數組的話我們是一開始就聲明一段連續的內存，如果節點沒有預設的那么多就會浪費內存；如果節點超出預計數量，就要重新建立一個新的數組把原來數組的數據傳去新的數組，這樣會浪費計算資源。用指針的話方便無限添加新節點，用數組建構的樹，節點與節點之間不需要是連續的內存，只需要在建立新節點的時候把指針指向父節點即可，方便對樹進行添加與刪除的操作。

二叉樹的遍歷，前中后是相對于根節點來說的。先訪問根節點就是前序，以此類推

二叉樹就是所有節點的度<=2的樹

樹是節點的有限集合

Node.cpp中的SearchNode(int nodeIndex)函數可以很簡化，如下：

Node* Node::SearchNode(int nodeIndex)

{

if (this->index == nodeIndex)

return this;

if (this->pLChild != NULL)

if (this->pLChild->SearchNode(nodeIndex) != NULL)

return this->pLChild->SearchNode(nodeIndex);

if (this->pRChild != NULL)

return this->pRChild->SearchNode(nodeIndex);

return NULL;

}

main.cpp:


#include?<iostream>
#include?"Tree.h"
#include?<stdlib.h>
using?namespace?std;

/*
二叉樹（用鏈表表達）

?結點要素：索引?數據?左孩子指針?右孩子指針?父結點指針

?（頭節點的父結點指針為NULL，葉結點的左右孩子結點指針為NULL）

索引：

?數組表達的二叉樹中的索引指的就是數組的下標
鏈表表達時，索引必須也是當前結點的一部分，所以需要用一個數據成元來表示索引

int?tree[n]?3??5?8???2?6?9?7

?數據：
?此處用int

?左孩子指針、右孩子指針：拿到一個結點時，可以通過其左孩子指針、右孩子指針分別訪問其左孩子結點、右。
????????（0）

????5（1）??????8（2）

2（3）?6（4）??9（5）7（6）

?前序遍歷：（下標）0?1?3?4?2?5?6
?中序遍歷：?3140526
?后序遍歷：3415620

?如果要在孩子結點掛載孩子，需要通過搜索找到孩子結點的索引，所以，查找結點是一個基本操作，通過頭結點找到結點，再進行其他操作。
如果要刪除結點，不僅刪除一個結點，需要把其所有子結點和子結點的子結點全部刪除

?銷毀樹時，也需要通過指針一級一級地找到頭結點一下的所有結點一一進行消除，否則造成內存的泄漏
?*/
int?main()?{
????Node?*node1?=?new?Node();
????node1->index?=?1;
????node1->data?=?5;

????Node?*node2?=?new?Node();
????node2->index?=?2;
????node2->data?=?8;

????Node?*node3?=?new?Node();
????node3->index?=?3;
????node3->data?=?2;

????Node?*node4?=?new?Node();
????node4->index?=?4;
????node4->data?=?6;

????Node?*node5?=?new?Node();
????node5->index?=?5;
????node5->data?=?9;

????Node?*node6?=?new?Node();
????node6->index?=?6;
????node6->data?=?7;

????Tree?*tree?=?new?Tree();
????tree->AddNode(0,0,node1);
????tree->AddNode(0,1,node2);

????tree->AddNode(1,0,node3);
????tree->AddNode(1,1,node4);

????tree->AddNode(2,0,node5);
????tree->AddNode(2,1,node6);

???//?tree->PreorderTraversal();
????tree->InorderTraversal();
//????tree->PostorderTraversal();

????return?0;
}

Tree.cpp:

#include?"Tree.h"
#include?"Node.h"
#include?<iostream>
#include?<stdio.h>
using?namespace?std;


Tree::Tree(){
????m_pRoot?=?new?Node();//頭節點不放有意義的值，index為0；
}


Tree::~Tree()?{//銷毀樹
????DeleteNode(0,NULL);
????//或者m_pRoot->DeleteNode();
}

Node?*Tree::SearchNode(int?nodeIndex)?{//根據索引尋找結點
//遞歸函數
????return?m_pRoot->SearchNode(nodeIndex);
}

bool?Tree::AddNode(int?nodeIndex,int?direction,Node?*pNode)?{//添加結點
????Node?*temp?=?SearchNode(nodeIndex);
????if(temp?==?NULL){
????????return?false;//根本沒有找到對應結點
????}
????//不能直接用外面傳進來的結點，因為外面的函數可以對其進行修改，容易導致其他錯誤
????Node?*node?=?new?Node();
????if(node?==?NULL){
????????return?false;
????}
????//只需要對這兩個值進行復制，其他三個指針不用，因為三個指針的值取決于結點在樹中的位置
????node->index?=?pNode->index;
????node->data?=?pNode->data;
????node->pParent?=?temp;

????if(direction?==?0){
????????temp->pLChild?=?node;
????}

????if(direction?==?1){
????????temp->pRChild?=?node;
????}

????return?true;

}

bool?Tree::DeleteNode(int?nodeIndex,Node?*pNode)?{//刪除結點
????Node?*temp?=?SearchNode(nodeIndex);
????if(temp?==?NULL){
????????return?false;//根本沒有找到對應結點
????}

????if(pNode?!=?NULL){//若pNode==NULL,意思就是不要這個結點，刪了不需要
????????pNode->data?=?temp->data;
????}
????//刪除結點在樹這個層面不太容易操作，所以在Node級進行操作
????//對于Node來說，刪除自己需要：
????//?1.把自己的子結點刪除
????//?2.看自己是父結點的左孩子還是右孩子，把父結點對應指針置為NULL，然后再自殺;

????temp->DeleteNode();
????return?true;
}


void?Tree::PreorderTraversal()?{//前序遍歷,在Node中比在Tree中更容易實現
????m_pRoot->PreorderTraversal();
}
void?Tree::InorderTraversal()?{//中序遍歷
????m_pRoot->InorderTraversal();
}
void?Tree::PostorderTraversal()?{//后序遍歷
????m_pRoot->PreorderTraversal();
}

Tree.h:


#ifndef?INC_0210_TREE_H
#define?INC_0210_TREE_H

#include?"Node.h"
#include?<stdio.h>
class?Tree{
public:
????Tree();//創建樹
????~Tree();//銷毀樹
????Node?*SearchNode(int?nodeIndex);//根據索引尋找結點
????bool?AddNode(int?nodeIndex,int?direction,Node?*pNode);//添加結點
????bool?DeleteNode(int?nodeIndex,Node?*pNode);//刪除結點

????void?PreorderTraversal();//前序遍歷
????void?InorderTraversal();//中序遍歷
????void?PostorderTraversal();//后序遍歷


private:
????Node?*m_pRoot;
};

#endif?//INC_0210_TREE_H

Node.h:

#include?<stdio.h>

#ifndef?INC_0210_NODE_H
#define?INC_0210_NODE_H

class?Node{
public:
????Node();
????Node?*SearchNode(int?nodeIndex);
????void?DeleteNode();
????void?PreorderTraversal();//前序遍歷
????void?InorderTraversal();//中序遍歷
????void?PostorderTraversal();//后序遍歷
????//需要注意，bool不需要，因為在樹這個類中已經找到結點類，無所謂找得到與否，所以也不需要nodeIndex。
????//第二個參數也不需要了，在Tree中的刪除函數已經取到了
????int?index;
????int?data;
????Node?*pLChild;
????Node?*pRChild;
????Node?*pParent;
};

#endif?//INC_0210_NODE_H

Node.cpp:

#include?"Node.h"
#include?"Tree.h"
#include?<stdio.h>
#include?<iostream>
using?namespace?std;

Node::Node()?{
????index?=?0;
????data?=?0;
????pLChild?=?NULL;
????pRChild?=?NULL;
????pParent?=?NULL;
}

Node?*Node::SearchNode(int?nodeIndex){//一個是Tree下面的SearchNode，一個是Node下面的SearchNode，功能基本相同
????//在Node下面實現這個功能，這個功能將來被Tree這個類調用
????if(this->index?==?nodeIndex){
????????return?this;//返回當前這個結點
????}

????Node?*temp?=?NULL;
????if(this->pLChild?!=?NULL){
????????if(this->pLChild->index?==?nodeIndex){
????????????return?this->pLChild;
????????}
????????//若不是左孩子
????????else{
????????????temp?=?this->pLChild->SearchNode(nodeIndex);
????????????if(temp?!=?NULL)?return?temp;
????????}
????}

????if(this->pRChild?!=?NULL){
????????if(this->pRChild->index?==nodeIndex){
????????????return?this->pRChild;
????????}
????????else{
????????????temp?=?this->pRChild->SearchNode(nodeIndex);
????????????if(temp?!=?NULL)?return?temp;
????????}
????}
????return?NULL;
}

void?Node::DeleteNode()?{
????if(this->pLChild?!=?NULL){
????????this->pLChild->DeleteNode();
????}
????if(this->pRChild?!=?NULL){
????????this->pRChild->DeleteNode();
????}
????if(this->pParent?!=?NULL){
????????if(this->pParent->pLChild?==?this){
????????????this->pParent->pLChild?=?NULL;
????????}
????????if(this->pParent->pRChild?==?this){
????????????this->pParent->pRChild?=?NULL;
????????}
????}
????delete?this;
}


void?Node::PreorderTraversal()?{//前序遍歷,在Node中比在Tree中更容易實現
????cout?<<?this->index?<<?"??"<<?this->data?<<?endl;
????if(this->pLChild?!=?NULL){
????????this->pLChild->PreorderTraversal();//通過遞歸，將訪問左結點的概念變成訪問左子樹
????}
????if(this->pRChild?!=?NULL){
????????this->pRChild->PreorderTraversal();
????}
}

void?Node::InorderTraversal()?{//中序遍歷
????if(this->pLChild?!=?NULL){
????????this->pLChild->InorderTraversal();
????}
????cout?<<?this->index?<<?"??"<<?this->data?<<?endl;
????if(this->pRChild?!=?NULL){
????????this->pRChild->InorderTraversal();
????}
}
void?Node::PostorderTraversal()?{//后序遍歷
????if(this->pLChild?!=?NULL){
????????this->pLChild->PostorderTraversal();
????}
????if(this->pRChild?!=?NULL){
????????this->pRChild->PostorderTraversal();
????}
????cout?<<?this->index?<<?"??"<<?this->data?<<?endl;
}

數組表示二叉樹：

Tree.h:


#ifndef?INC_0210_TREE_H
#define?INC_0210_TREE_H

class?Tree{
public:
????Tree(int?size,int?*pRoot);//創建樹
????~Tree();//銷毀樹
????int?*SearchNode(int?nodeIndex);//根據索引尋找結點
????bool?AddNode(int?nodeIndex,int?direction,int?*pNode);//添加結點
????bool?DeleteNode(int?nodeIndex,int?*pNode);//刪除結點
????void?TreeTraverse();//遍歷結點
private:
????int?*m_pTree;//指針指向數組，數組在構造函數中去分配，在析構函數中去銷毀
????int?m_iSize;
};

#endif?//INC_0210_TREE_H

Tree.cpp:



#include?"Tree.h"
#include?<iostream>
using?namespace?std;

Tree::Tree(int?size,int?*pRoot)?{
????m_iSize?=?size;
????m_pTree?=?new?int[size];

????//初始化為0
????for(int?i?=0;i?<?size?;i++){
????????m_pTree[i]?=?0;
????}
????m_pTree[0]?=?*pRoot;//初始化根結點
}

Tree::~Tree(){
????delete?[]m_pTree;
????m_pTree?=?NULL;
}

int?*Tree::SearchNode(int?nodeIndex){
????//對nodeIndex的合法性進行判斷
????if(nodeIndex?<?0?||?nodeIndex?>=?m_iSize){
????????return?NULL;
????}
????//若當前結點沒有意義
????if(m_pTree[nodeIndex]?==?0){
????????return?NULL;
????}
????return?&m_pTree[nodeIndex];
}

bool?Tree::AddNode(int?nodeIndex,int?direction,int?*pNode){
????//先找到對應結點，之前還是需要進行合法性判斷
????if(nodeIndex?<?0?||?nodeIndex?>=?m_iSize){
????????return?false;
????}
????//若當前結點沒有意義
????if(m_pTree[nodeIndex]?==?0){
????????return?false;
????}
????//若合法,0-左，1-右
????if(direction?==?0){
????????if(?nodeIndex?*?2?+?1?>=?m_iSize){
????????????return?false;
????????}
????????//若當前結點沒有意義
????????if(m_pTree[nodeIndex?*?2?+?1]?!=?0){//若左節點已經有值
????????????return?false;
????????}
????????m_pTree[nodeIndex?*?2?+?1]?=?*pNode;//pNode本身是一個指針，我們需要往里面放內容
????}
????if(direction?==?1){
????????if(?nodeIndex?*?2?+?2?>=?m_iSize){
????????????return?false;
????????}
????????//若當前結點沒有意義
????????if(m_pTree[nodeIndex?*?2?+?2]?!=?0){//若左節點已經有值
????????????return?false;
????????}
????????m_pTree[nodeIndex?*?2?+?2]?=?*pNode;//pNode本身是一個指針，我們需要往里面放內容
????}
????return?true;

}

bool?Tree::DeleteNode(int?nodeIndex,int?*pNode){
????//先找到對應結點，之前還是需要進行合法性判斷
????if(nodeIndex?<?0?||?nodeIndex?>=?m_iSize){
????????return?false;
????}
????//若當前結點沒有意義
????if(m_pTree[nodeIndex]?==?0){
????????return?false;
????}
????//若合法,則傳出來
????*pNode?=?m_pTree[nodeIndex];
????//然后把對應結點刪除，即置零
????m_pTree[nodeIndex]?=?0;
????return?true;
}
void?Tree::TreeTraverse(){
????for(int?i=0;i<m_iSize;i++){
????????cout?<<?m_pTree[i]<<"?";
????}
}

main.cpp:


#include?<iostream>
#include?"Tree.h"
#include?<stdlib.h>
using?namespace?std;

/*
二叉樹（數組表示,也可以使用鏈表表達）
課程要求：完成樹的基本操作
1.樹的創建和銷毀
2.樹中節點的搜索
3.樹中節點的添加與刪除
4.樹中節點的遍歷

BOOL?CreatTree(Tree?**pTree,Node?*pRoot);//創建樹
void?DestroyTree(Tree?*pTree);//銷毀樹
Node?*SearchNode(Tree?*pTree,int?nodeIndex);//根據索引尋找節點
BOOL?AddNode(Tree?*pTree,int?nodeIndex,int?direction,Node?*pNode);//添加節點
BOOL?DeleteNode(Tree?*pTree,int?nodeIndex,Node?*pNode);//刪除節點
void?TreeTraverse(Tree?*pTree);//遍歷

關于數組與樹之間的算法轉換
int?tree[n]?3??5?8???2?6?9?7

????????3（0）???????????父結點下標*2+1?該結點左
????????????????????????父結點下標*2+2?該結點右
????5（1）??????8（2）

2（3）?6（4）??9（5）7（6）
?*/
int?main()?{
????int?root?=?3;
????Tree?*pTree?=?new?Tree(10,&root);//調用構造函數
????int?node1?=?5;
????int?node2?=?8;
????pTree->AddNode(0,0,&node1);
????pTree->AddNode(0,1,&node2);

????int?node3?=?2;
????int?node4?=?6;

????pTree->AddNode(1,0,&node3);
????pTree->AddNode(1,1,&node4);

????int?node5?=?9;
????int?node6?=?7;

????pTree->AddNode(2,0,&node5);
????pTree->AddNode(2,1,&node6);

????int?node?=?0;
????pTree->DeleteNode(6,&node);
????cout?<<endl?<<"node="<<node<<?endl;

????pTree->TreeTraverse();

????int?*p?=?pTree->SearchNode(2);
????cout?<<endl?<<"node="<<?*p?<<?endl;

????delete?pTree;//調用析構函數
????return?0;
}

樹是節點的有限集合

度：當前節點的直接的孩子（子節點）

結點深度：在第幾層深度就是幾

樹深度

?二叉樹

1.所有結點的度都<=2

2.（對于根來說）

樹的用途：人機對戰

二叉樹節點要素：

索引 數據 左孩子指針 右孩子指針 父節點指針

之前的是數組二叉樹

現在是鏈表二叉樹

數組2叉樹 刪除一個節點 該節點數據=0則可

插入節點，只需要將索要插入的節點內容賦值給被插入的節點則可

節點序列 根節點序列為n,則2n+1為根節點的左節點